问“回溯”和“分支和绑定”的区别

EN

回溯

1. 它用于查找问题的所有可能解决方案。
2. 它以DFS(深度优先搜索)的方式遍历状态空间树。
3. 它意识到自己做了一个错误的选择，并通过备份撤消最后一个选择。
4. 它搜索状态空间树，直到找到解决方案。
5. 它涉及可行性all

Branch-and-Bound

它是用来解决优化问题的。它可以以任何方式遍历树，DFS或BFS.

• It意识到它已经有了预解所导致的更好的最优解，所以它放弃了pre-solution.

• It完全搜索状态空间树来获得最优解。

• 它涉及到一个边界DFS

回溯

回溯是求解离散约束满足问题的一个通用概念。它使用DFS。一旦它达到了无法构造解决方案的地步，它就会返回到最后一个可以选择的点。通过这种方式，它会迭代所有可能的解决方案，有时可能会提前中止。

分支定界

分枝定界(B&B)是求解离散约束优化问题(COPs)的一个概念。它们类似于CSP，但除了具有约束外，它们还具有优化标准。与回溯相反，B&B使用广度优先搜索。

名称的一部分，边界，指的是B&B修剪可能解的空间的方式:它得到一个启发式方法，并得到一个上界。如果不能改善这一点，则可以丢弃超树。

除此之外，我看不出回溯有什么不同。

其他来源

在网络上还有其他的答案，它们做出了截然不同的声明：

• Branch-and-Bound正在通过修剪(source)

进行回溯

回溯

• Backtracking是一种通用算法，用于寻找某些计算问题的全部(或部分)解，特别是约束满足问题，它逐步建立解的候选者，并在确定c不可能完成有效解时立即放弃每个部分候选者c(“回溯”)。
• 它枚举了一组部分候选者，原则上可以用各种方式完成，以给出给定问题的所有可能解。完成是通过一系列候选扩展步骤逐步完成的。
• 从概念上讲，部分候选被表示为潜在搜索树树结构的节点。每个部分候选者都是与其不同的候选者的父代，这些候选者只有一个扩展步骤，树的叶子是不能进一步扩展的部分候选者。
• 它以深度优先的顺序从根向下递归遍历此搜索树。它意识到自己做了一个错误的选择，并通过备份来撤消最后一个选择。有关更多详细信息，请访问
• ：Sanjiv Bhatia's presentation on Backtracking for UMSL.

分支定界

• 分支定界算法由通过状态空间搜索对候选解决方案的系统枚举组成:候选解决方案的集合被认为形成了一棵根树，整个集合位于根部。
• 该算法探索此树的分支，这些分支表示解决方案集合的子集。在枚举分支的候选解之前，对照最优解的上界和下界检查分支，并且如果分支不能产生比algorithm.
• It迄今发现的最佳解更好的解，则丢弃该分支。
  1. BFS (呼吸优先搜索)或(先进先出)分支和Bound
  2. D-Search或(后进先出)分支和边界
  3. Least计数搜索或(LC)分支和LIFO

​

有关更多信息，请访问：Sanjiv Bhatia's presentation on Branch and Bound for UMSL.