比较回溯法和限界剪枝法的异同

比较回溯法和限界剪枝法的异同如下：

一、共同点

都是在问题的状态空间树上搜索问题解的算法，都通过活结点表实现。都用约束函数剪去不含答案结点的分枝，用限界函数剪去不含最优解的分枝。

二、区别

1.求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有可行解；而分枝限界法的求解目标是找出满足约束条件的一个可行解，或某种意义下的最优解。

2.搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法以广度优先的方法搜索解空间树。

3.对当前扩展节点的扩展方式不同：回溯法中的每个活结点可能多次成为当前扩展节点，纵深方向扩展其中一个儿子，然后再回溯后扩展其他儿子；而分枝限界法中每个活结点只有一次机会成为扩展结点，一次产生所有的孩子结点，自身成为死结点，之后无需返回该结点处。

拓展：

回溯法是一种穷举搜索的算法，通过逐步构建候选解，然后根据约束条件进行判断，如果当前的候选解不能满足约束条件，就进行回溯，撤销上一步的选择，继续搜索其他可能的解。回溯法常用于求解排列、组合、子集等问题。

回溯法的基本思想是深度优先搜索，在搜索的过程中利用剪枝策略来减少搜索空间。回溯法的核心是递归实现，在每一层递归中，都会进行选择、判断和回溯操作。

回溯性思维的特点就是由当前及过去，由表及里地追根溯源、“顺藤摸瓜”过程。其方法主要有：(1)倒推法，即按照问题发生的经过顺序倒推，以寻找问题究竟是在哪一个环节上引起的，找出问题的症结所在。(2)析因实验法，即通过实验寻找原因。(3)纵横比较法，即在横向比较发现问题的基础上，进而纵向比较，找出问题的原因。(4)概率统计因果法，即通过对某种原因在历史上出现的概率进行统计，以作出决策的概括。(5)再认识，即对已经认识过的因果关系，根据新的历史经验重新加以认识，以取得新的认识成果，澄清以前认识不当之处。科学的决策要求决策者在探求问题产生的原因时，要善于正确地运用回溯性思维去加以分析、研究和判断，为决策提出有力的、准确的依据。

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com