回溯法=算法思想

59 阅读 0 评论 39 点赞

我是靠谱客的博主矮小冬瓜，最近开发中收集的这篇文章主要介绍回溯法=算法思想，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

回溯法是比贪心法和动态规划法更一般的方法。
解为n-元组(x0,x1,…,xn-1)形式。
通过搜索状态空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。
回溯法是一种选优搜索法，按照选优条件深度优先搜索，以达到目标。当搜索到某一步时，发现原先选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态称为“回溯点”。
.树中每个结点称为一个问题状态；
若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；
若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；
如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。
————————————————
版权声明：本文为CSDN博主「深度学习从入门到放弃」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44771102/article/details/127546393