多源和多汇路径规划？

Question

多源和多汇路径规划？

3

我可以帮您翻译成中文。这段内容是关于编程的，讲述了一个最短路径问题需要解决，并且作者相信应该有一种高效的解决方案。接下来是一个图形的 ASCII 表示。

input

. N N N N N N
W 7 9 8 8 7 5 N . . . N N N
W 2 2 2 1 1 6 6 N N N 5 5 N E
W 1 2 3 2 2 2 2 4 5 5 4 2 5 E
. S S S 3 3 3 2 6 5 4 2 2 2 E
. . . . S S 2 2 2 2 3 7 2 2 E
. . . . . . S 2 3 2 7 7 7 7 E
. . . . . . . S 7 7 7 7 7 7 E
. . . . . . . S 7 7 7 S S 7 E
. . . . . . . . S 7 S . . S
. . . . . . . . . S

Output:
35

我需要找到从一个“E”点到一个“W”点的最短路径，沿着编号点行走。我们不能在“N”和“S”点上行走。当我们站在一个点上时，我们能够向上、下、左、右走。我需要找到以我步行的编号方块为衡量标准的最短路径。以下是一个更简单的例子：

我会创建一个双向有向无环图，所有边都指向一个编号的边，该编号作为权重，所有指向 E 或 W 的边的权重为 0：

我的尝试

现在这是一个从多个源到多个汇点寻找最短路径的情况。

我的天真想法是，我可以从每个w运行Dijkstra到每个E。然而，这将以类似于O(W * dijkstra ^ E)（其中E是E节点的数量）的方式运行。

有没有更聪明的方法来执行多源多汇点的Dijkstra算法呢？

- n00bster

是的，所有权重都是正数，我会尝试转换这些数字。 - n00bster

在你的第一个图中，右上角的N和E无法到达任何编号的方块。 - stark

在那种情况下，对于那个E来说，它和任何W之间都没有任何路径。 - n00bster

2

使用松弛的 BFS 算法。将所有 W 放入队列中。当到达一个未被访问过的节点时，分配一个权重并将其添加到队列中。如果一个节点已经被访问过，则检查到该节点的新路径是否具有较低的权重。如果是，则更新权重并将节点添加到队列中。当到达 E 时，如果改进了它的权重，则更新它的权重，但不要将其添加到队列中。继续执行直到队列为空。 - user3386109

我相信在我之前有其他人使用过这个算法，但我不知道他们的名字。所以我恐怕不能告诉你要搜索什么。 - user3386109

显示剩余4条评论

2个回答

1

在评论中提到了一种解决方案，但需要转化为答案：运行普通的BFS，但重新将任何先前访问过的节点加入队列，只要它们可以以比先前预计的更低的成本到达。将新发现的更便宜的路径重新加入已访问节点的队列，让我们重新计算其邻居路径。

缺点是BFS将至少探索所有节点，因此最优性取决于您拥有的图形类型 - 如果它是具有相对于图形尺寸的许多起始和结束点的图形（如您的示例），则这很好，而随着源和汇点数量相对于图形大小的减少，运行多个Dijkstra变得有吸引力。

以下是代码：

const findAllCoords = (G, tgt) => 
  G.reduce((a, row, ri) => {
    const res = row.reduce((a, cell, ci) => 
      cell === tgt ? [...a, [ci, ri]] : a
    , []);
    return res.length ? [...a, ...res] : a;
  }, [])
;

const shortestPathMultiSrcMultiDst = (G, src, dst) => {
  const key = ([x, y]) => `${x} ${y}`;
  const dstCoords = findAllCoords(G, dst);
  const visited = Object.fromEntries(
    dstCoords.map(e => [key(e), Infinity])
  );
  const neighbors = ([x, y]) =>
    [[0, -1], [-1, 0], [1, 0], [0, 1]]
    .map(([xx, yy]) => [x + xx, y + yy])
    .filter(([x, y]) => 
      G[y] && (!isNaN(G[y][x]) || G[y][x] === dst)
    )
  ;
  const q = findAllCoords(G, src).map(e => [e, 0]);
  
  while (q.length) {
    let [xy, cost] = q.shift();
    const [x, y] = xy;
    const k = key(xy);
    cost += isNaN(G[y][x]) ? 0 : +G[y][x];
    
    if (!(k in visited) || cost < visited[k]) {
      visited[k] = cost;
      q.push(...neighbors(xy).map(e => [e, cost]));
    }
  }

  return Math.min(...dstCoords.map(e => visited[key(e)]));
};

const G = `
. N N N N N N
W 7 9 8 8 7 5 N . . . N N N
W 2 2 2 1 1 6 6 N N N 5 5 N E
W 1 2 3 2 2 2 2 4 5 5 4 2 5 E 
. S S S 3 3 3 2 6 5 4 2 2 2 E
. . . . S S 2 2 2 2 3 7 2 2 E
. . . . . . S 2 3 2 7 7 7 7 E
. . . . . . . S 7 7 7 7 7 7 E
. . . . . . . S 7 7 7 S S 7 E
. . . . . . . . S 7 S . . S
. . . . . . . . . S
`.trim().split("\n").map(e => e.split(" "))
;
console.log(shortestPathMultiSrcMultiDst(G, "W", "E"));

我认为共享更好的答案是将问题转化为一个普通的迪杰斯特拉可解图，通过将所有源连接到一个节点和将所有汇连接到一个节点，这样做的效果在我看来基本上是毫无意义的。

- ggorlen

这个问题将使用哪个运行时？O(Enodes*(V+E))？ - n00bster

由于我可能会探索每个节点Enodes次，所以这样做。 - n00bster

我不确定时间复杂度，所以没有加上去，但是你的分析对我来说似乎很直观。我在搜索了几分钟后发现这篇论文提供了最好的解决方案，但我没有时间深入研究。如果我能够巩固我的理解，我会更新的，同时如果你有任何想法，请随意编辑或留下评论。 - ggorlen

ggorlen，我已经添加了自己的答案尝试，我很高兴有更多人来审查它。 - n00bster

是的，你的解决方案看起来好多了。我认为它完全解决了问题，并且始终比这个更优化，所以请随意移动复选标记。 - ggorlen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n00bster · Accepted Answer

经过思考，我认为我已经想出了一个解决方案。接受的答案完全有效和不错，但我认为应该比最坏情况下需要评估每条边E的BFS运行速度更快。

我的解决方案是这样的：我将所有E节点连接到一个源点上，从源点(s)到E有边，权重为0。所有W节点也都连接到一个汇点(t)，从W到汇点有边。

这意味着前面展示的图将如下所示：

现在，我只需从s到t运行一个普通的Dijkstra算法即可。