'回溯'和'分支和界限'之间的区别

Question

在回溯中,我们使用bfs和dfs.Even在分支和绑定中我们使用bfs和dfs以及最低成本搜索.

所以我们何时使用回溯,何时使用分支和绑定

使用分支和绑定会减少时间的复杂性吗？

什么是分支机构中的最低成本搜索？

如果我错了,请纠正我

谢谢

Answer 1

回溯

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

分支定界

1. 它用于解决优化问题。
2. 它可以以任何方式遍历树，DFS 或 BFS。
3. 它意识到它已经有了一个更好的最优解，这是预解导致的，所以它放弃了那个预解。
4. 它完全搜索状态空间树以获得最优解。
5. 它涉及一个边界函数。