路径规划-多个目的地

Question

问题是：

我有一个图G=（V，E）。顶点的子群U<V、 以及边缘的起始顶点s的权重函数w。

我需要找到从s穿过U中所有顶点的最短路径。

• 计算可以近似，计算时间和路径长度之间应该有一些平衡。我需要一个快速算法/启发式算法，它将产生最短路径的精细近似
• 这个算法（在C++中）实现起来应该不会太复杂。例如，我已经想好了一种方法，将其转化为旅行推销员问题，并使用TSP求解器库或使用某种启发式方法的东西，但找不到，而自己实现启发式方法太难了

非常感谢！=]

Answer 1

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

上述文章中的参考链接到一种将广义TSP问题转换为TSP问题而不使图中节点数加倍的方法。

记录保存的TSP求解器是免费提供的，被称为Concorde，可以从这里下载，它可以作为命令行工具运行（可能作为库，不确定）。

当我试图为RevolvoMan4k游戏创建一个解算器时，我遇到了GTSP，通过按下最少的按钮来获得每个级别上的所有金钱。（这是一个有趣的游戏，但在50级之后，级别是随机的，所以有些级别可能是不可能的，需要用"N"跳过）。

Answer 2

假设您有3个顶点：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的算法，。。。