29-回溯法与分支限界法的异同

6.5　回溯法与分支限界法的异同

回溯法与分支限界法的比较如下。

1．相同点

（1）均需要先定义问题的解空间，确定的解空间组织结构一般都是树或图。

（2）在问题的解空间树上搜索问题解。

（3）搜索前均需确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。

（4）搜索过程中必须判断扩展生成的结点是否满足判断条件，如果满足，则保留该扩展生成的结点，否则舍弃。

2．不同点

（1）搜索目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

（3）扩展方式不同：在回溯法搜索中，扩展结点一次生成一个孩子结点，而在分支限界法搜索中，扩展结点一次生成它所有的孩子结点。