在回溯中，我们同时使用 bfs 和 dfs。即使在分支定界中，我们也使用 bfs 和 dfs 来进行最低成本搜索。
所以我们什么时候使用回溯，什么时候使用分支定界
使用分支定界会降低时间复杂度吗？
什么是分支定界中的最低成本搜索？
问问题
27527 次
4 回答
13
回溯
- 它用于查找问题的所有可能解决方案。
- 它通过DFS（深度优先搜索）方式遍历状态空间树。
- 它意识到它做出了错误的选择并通过备份撤消了最后的选择。
- 它搜索状态空间树，直到找到解决方案。
- 它涉及可行性函数。
分支定界
- 它用于解决优化问题。
- 它可以以任何方式遍历树，DFS 或 BFS。
- 它意识到它已经有了预解决方案导致的更好的最佳解决方案，因此它放弃了该预解决方案。
- 它完全搜索状态空间树以获得最优解。
- 它涉及一个边界函数。
于 2015-05-04T08:10:52.817 回答
3
回溯
回溯是解决离散约束满足问题（CSP）的一般概念。它使用 DFS。一旦到了很明显无法构建解决方案的地步，它就会回到有选择的最后一点。这样它会迭代所有潜在的解决方案，有时可能会提前中止。
分支定界
分支定界 (B&B) 是解决离散约束优化问题 (COP) 的概念。它们与 CSP 类似，但除了具有约束之外，它们还具有优化标准。与回溯相比，B&B 使用广度优先搜索。
名称的一部分，即bound，指的是 B&B 修剪可能解决方案空间的方式：它获得了一个获得上限的启发式方法。如果这无法改进，则可以丢弃 sup-tree。
除此之外，我看不出回溯有什么不同。
其他来源
网络上还有其他答案，它们做出了截然不同的陈述：
- Branch-and-Bound 是通过修剪回溯（来源）
于 2020-03-30T18:21:52.747 回答
1
回溯
- 回溯是一种通用算法，用于找到一些计算问题的所有（或部分）解决方案，特别是约束满足问题，它逐步构建解决方案的候选者，并在确定 c 不能时放弃每个部分候选者 c（“回溯”）可能完成一个有效的解决方案。
- 它列举了一组部分候选，原则上，它们可以以各种方式完成，以给出给定问题的所有可能解决方案。完成是通过一系列候选扩展步骤逐步完成的。
- 从概念上讲，部分候选被表示为树结构的节点，即潜在搜索树。每个部分候选者都是与它相差一个扩展步骤的候选者的父节点，树的叶子是不能进一步扩展的部分候选者。
- 它以深度优先顺序 (DFS) 从根向下递归遍历此搜索树。它意识到它做出了错误的选择并通过备份撤消了最后的选择。
- 更多详情：Sanjiv Bhatia 关于 UMSL 回溯的演讲。
分支和绑定
- 分支定界算法包括通过状态空间搜索对候选解进行系统枚举：候选解的集合被认为是形成一棵有根树，整个集合在根处。
- 该算法探索这棵树的分支，这些分支代表解决方案集的子集。在枚举分支的候选解之前，会根据最优解的估计上限和下限检查分支，如果它不能产生比算法迄今为止找到的最佳解更好的解，则将其丢弃。
- 它可以通过以下任何方式遍历树：
- BFS （呼吸优先搜索）或（FIFO）分支定界
- D-Search或(LIFO) 分支定界
- 最少计数搜索或(LC) 分支定界
- 更多信息：Sanjiv Bhatia 关于 UMSL 的 Branch and Bound 的演讲。
于 2017-04-04T21:12:22.507 回答
0
回溯：-从解空间中选择最优解。- 遍历 DFS。分支定界：-BFS 遍历。- 这里只产生富有成效的解决方案，而不是产生所有可能的解决方案。
于 2020-04-01T16:31:43.413 回答