c++ - 路径规划-多个目的地

问题是这样的:

我有一个图G =(V，E)。 U
我需要找到从s穿过U中所有顶点的最短路径。

计算可以近似，计算时间和路径长度之间应该有一些平衡。
我需要一种快速的算法/启发式算法，可以对最短的路径产生近似的近似值。

该算法实现起来不太复杂(在C++中)。例如，我已经想到了一种将其转化为Traveling Salesman问题，使用TSP求解器库或使用某种启发式方法但找不到的方法的方法，而我自己也可以实现启发式方法硬。

谢谢先进! =]

最佳答案

这是“旅行推销员问题”的一个变体，称为“集合TSP问题”或“广义TSP”。这是Wikipedia link。

上一篇文章的引用链接到method，用于将广义TSP问题转换为TSP问题而不会使图中的节点数量加倍。

保留记录的TSP求解器是免费提供的，称为Concorde，可以从here下载，可以作为命令行工具运行(不确定的是作为库运行)。

当尝试通过按最小数量的按钮获得每个级别的所有资金来创建RevolvoMan4k游戏的求解器时，我遇到了GTSP。 (这是一个有趣的游戏，但是级别50之后，级别是随机的，因此有些级别是不可能的，需要用'N'跳过)。