'回溯'和'分支限界法'的区别

Question

在回溯算法中，我们同时使用广度优先搜索和深度优先搜索。即使在分支界限算法中，我们也会使用广度优先搜索和深度优先搜索以及最小代价搜索。

那么何时使用回溯算法，何时使用分支界限算法呢？

使用分支界限算法是否会降低时间复杂度？

分支界限算法中的最小代价搜索是什么？

- Varun Teja

Answer 1

回溯法

1. 它用于查找问题的所有可能解决方案。
2. 它以深度优先搜索（DFS）的方式遍历状态空间树。
3. 当它意识到做出了错误选择时，会通过撤销上一个选择来进行回溯。
4. 它在搜索状态空间树直到找到解决方案。
5. 它涉及到可行性函数。

分支定界法

1. 它用于解决优化问题。
2. 它可以以任何方式遍历树，DFS或BFS。
3. 当它发现已经有更好的最优解时，会放弃该前置解。
4. 它完全搜索状态空间树以获得最优解。
5. 它涉及到一个界限函数。

- Abhishek Dey

---

回溯算法总能找到最优解吗？ - Varun Teja

是的，总是提供最佳解决方案。 - Abhishek Dey

@AbhishekDey实际上，回溯法可以给出*一个解决方案，但不一定是最优解。回溯法最适用于约束满足问题，而分支限界法最适用于优化问题。 - Cameron Gagnon

@CameronGagnon 为了明确起见，回溯算法在理论上保证最优性，因为它将探索所有解决方案，仅修剪那些它确定不可能是最优的。当然，在实践中，如果组合数是指数级别的，并且没有智能修剪，这种算法在中等到大型实例上可能需要很长时间。 - Patrice Gahide

Answer 2

回溯法

回溯法是解离散约束满足问题（CSP）的通用概念，它使用DFS。一旦到达一个清楚无法构造解决方案的点，就会返回到上次有选择的地方。这样，它迭代所有可能的解决方案，有时可能会提前中止。

分支限界法

分支限界法（Branch-and-Bound，简称B&B）是解离散有约束优化问题（COP）的概念。它们类似于CSP，但除了具有约束条件外，还有一个优化准则。与回溯法不同，B&B使用广度优先搜索。

名字中的“限界”部分指的是B&B修剪可能解的空间的方式：它得到一种启发式，获得一个上界。如果无法改进，就可以丢弃子树。

除此之外，我看不出与回溯法的区别。

其他来源

网络上有其他答案提出了非常不同的说法：

• 分支限界法是带剪枝的回溯法（来源）

- Martin Thoma

Answer 3

回溯算法

• 回溯是一种通用算法，用于找到某些计算问题的所有（或一些）解决方案，特别是约束满足问题。它逐步构建候选解决方案，并放弃每个部分候选者c（“回溯”），因为它确定c无法完成为有效解决方案。
• 它枚举了一组部分候选者，原则上可以通过各种方式完成，以给出给定问题的所有可能解决方案。完成是通过一系列候选扩展步骤逐步完成的。
• 在概念上，部分候选者表示为树结构的节点，即潜在搜索树。每个部分候选者是与其仅相差一个扩展步骤的候选者的父级，树的叶子是不能再进一步扩展的部分候选者。
• 它以深度优先顺序（DFS）从根向下递归地遍历此搜索树。当它意识到自己做出了错误选择并撤消最后一次选择时，它会进行回退。
• 更多细节请参见：Sanjiv Bhatia关于UMSL的回溯演示。

分支定界法

• 分支定界算法通过状态空间搜索对候选解进行系统枚举：将候选解集合视为具有根节点的树。
• 该算法探索这棵树的分支，这些分支表示解集的子集。在枚举分支的候选解之前，将检查该分支是否能够产生优于算法迄今为止找到的最佳解的上界和下界估计值，如果不能，则放弃该分支。
• 它可以以任何以下方式遍历树：
  1. BFS (广度优先搜索)或(FIFO)分支定界
  2. D-Search或(LIFO)分支定界
  3. 最小计数搜索或(LC)分支定界
• 更多信息请参考：Sanjiv Bhatia关于UMSL的分支定界演示。

- kshitij chaurasiya

Answer 4

回溯法： -从解空间中选择最优解。 -通过深度优先搜索（DFS）进行遍历。

分支界定法： -广度优先搜索（BFS）遍历。 -只生成有价值的解，而不是生成所有可能的解。

- user117172