路径规划 - 多个目的地

我有一个图G =（V，E）。顶点的子组U < = V和起始顶点s。权重函数w用于边缘。

我需要找到“S”，通过所有的顶点在美国

计算可以近似通过最短路径，应该是计算时间和路径长度之间的某种平衡。我需要一个快速的算法/启发式，将产生最短路径的罚款近似。
这个算法不应该太复杂（C++）。例如，我已经想到了一种将它变成旅行推销员问题的方法，并且使用TSP解算器库或者某种启发式的方法，但是找不到任何方法，并且自己实施启发式方法也是如此硬。

谢谢先进！ =]

2012-08-23 GalDude33

想象一下，你有3个顶点：S，A和B. 现在，假设我们需要找到从S到A和B的最短路径。最简单的方法是找到哪个点更接近于S：A或B.如果您的图实际上有一些空间数据，则可以使用顶点的坐标来近似此值，否则，您将不得不从S到每个目的地获得最短路径。选择最近的目的地，在这种情况下，让我们说这是A，然后在那里旅行。现在你唯一要去的地方是B.计算A到B的最短路径，然后去那里。

现在，在多于2个目的地的情况下，您可以递归执行此操作。我不知道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算法，...

来源

2012-08-23 03:22:58 bigblind

这是称为Set TSP问题或广义TSP的旅行推销员问题的变体。这里是维基百科link。

上述文章的参考链接到method用于将通用TSP问题转换为TSP问题，而不会使图表中的节点数量加倍。

记录持有TSP解算器是免费提供的，称为Concorde，可以从here下载，它可以作为命令行工具运行（可能作为库，不确定）。

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

来源

2012-08-23 03:37:21 Xantix

是的，正如我所说我知道如何使它成为TSP问题，但我无法理解如何将concrode的求解器集成到我的C++程序中（如果可能的话）。也AFAIK concrode是一个确切的求解器，而不是一个启发式解算器，我认为... – GalDude33

路径规划 - 多个目的地

回答

相关问题