performance - 使用回溯和分支定界的优点

Question

我知道 DP 为许多 NP 完全问题（如 TSP）提供了更好的性能。虽然所需的空间很大，但它很好地降低了复杂性。

但是与蛮力搜索相比，我无法理解分支定界和回溯的效率。

在最坏的情况下，蛮力是否等于 b&b 或回溯？

Answer 1

通过穷举搜索，您将计算所有 N! 节点之间的可能路径。使用回溯，您可能会计算出访问一半节点的路线，注意到它已经比目前找到的最佳路线更昂贵，然后停止调查该部分路线。通过这样做，您跳过了计算通过完成该部分路线产生的所有路线，从而节省了详尽搜索的时间，这将继续检查它们。