1

问题是这样的：

我有一个图 G=(V,E)。顶点子组 U<=V 和起始顶点 s。边缘的权重函数 w。

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

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

感谢先进！=]

4

2 回答 2

3

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

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

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

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

于 2012-08-23T03:37:21.440 回答
0

假设您有 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.))

对于最接近的节点和 getShortestPath 函数，您可以使用任何适合您的图形的搜索算法、A*、dijkstra 算法，...

于 2012-08-23T03:22:58.513 回答