求解旅行商问题时分支定界算法比蛮力算法快吗？

Question

我了解分支定界算法是如何解决旅行商问题的，但是我很难理解算法比蛮力要快的多。我所看到的方式，您最终将走遍所有道路。有人可以举例说明B＆B算法比强行使用所有路径快吗？

Answer 1

假设我们有以下欧氏TSP实例：

0                                                       7
1                                                       6
2                                                       5
3                                                       4

每个数字是一个顶点，所有节点之间的线段是边。

强力方法会检查所有8个！ = 40320可能的路径。

另一方面，分支定界算法可能从路径0→1→2→3→4→5→6→7开始，这恰好是最佳路径，并过滤掉所有其他开始的路径通过在左侧的节点和右侧的节点之间多次切换。例如，当它考虑部分路径0→4→1时，会看到该前缀的长度已经超过了迄今为止找到的最短路径的长度，因此无需下降并检查以0→开头的每条路径分别从4→1。仅此前缀就过滤掉5个！ = 120条单独的路径，但是有96条这样的交替路径，它们会累计滤除11520个潜在解决方案，占解决方案空间的29％。