在给定源节点、目标节点和中间节点的情况下，如何检测最短曼哈顿距离是否被阻塞？

Question

在给定源节点、目标节点和中间节点的情况下，如何检测最短曼哈顿距离是否被阻塞？

5

这是我本来想发的完整标题，但它实际上太长了：

给定源节点、目标节点和中间节点，如何检测最短曼哈顿距离是否被中间节点阻塞？

我画了一张图来更清晰地说明问题。左边的图中，“u”是源节点，“v”是目标节点。标有1到6的节点是中间节点。从u到v的最短曼哈顿距离为12，但中间节点组成了一个墙，阻挡了它。右边的图中，u'是源节点，v'是目标节点，显示中间节点1到5不会阻碍从u'到v'的最短曼哈顿距离。

我正在尝试找到一种算法，不需要实际进行图形搜索（例如BFS），因为u和v之间的距离可能非常大。

- Josh Kearns

在你的左图中，从u到v的所有路径都被阻塞了吗？我认为你需要进行某种搜索来发现这一点。 - Ted Hopp

@TedHopp 是的，我已经在描述中提到了（就在它下面）。 - Josh Kearns

你提到最短路径被阻塞了；至少对我来说，不清楚所有路径都被阻塞了。 - Ted Hopp

@Ted，没有唯一的最短路径，而是有一个唯一的最短距离（在这种情况下为12），但所有具有此距离的可能路径都需要经过其中一个中间节点。 - Dunaril

2个回答

0

这是我的想法：

我将描述目标在源的右上方的情况，对于其他情况，进行旋转。（对于节点具有相同x/y坐标的简单情况，只需检查它们之间是否有阻塞节点）

取一个矩阵，源和目标在角落里。现在，一列一列地从左到右，在列内从下到上，标记阻塞节点。如果任何以下情况之一成立，则节点B被视为阻塞：

B是中间节点
位于B左侧和下方的节点都是阻塞（根据处理顺序，两者已经被检查过），或者超出了矩阵的边界

最后，如果目标被阻塞，则没有自由的最短路径。

所需时间为O(m*n)，其中m、n是矩阵边长。因此，当您只有几个中间节点时，templatetypedef的解决方案可能更合适。

编辑：之前有点错了，现在希望没有漏掉什么

- voidengine

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

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

- templatetypedef · Accepted Answer

如果你只想检测最短路径（由沿着正确方向单调移动的步骤组成）是否被阻塞，那么你需要检查阻塞节点是否将起点和终点所形成的矩形分成两个不连通的区域。如果从起点到终点没有最短路径，则每条路径必须有一些被阻塞的点。

假设简单起见，你的起点在目标点下方且左侧。在这种情况下，在O(n)时间内找到包含起点和终点的边界框中的所有障碍点。现在，你需要看看是否存在一些节点子集将矩形分为两部分，其中一个包含左下角，另一个包含右上角。当且仅当从左侧到右侧、从左侧到底部、从顶部到右侧或从顶部到底部有一条路径时，才可能出现这种情况。因此，我们只需要检查这些是否可能发生。

幸运的是，这可以通过将问题建模为图搜索来高效地完成，该图的大小为O(n)，其中n是阻塞点的数量，与边界框的大小无关。也就是说，无论测试点之间有多远，搜索图的大小仅取决于阻塞点的数量。

你要构建的图有两个部分。首先，构建一个图，其中每个阻塞点都连接到其周围3x3正方形中的每个其他阻塞点。这些边将可能是同一障碍物的阻塞点链接在一起，因为从源到目标的任何路径都不能穿过通过边缘相连的两个阻塞点之间。现在，添加四个新节点，表示顶部墙、左侧墙、右侧墙和底部墙，并将它们连接到与适当墙壁相邻的每个节点。例如，从左侧墙节点到右侧墙节点的路径表示一系列阻塞节点，使得无法从左下节点到达右上节点。

该图的大小为O(n)，其中n是阻塞节点的数量，因为有O(n)个节点，每个节点最多可以有12条边-每个邻居各一条，潜在地每个墙壁各一条。你可以在最坏情况下用二次时间构造它，通过扫描每个节点，并检查它是否相邻来处理每个其他节点。可能有更好的方法，但我暂时想不到。

现在您有了这个图，对于每一对墙壁，在连接它们会断开图形的情况下，在这个图形中运行一个图形搜索。如果存在路径，则报告最短路径被阻塞。如果不存在，则报告某些最短路径未被阻塞。这些搜索可以使用简单的DFS完成，或者由于您正在运行多个搜索并且只想知道它们是否连接，因此仅需使用强连通组件算法一次，并检查任何重要节点对是否在同一个SCC中。无论哪种方法，时间复杂度为O(n)。

因此，解决此问题的时间最多为O(n^2)，瓶颈是构建图所需的时间。

希望这能帮到您！