由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同 。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树 。
分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点 。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解 。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树 。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树 。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同 。在分支限界法中，每一个活结点只有一次机会成为扩展结点 。活结点一旦成为扩展结点，就一次性产生其所有儿子结点 。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程 。这个过程一直持续到找到所求的解或活结点表为空时为止 。
回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解 。
分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解 。
推荐阅读
- 余光中经典情话有哪些？
- 召回算法实践总结
- 家庭婚姻感悟经典句子有哪些？
- 人工智能技术含量降级，算法工程师从主人沦为保姆？是喜是忧？
- 巴菲特十句最经典名言是什么？
- Google tcp拥塞控制 bbr算法
- 字符串匹配KMP算法
- 微软|Win11企业安装率仅1.44% 还不如经典的WinXP多
- Python经典推导式，助你高效优雅的撸代码
- 岁月静好的经典句子有哪些？