我了解“分支定界算法”如何解决旅行商问题，但是在尝试理解算法比蛮力更快时遇到了麻烦。我所看到的方式，您最终将走遍所有道路。有人可以举例说明B＆B算法比强行使用所有路径快吗？
maochanggeng 回答：解决Traveling Salesman问题时，分支定界算法比暴力算法快多少？
假设我们有以下欧氏TSP实例：
{{1}}
每个数字都是一个顶点，所有节点之间的线段是边（未绘制）。
暴力破解会检查所有8个！ = 40320可能的路径。
另一方面，分支定界算法可以从路径0→1→2→3→4→5→6→7开始，这恰好是最佳路径，并过滤掉所有其他路径首先在左边的节点和右边的节点之间不止一次地交替。例如，当它考虑部分路径0→4→1时，会看到该前缀的长度已经超过了迄今为止找到的最短路径的长度，因此无需下降并检查以0→开头的每条路径分别从4→1。仅此前缀就过滤掉5个！ = 120条单独的路径，但是有96个这样的交替前缀，它们会累计过滤掉11520个潜在解决方案，占解决方案空间的29％。