如果城市很少（少于 6 个），旅行商问题的最佳算法是什么？

Question

我看过很多尝试解决旅行商问题的解决方案，如果 p!=np ，但我想知道如果只有 6 或 5 个城市的最佳解决方案，哪种算法将给出最佳解决方案在这种情况下？

Answer 1

对于6个城市，一次计算15个城际距离，然后选择一个起点并评估可能的5!/2=60个周期（其中一半相同方向反转）。

为了获得最大效率，您可以对排列进行硬编码 table。另一种可能的措施是以这样一种方式安排周期长度计算，即可以重复使用一些部分和，也可以借助硬编码 tables.

一些求和一旦超过当前最短时间就可能会过早流产。首先尝试最短的段可能会获得更多收益。

对这些主题进行彻底的探索似乎是一种努力，节省下来的钱可能不值得关心，除非你有数百万个 6 城市问题需要解决。