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

StackOverflow https://stackoverflow.com/questions/222413

  •  03-07-2019
  •  | 
  •  

题

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

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

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

有帮助吗？

解决方案

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

在你的情况下，鉴于你只有十几个被标记为'mustpass'，并且给出了12个！相当小（479001600），你可以简单地尝试只有'mustpass'节点的所有排列，并查看从'start'到'end'的最短路径，它按顺序访问'mustpass'节点 - 它只是是该列表中每两个连续节点之间最短路径的串联。

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

这样的事情：

//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 3 ），对于所有排列部分是O（k！n），并且100 ^ 3 +（12！）（100）实际上是花生，除非你有一些非常严格的约束。]

其他提示

运行 Djikstra算法，找到所有关键节点之间的最短路径（开始，结束） ，并且必须通过），然后深度优先遍历应该告诉你通过结果子图的最短路径接触所有节点开始...必须...结束

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

原因在于，与旅行商问题不同，玉米迷宫不允许您直接从地图上的任何一个点移动到任何其他点，而无需通过其他节点到达那里。

我实际上建议将A *寻路作为一种技巧来考虑。您可以通过确定哪些节点可以直接访问哪些其他节点以及“成本”是什么来进行设置。来自特定节点的每一跳的数据是。在这种情况下，看起来每个“跳”都是“跳”。可能是相同的成本，因为你的节点似乎相对密集。 A *可以使用此信息查找任意两点之间的最低成本路径。由于你需要从A点到达B点并且访问中间约12个，所以即使是使用寻路的蛮力方法也不会有任何伤害。

只是另类考虑。它确实看起来非常像旅行推销员的问题，这些都是很好的论文，但仔细观察，你会发现它只是过于复杂的事情。 ^ _ ^这来自视频游戏程序员的头脑，他之前处理过这类事情。

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

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

一旦你有了这个新的图表，你就会遇到旅行销售人员的问题（好吧，几乎......不需要回到你的起点）。上述任何与此相关的帖子都将适用。

Andrew Top有正确的想法：

1）Djikstra的算法 2）一些TSP启发式。

我推荐Lin-Kernighan启发式：它是任何NP Complete问题中最着名的之一。唯一要记住的是，在第2步之后再次展开图形后，你可能在扩展路径中有循环，所以你应该绕过那些（看看你路径上的顶点的程度）。

我实际上不确定这个解决方案相对于最佳解决方案有多好。可能存在一些与短路有关的病理情况。毕竟，这个问题看起来很像Steiner Tree： http://en.wikipedia.org/wiki/Steiner_tree 你绝对不能通过收缩图表和运行Kruskal来近似Steiner Tree。

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

  • [开始->a->b->c->结束]
  • [开始->a->c->b->结束]
  • [开始->b->a->c->结束]
  • [开始->b->c->a->结束]
  • [开始->c->a->b->结束]
  • [开始->c->b->a->结束]

其中之一将是最短的。

（“多次访问”节点在哪里（如果有的话）？它们只是隐藏在最短路径初始化步骤中。a 和 b 之间的最短路径可能包含 c 甚至终点。你不需要关心）

考虑到节点和边缘的数量相对有限，您可以计算每个可能的路径并采用最短的路径。

通常这称为旅行商问题，并且无论您使用何种算法，都具有非确定性多项式运行时。

http://en.wikipedia.org/wiki/Traveling_salesman_problem

如何在十几个'必须访问'节点上使用暴力。您可以轻松地覆盖12个节点的所有可能组合，这样您就可以使用最佳电路来覆盖它们。

现在你的问题被简化为找到从起始节点到电路的最佳路线，然后你可以跟随它直到你覆盖它们，然后找到从那个到最后的路线。

最终路径由：

组成

开始 - ＆gt;电路路径* - ＆gt;必须访问节点的电路 - ＆gt;结束路径* - ＆gt;端

你找到我用*标记的路径

从起始节点到电路上的每个点进行A *搜索 对于每一个，从电路上的下一个和上一个节点到结尾进行A *搜索（因为你可以沿着任一方向的电路循环） 您最终得到的是很多搜索路径，您可以选择成本最低的路径。

通过缓存搜索有很多优化空间，但我认为这将产生良好的解决方案。

尽管如此，它并没有找到最佳解决方案，因为这可能涉及将必须访问电路留在搜索范围内。

在任何地方都没有提到的一件事是，在路径中是否可以多次访问同一个顶点。这里的大多数答案都假设可以多次访问同一个边缘，但我的问题是给出了一个问题（路径不应该多次访问同一个顶点！）是它不 ok两次访问同一个顶点。

因此，蛮力方法仍然适用，但是当您尝试计算路径的每个子集时，您必须删除已经使用过的顶点。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top