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

Question

有人知道算法或做某事吗

所以我有与弧连接的节点，我必须找到一个解决方案来找到覆盖所有节点的近似最短路径。（我只能拜访他们一次）

它必须是一个近似路径，因为它需要很长时间才能得到最短路径

感谢您的回答:)

（我必须在java中这样做）

Answer 1

这被称为旅行推销员问题，一个合理且快速的近似方法是始终访问最近的未访问节点，然后在其他几个起始位置重试相同的操作。通常，这会让您非常接近最佳解决方案。

另一种算法是先构造图的最小生成树，然后删除重复的节点。这保证了次优性的某个上限（在欧几里得情况下不超过两倍，（维基百科））

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

一旦你有了一个解决方案（即使是一个糟糕的解决方案），你可以通过 K-opt 来改进它：重复选择 K 个随机边，将它们完全删除，然后找到重新连接新端点的最佳方法。K-opt 的一个变体是Lin-Kerningham启发式算法，它交替使用 2-opt 步骤和 3-opt 步骤（以某种顺序），其中三个边中的两个总是相邻的。

如果大多数边丢失或很长（两个节点之间的距离不形成度量），那么您就有问题了。假设它是 NP 完全的，如果缺少边，则决定是否存在这样的路径。

Answer 2

一个非常快速的近似是沿着空间填充曲线对顶点进行排序。空间填充曲线减少了维度并且还保留了一些空间信息。尝试旅行推销员问题的摩尔曲线，因为它是 4 条希尔伯特曲线的副本，因此起点和终点彼此相邻。但是画起来有点贵。

Answer 3

就在这里。该方法称为“遗传优化”，具体如下： 1. 找到一个解决方案，即访问每个节点一次的路径。2. 随机选择 k 个相邻节点：N1,N2..Nk : X->N1->..Nk->Y 3. 使用节点 N1..Nk 检查从 X 到 Y 是否有更短的路径 4.将路径 X -*> Y 替换为较短的解决方案 5. goto 2

k 必须很小（5 或更少），以便您可以轻松找到更短的组合

它的好处是您可以随时停止并使用现有的解决方案。一个改进是随机选择一个较大的 k 一次。

Answer 4

如果您不需要自己实现算法，您可能需要查看JGraphT。它有一个算法的实现来找到哈密顿循环。