两条路径的最短交点

Question

解释：

在上面的示例图片中，有一个绿色圆圈跟随任意路径。

我希望红色圆圈以尽可能少的步骤与绿色圆圈相交，如图所示。

圆圈可以一步移动到8个相邻格子中的任何一个，黑色格子不能穿过。

路径表示为坐标列表。在这种情况下，绿色路径是 [(0,3),(0,2),(0,1)...(5,0)].

为了找到最短的交汇点，我可以遍历绿色路径列表中的每个坐标，并使用 A* 算法找到从红色圆圈到该坐标的最短路径。如果返回的路径长度等于绿色圆圈到达该坐标所需的步数，则找到最短的会合点路径。

这当然是一种蛮力方法，java 代码看起来像这样：

List<Coord> minMeetingPointPath(Coord redLoc, List<Coord> greenPath) {
    for (int step = 0; step < greenPath.size(); step++) {
        Coord greenLoc = greenPath.get(step);
        List<Coord> redPath = shortestPathAStar(redLoc, greenLoc);
        if (redPath.size() == step)
            return redPath;
    }
    return null;
}

问题

所以我的问题是：

是否有更有效的方法来解决这个问题而不使用蛮力方法？

Answer 1

我有 2 种方法可以提高效率

1) 从目标开始。从绿球开始。查找（并跟踪）从绿色节点位置到红色节点位置的最短路径。这本身不会减少搜索，但是如果您将搜索深度限制为移动数（即移动 0 搜索到深度 0 移动 1 搜索到深度 1 ... 移动 n 搜索到深度 n ) 它会减少你搜索的时间，因为你只会搜索到相关的深度，超过那个点的任何东西都没有价值，不需要检查。

2) 如果不需要，根本不要搜索。给你的搜索一个深度降神会，你已经有了每个节点的开始和结束的 x，y 位置，所以在你做你的 A* 搜索之前检查移动数和直线距离例如：0,5（绿色当前位置）和 0,0（红色起始位置）之间的最短距离是 5 所以如果绿色物体移动是移动 4 或更少，你知道没有办法到达那里，即使没有什么挡路的。但是，如果它移动了 5 步或更多，您知道可能有一种方法可以及时到达该位置，因此值得搜索以查看路径实际需要多长时间。

两条路径的最短交点

Shortest meeting point of two paths

language-agnostic

shortest-path

path-finding

解释：

问题