algorithm - 扭曲网格中的最短路径

Question

我正在尝试解决基于图形的问题，这是声明:我必须找到从标记位置 (s) 到标记位置 (S) 的最短路线 [注意 : 我标记 S 和 E 只是为了便于理解]。这是一个问题，我只能通过标记为 0 的单元格，而标记为 1 的单元格表示无法通过的墙。我也可以选择只移除一堵墙，如果它能给我一条更短的导出路线。 只能在主要方向上移动；不允许对角移动。

示例二维网格:

[
    [0(S) 1  1  1  1   ], 
    [0    0  1  1  1   ],
    [1    0  1  0  1   ],
    [1    1  0  0  0(E)],
]

如果没有移除墙壁的选项，我可以简单地使用Bfs 或Dijkstra 来找到最短路线。这个问题已被问到这里: here - 他们简单地使用完全穷举搜索，这对大型矩阵来说非常糟糕，他们专注于基于语言的优化，这不是解决问题的好方法。

Someone asked it here - 接受的答案有以下方法:

• 从 jail 门口开始进行广度优先搜索，以找到每个可通行空间距 jail 门的距离。

• 从逃生舱开始运行另一个广度优先搜索，找到每个可通行空间与逃生舱的距离。

• 现在遍历墙壁，并考虑依次移除每堵墙。你知道每个可通行空间离 jail 门的距离和逃生舱，所以你可以立即算出穿过墙留下的空间的最短路线
  你刚刚删除了。

但我不清楚这是什么意思(所以你可以立即计算出穿过墙留下的空间的最短路径的长度)在上面第3步。

还有没有更好的方法来处理它？

完全不用图，用动态规划能解决吗？

Answer 1

我会按如下方式稍微扩充图:构建一个新图 G'，它是初始图 G 的两倍。 G'的每个节点代表一个状态(v, rem) 其中v是G的一个节点，rem\in {0, 1} 表示您是否已经删除了一个节点。同时添加一个额外的节点 E_new

G'中的邻接如下:

• 所有 (v, 0)(resp. (v, 1))就像在 G 中一样相互链接(如果它们都具有值 0)。
• 如果 v1 的值为 0 而它的一个邻居 v2 的值为 1，则在 (v1, 0) 和 (v2, 1) 之间添加一条边
>
• (E, 0) 和 (E, 1) 都以 0 的成本链接到 E_new。(如果您不使用成本只需将长度减 1)。

您现在的目标是从 (s, 0) 到 E_new，Dijkstra(如果所有步骤的成本相同，那么 BFS 在您的情况下)应该可以正常工作时间最多 O(n) 其中 n 是您的节点数(不是正方形的边)。 A* 会更快，但实现起来有点棘手。如果您希望不移除墙壁的解决方案成为首选(等长)，则必须注意执行 BFS 的顺序(首先是 rem=0 的节点)。

这与 Shortest path in matrix with obstacles with cheat paths 非常相似(实际上是一个实例) .

编辑:您在上面建议的答案具有相同的复杂性，需要 2 个 BFS 而不是 1 个，但在图表上小两倍，所以可能相似，再加上另一个循环，所以我不知道哪个更快。

(so you can immediately work out the length of the shortest route that passes through the space left by the wall )

在第 1 步和第 2 步中，您一方面计算了源和每堵墙之间的最排序路径，另一方面计算了导出和所有墙之间的最排序路径，而不穿过任何墙。通过为给定的墙节点添加这两个值，您可以获得仅穿过该墙的从 s 到 e 的路径长度。通过遍历所有的墙(或者至少是其中的一部分，如果你聪明的话)，你会得到最短的这样的路径，你可以将它与最短的(s，e)路径进行比较而不穿过任何墙，只保留最好的。

编辑 2

这是我的方法的一个小例子:假设你的网格是这样的:

[[0, 0, 1],
 [0, 1, 0]]

其中的节点可以用坐标(1, 1), (1, 2)等来表示。唯一存在的边是 (1, 1) 到 (1, 2) 和 (1, 1) 到 (2, 1)，以及 (3, 1) 和 (2, 2) 到 (3, 2)。向每个节点添加一个第三维 rem，可以取值 0 或 1。对于 rem 的每个值，如果 (i1, j1)->(i2, j2) 在图中，您现在有 (i1, j1, rem )->(i2, j2, rem)。对于所有不在图中(因为墙壁)的边 (i1, j1)->(i2, j2)，您现在有 (i1, j1, 0)->(i2, j2, 1)。另外，最后，(2, 3, 0)->E_new 和 (2, 3, 1)->E_new。您可以在此新图中运行 BFS。