algorithm - 修改 A* 以在矩形网格上找到最接近多个目标的路径

Question

问题:在有障碍物的矩形网格上找到多个目标中最近的路径。只允许向上/向下/向左/向右移动(没有对角线)。我确实看到了this question and answers , and this , and that ，等等。我没有看到任何人使用或建议我的特定方法。我的方法是否存在重大错误？

我在这里最重要的约束是，如果需要，将路径(或任何列表)表示为“堆栈”或“单链表”对我来说非常便宜。也就是说，恒定时间访问顶部元素，O(n) 用于反转。

(对我而言)显而易见的解决方案是使用曼哈顿距离启发法搜索从任何目标到起点的路径。从目标到起点的第一条路径将是到最近目标的最短路径(可能是许多路径中的一个)，并且我不需要在遵循它之前反转路径(它将以“正确”顺序，起点在上，目标在末尾)。

在伪代码中:

A*(start, goals) :
    init_priority_queue(start, goals, p_queue)
    return path(start, p_queue)

init_priority_queue(start, goals, q_queue) :
    for (g in goals) :
        h = manhattan_distance(start, g)
        insert(h, g, q_queue)

path(start, p_queue) :
    h, path = extract_min(q_queue)
    if (top(path) == start) :
        return path
    else :
        expand(start, path, q_queue)
        return path(start, q_queue)

expand(start, path, q_queue) :
    this = top(path)
    for (n in next(this)) :
        h = mahnattan_distance(start, n)
        new_path = push(n, path)
        insert(h, new_path, p_queue)

对我来说，以这种方式反向搜索似乎是很自然的。这里有想法吗？

还有一个问题:假设我的优先级队列在具有相同优先级的元素上是稳定的(如果两个元素具有相同的优先级，则较晚插入的会较早出来)。我故意未定义上面的 next:随机化返回矩形网格上可能的下一个图 block 的顺序似乎是一种非常便宜的方法，可以通过矩形找到一条不可预测的、相当曲折的路径没有障碍物的区域，而不是沿着两个边缘(锯齿形路径在统计上更有可能)。对吗？

Answer 1

据我所知，它在大 O 中是正确且高效的(N log N，只要启发式是可接受且一致的，其中 N = 网格的单元数，假设您使用其操作有效的优先级队列在日志 N)。之字形也可以。

附注对于这类问题，有一个效率更高的“优先级队列”可以在 O(1) 中运行。我所说的这类问题是指每对节点之间的有效距离是一个非常小的常数(在这个问题中为 3)的情况。

编辑:根据评论中的要求，这里是针对此问题的恒定时间“优先队列”的详细信息。

首先，将图转换为下图:设图中节点(即网格中的单元格)的势为节点到目标(即启发式)的曼哈顿距离。我们称节点 i 的势为 P(i)。之前，相邻单元格之间有一条边，其权重为 1。在修改后的图中，权重 w(i, j) 变为 w(i, j) - P(i) + P(j)。这与在启发式可接受且一致的情况下为什么 A* 是最优的并在多项式时间内终止的证明完全相同。请注意，此问题的曼哈顿距离启发式算法是可接受且一致的。

第一个关键观察是原始图中的 A* 与修改后的图中的 Dijkstra 完全相同。这是因为修改后的图中节点 i 的“值”恰好是与原始节点的距离加上 P(i)。第二个关键观察是我们转换后的图中每条边的权重要么是 0 要么是 2。因此，我们可以通过使用“双端队列”(或双向链表)而不是普通队列来模拟 A*:每当我们遇到权重为 0 的边，将其推到队列的前面，每当我们遇到权重为 2 的边时，将其推到队列的末尾。

因此，该算法模拟A*，在最坏情况下以线性时间运行。