首页 文章

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

提问于
浏览 次
68

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

我需要找到通过此图表的最短路径，该路径从'start'开始，结束于'end'， and passes through all of the 'mustpass' nodes (in any order).

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

algorithm graph-theory

10 回答

  • 3

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

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

    换句话说，首先找到每对顶点之间的最短距离（你可以使用Dijkstra的算法或其他算法，但是那些小数字（100个节点），即使是最简单的代码Floyd-Warshall algorithm也会及时运行） . 然后，一旦你在表中有这个，尝试你的'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 'mustpass'节点，它的运行时间是Floyd-Warshall部分的O（n3），所有排列部分的运行时间是O（k！n），100 ^ 3（12！）（100）实际上是花生，除非你有一些非常严格的约束 . ]

    回复于
  • 14

    运行Djikstra's Algorithm以找到所有关键节点（开始，结束和必须通过）之间的最短路径，然后深度优先遍历应该告诉您通过触发所有节点的结果子图的最短路径开始...必须......结束

    回复于
  • 2

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

    这样做的原因是，与旅行商问题不同，玉米迷宫不允许您直接从任何一个点旅行到 Map 上的任何其他点，而无需通过其他节点到达那里 .

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

    只是另一种考虑因素 . 它确实看起来非常像旅行推销员的问题，这些都是很好的论文，但是看得更近，你之前已经处理过这类事情了 .

    回复于
  • 3

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

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

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

    回复于
  • 14

    Andrew Top有正确的想法：

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

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

    我实际上不确定这个解决方案相对于最佳解决方案有多好 . 可能存在一些与短路有关的病理情况 . 毕竟，这个问题看起来很像Steiner Tree：http://en.wikipedia.org/wiki/Steiner_tree，你绝对可以't approximate Steiner Tree by just contracting your graph and running Kruskal'例如 .

    回复于
  • 5

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

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

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

    回复于
  • 0

    这不是TSP问题而不是NP-hard，因为原始问题不要求必须访问必须通过的节点一次 . 通过Dijkstra 's algorithm. There may be a better way to go but a simple one would be to simply work a binary tree backwards. Imagine a list of nodes [start,a,b,c,end]. Sum the simple distances [start->a->b->c->end] this is your new target distance to beat. Now try [start->a->c->b->end] and if that'更好地设置作为目标（并记住它来自节点模式），在编译所有必须通过节点之间的最短路径列表之后，这使得答案变得更加简单，更加简单 . 通过排列向后工作：

    • [start-> a-> b-> c-> end]

    • [start-> a-> c-> b-> end]

    • [start-> b-> a-> c-> end]

    • [start-> b-> c-> a-> end]

    • [start-> c-> a-> b-> end]

    • [start-> c-> b-> a-> end]

    其中一个将是最短的 .

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

    回复于
  • 68

    如果algorythm应该在大约一秒钟，一天，一周左右的时间内运行，那将会很高兴:)如果一周没问题且它是一次性的，你可以在几个小时内编写一个软件并蛮力 . 但如果它嵌入在用户界面中并且必须每天计算很多次......我认为是另一个问题 .

    回复于
  • 0

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

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

    最终路径包括：

    开始 - >电路路径* - >必须访问节点的电路 - >结束路径* - >结束

    你会发现我用*标记的路径

    从起始节点到电路上的每个点进行A *搜索，从电路上的下一个节点到最后一个节点进行A *搜索（因为你可以沿着任一方向的电路循环）你是什么人最终会有很多搜索路径，您可以选择成本最低的路径 .

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

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

    回复于
  • 23

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

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

    回复于

相关问题