Lol*_*lau 2 java algorithm path shortest-path
有人知道算法或其他事情要做
所以我有节点与arc连接,我必须找到一个解决方案来找到覆盖所有节点的近似最短路径.(我只能访问一次)
它必须是近似路径,因为它需要很长时间才能获得最短路径
谢谢你的回答:)
(我必须在java中这样做)
这被称为旅行商问题,合理且快速的近似是始终访问最近的未访问节点,然后用其他几个起始位置重试.通常情况下,这会让您非常接近最佳解决方案.
另一种算法是首先构造图的最小生成树,然后删除重复的节点.这保证了次优性的某个上限(在欧几里德案例中不超过两倍,(维基百科))
另一种算法是从前三个节点开始,然后按照某种顺序添加下一个节点(初始,按x坐标排序,按照距中心的距离排序......)通过拆分现有边缘(或在末尾添加新节点) ,在最短路径的情况下),同时保持路径尽可能短.
一旦你有了解决方案(即使是坏的解决方案),你可以通过K-opt改进它:反复选择K个随机边缘,完全删除它们并找到重新连接新端点的最佳方法.K-opt的变体是Lin-Kerningham启发式,它将2-opt步骤与3-opt步骤(按某种顺序)交替,其中三个边缘中的两个总是相邻.
如果大多数边缘丢失或很长(两个节点之间的距离不形成度量)那么你就会遇到问题.让我们说它的NP-complete确定如果缺少边缘,这条路径是否存在.