当前位置：文江博客话题详情

查找图中访问某些节点的最短路径

发布于 2024-07-07 06:26:05 字数 420 浏览 4 评论 0原文

我有一个大约有 100 个节点和大约 200 个边的无向图。一个节点标记为“开始”，一个节点标记为“结束”，大约有十几个标记为“必须通过”。

我需要找到通过该图的最短路径，该路径从“开始”开始，在“结束”结束，并通过所有“必须通过”节点（以任何顺序）。

（ http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是有问题的图表 -它代表宾夕法尼亚州兰卡斯特的玉米迷宫）

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

旧伤还要旧人安 2024-07-14 06:26:05

其他人将其与旅行商问题进行比较可能没有仔细阅读您的问题。在 TSP 中，目标是找到访问所有顶点的最短循环（哈密顿循环）——它对应于将每个节点标记为“必须通过”。

就您而言，考虑到您只有大约十二个标记为“必须通过”的，并且考虑到 12 个！相当小（479001600），您可以简单地尝试仅“必须通过”节点的所有排列，并查看按该顺序访问“必须通过”节点的从“开始”到“结束”的最短路径 - 它将简单地是该列表中每两个连续节点之间的最短路径的串联。

换句话说，首先找到每对顶点之间的最短距离（您可以使用 Dijkstra 算法或其他算法，但对于这些小数字（100 个节点），即使是最简单的代码 Floyd-Warshall 算法将及时运行）。然后，一旦将其放入表中，请尝试“必须通过”节点的所有排列以及其余的排列。

像这样的东西：（

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

当然，这不是真正的代码，如果你想要实际的路径，你必须跟踪哪种排列给出最短距离，以及所有对的最短路径是什么，但你明白了.)

对于任何合理的语言，它最多会在几秒钟内运行:)
[如果有 n 个节点和 k 个“必须通过”节点，则 Floyd-Warshall 部分的运行时间为 O(n³)，所有排列部分的运行时间为 O(k!n)，并且100^3+(12!)(100) 实际上是微不足道的，除非你有一些真正的限制性约束。]

Everyone else comparing this to the Travelling Salesman Problem probably hasn't read your question carefully. In TSP, the objective is to find the shortest cycle that visits all the vertices (a Hamiltonian cycle) -- it corresponds to having every node labelled 'mustpass'.

In your case, given that you have only about a dozen labelled 'mustpass', and given that 12! is rather small (479001600), you can simply try all permutations of only the 'mustpass' nodes, and look at the shortest path from 'start' to 'end' that visits the 'mustpass' nodes in that order -- it will simply be the concatenation of the shortest paths between every two consecutive nodes in that list.

In other words, first find the shortest distance between each pair of vertices (you can use Dijkstra's algorithm or others, but with those small numbers (100 nodes), even the simplest-to-code Floyd-Warshall algorithm will run in time). Then, once you have this in a table, try all permutations of your 'mustpass' nodes, and the rest.

Something like this:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Of course that's not real code, and if you want the actual path you'll have to keep track of which permutation gives the shortest distance, and also what the all-pairs shortest paths are, but you get the idea.)

It will run in at most a few seconds on any reasonable language :)
[If you have n nodes and k 'mustpass' nodes, its running time is O(n³) for the Floyd-Warshall part, and O(k!n) for the all permutations part, and 100^3+(12!)(100) is practically peanuts unless you have some really restrictive constraints.]

回复收藏 0 原文

行至春深 2024-07-14 06:26:05

运行 Djikstra 算法查找所有关键节点（起点、终点和必须节点）之间的最短路径-pass)，那么深度优先遍历应该告诉您通过生成的子图接触所有节点的最短路径 start ... Mustpasses ... end

回复收藏 0 原文

就像说晚安 2024-07-14 06:26:05

这是两个问题……Steven Lowe指出了这一点，但没有对问题的后半部分给予足够的尊重。

您应该首先发现所有关键节点（起点、终点、必须经过）之间的最短路径。一旦发现这些路径，您就可以构建一个简化的图，其中新图中的每条边都是原始图中从一个关键节点到另一个关键节点的路径。您可以使用许多寻路算法来找到最短路径。

不过，一旦有了这个新图表，您就完全遇到了旅行推销员问题（好吧，几乎......不需要返回到起点）。上面提到的任何与此相关的帖子都将适用。

回复收藏 0 原文

花之痕靓丽 2024-07-14 06:26:05

实际上，您发布的问题与旅行推销员类似，但我认为更接近于简单的寻路问题。您不需要访问每个节点，而只需要在尽可能短的时间（距离）内访问一组特定的节点。

这样做的原因是，与旅行商问题不同，玉米迷宫不允许你直接从地图上的任何一点旅行到任何其他点，而不需要经过其他节点才能到达那里。

我实际上会推荐 A* 寻路作为一种值得考虑的技术。您可以通过确定哪些节点可以直接访问哪些其他节点以及来自特定节点的每个跃点的“成本”来进行设置。在这种情况下，看起来每个“跃点”的成本可能相同，因为您的节点看起来间隔相对较近。 A* 可以使用此信息找到任意两点之间的最低成本路径。由于您需要从 A 点到达 B 点并访问其间大约 12 个点，因此即使使用寻路的强力方法也不会造成任何伤害。

只是考虑的替代方案。它看起来确实非常像旅行推销员问题，这些都是值得阅读的好论文，但仔细观察，您会发现它只是让事情变得过于复杂。 ^_^ 这是来自以前处理过此类事情的视频游戏程序员的想法。

回复收藏 0 原文

忆梦 2024-07-14 06:26:05

这不是 TSP 问题，也不是 NP 难题，因为原始问题并不要求必须通过的节点仅被访问一次。通过 Dijkstra 算法编译所有必须通过的节点之间的最短路径列表后，这使得答案变得非常非常简单，只需暴力破解即可。可能有更好的方法，但一个简单的方法就是简单地向后处理二叉树。想象一个节点列表 [start,a,b,c,end]。将简单距离 [start->a->b->c->end] 相加，这就是您要超越的新目标距离。现在尝试 [start->a->c->b->end] ，如果这样更好，请将其设置为目标（并记住它来自该节点模式）。逆向排列：