路径规划-多个目的地

Question

问题是：

我有一个图G=(V，E)。顶点U<=V的子群和边的起始顶点s.权函数w。

我需要找到通过美国所有顶点的“s”的最短路径。

• 计算可以近似，在计算时间和路径长度之间应有一定的平衡。我需要一个快速的算法/启发式，将产生一个很好的最短路径近似。
• 这个算法不应该太复杂，难以实现(在C++中)。例如，我已经想出了一种方法，把它变成一个旅行推销员问题，并使用TSP求解器库或使用某种启发式的东西，但是找不到，而实现这个启发式本身将是太困难了。

谢谢你！=]

Answer 1

这是旅行商问题的一个变体，称为集TSP问题，或广义TSP问题。这是维基百科的链接。

上述文章中的引用链接到方法，用于将广义TSP问题转换为TSP问题，而不将图中的节点数加倍。

该记录保存TSP解决程序是免费的，被称为协和，可以从这里下载，它可以作为命令行工具运行(可能是一个库，不确定)。

我在尝试为游戏RevolvoMan4k创建一个解决程序时，遇到了GTSP，只要按下最小的按钮，就能在每个级别上获得所有的钱。(这是一个有趣的游戏，但在50级之后，水平是随机的，所以有些可能是不可能的，需要跳过'N')。

Answer 2

假设你有三个顶点: S，A和B。现在，假设我们需要找到从S到A和B的最短路径，最简单的方法是找出哪个点更接近S: a或B。如果你的图有一些空间数据，你可以用顶点的坐标来近似，否则，你必须得到从S到每个目的地的最短路径。选择最近的目的地，在这种情况下，假设是A，然后去那里旅行。现在你唯一可以去的地方是B，计算出从A到B的最短路径，然后去那里。

现在，在有两个以上目的地的情况下，您可以递归地这样做。我不知道C++，但这里有一些伪代码可以让你开始

function pathThrough(startNode,destinationNodes[])
    closestNode = getClosestNode(startNode,destinationNodes)
    newDestinations = removeFromArray(destinationNodes,closestNode)
    return joinPaths(getShortestPath(startNode,closestNode),pathThrough(closestNode,newDestinations.))

对于closestNode和getShortestPath函数，您可以使用任何适合您的图的搜索算法，A*，dijkstra的算法，.