回溯与分枝定界的区别

Question

在回溯中，我们同时使用bfs和DFS。即使在分支和定界中，我们也使用bfs和dfs作为最小代价搜索的补充。

那么我们什么时候使用回溯，什么时候使用分支和定界

使用分支和定界能降低时间复杂度吗？

什么是最小成本的分支和界搜索？

Answer 1

回溯

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

分枝定界

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