问题是：在有障碍物的矩形网格上找到多个目标中最接近的一个。只允许向上/向下/向左/向右移动（没有对角线）。我确实看到了这个问题和答案，这个，那个等等。我没有看到任何人使用或建议我的特定方法。我的方法有重大错误吗？
我在这里最重要的限制是，如果你愿意的话，将路径（或任何列表）表示为"堆栈"或"单链表"是非常便宜的。也就是说，恒定时间访问顶部元素，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：随机化矩形网格上可能的下一个瓦片的返回顺序似乎是一种非常廉价的方法，可以在没有障碍物的矩形区域中找到一条不可预测的、相当曲折的路径，而不是沿着两条边走（曲折路径在统计上更可能）。这是正确的吗？
据我所见，它在大O中是正确有效的（N log N，只要启发式是可接受的和一致的，其中N=网格的单元数，假设你使用的是一个优先级队列，其操作在log N中工作）。"之字形"也会起作用。
p.s.对于这类问题，存在一个在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。因此，我们可以通过使用"deque"（或双向链表）而不是普通队列来模拟A*：每当我们遇到权重为0的边时，将其推到队列的前面，每当我们遇到权值为2的边时将其推送到队列的末尾。
因此，该算法模拟A*，并在最坏的情况下在线性时间内工作。