java - 如何获得近似解以获得通过所有节点的最短路径

Question

<分区>

Answer 1

这被称为 Travelling Salesman Problem一个合理且快速的近似方法是始终访问最近的未访问节点，然后在其他几个起始位置重试。通常，这会让您非常接近最佳解决方案。

另一种算法是先构造图的最小生成树，然后删除重复的节点。这保证了次优性的一定上限(在欧几里德情况下不超过两倍，(wikipedia))

另一种算法是从前三个节点开始，然后通过拆分现有边(或添加新边)以某种顺序添加下一个节点(初始、按 x 坐标排序、按距中心的距离排序...)最后，在最短路径的情况下)同时保持路径尽可能短。

一旦你有了一个解决方案(即使是一个糟糕的解决方案)，你可以通过 K-opt 改进它:重复选择 K 个随机边缘，完全删除它们并找到重新连接新端点的最佳方法。 K-opt 的一个变体是 Lin-Kerningham将 2-opt 步骤与 3-opt 步骤(按某种顺序)交替进行的启发式算法，其中三个边中的两个始终相邻。

如果大部分边缺失或很长(两个节点之间的距离不构成度量)，那么您就有问题了。我们只是说它是 NP 完全的，如果有缺失的边，确定这样的路径是否存在。