algorithm - 有没有办法保持 A* 中的方向优先级？ (即生成与广度优先相同的路径)

Question

我有一个可以从使用 A* 中获益的应用程序；但是，由于遗留原因，我需要它继续生成完全与之前有多个最佳路径可供选择时相同的路径。

例如，考虑这个迷宫

...XFX.S....S = startF = finishX = wall. = empty space

方向优先向上；正确的;向下;左。使用广度优先，我们将找到路径 DLLLU；然而，使用 A* 我们立即向左走，最终找到路径 LULLD。

我尝试确保在打破平局时始终朝着正确的方向扩张；并在从更重要的方向移动时覆盖 PreviousNode 指针，但在该示例中都不起作用。有办法做到这一点吗？

Answer 1

如果原始算法是 BFS，您正在寻找最短路径中的最小路径，其中“最小”是根据边上的一些总顺序 Ord 引起的词典顺序(当然还有“最短”是根据路径长度)。

amit 提出的调整权重的想法很自然，但我认为它不太实用，因为权重需要具有与路径长度相当的位数，以避免丢弃信息，这会使算法慢几个数量级。

值得庆幸的是，这仍然可以通过对 A* 进行两个简单且廉价的修改来完成:

1. 一旦达到目标，我们就应该继续访问节点直到路径长度增加，而不是返回到目标的任意最短路径，这样我们就可以访问属于最短路径的所有节点。
2. 在重建路径时，我们构建了构成最短路径的节点集。这个集合在考虑所有最短路径边时有一个 DAG 结构，现在很容易在这个 DAG 中找到从 start 到 goal 的词典编纂最小路径，这是期望的解决方案。

从示意图上看，经典 A* 是:

path_length = infinity for every node
path_length[start] = 0

while score(goal) > minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x
            ancestor[y] = x

return [..., ancestor[ancestor[goal]], ancestor[goal], goal]

其中 score(x) 代表 path_length[x] + heuristic(x, goal)。

我们简单地将严格的while循环不等式转化为非严格的不等式并添加一个路径重构阶段:

path_length = infinity for every node
path_length[start] = 0

while score(goal) >= minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x

optimal_nodes = [goal]
for every x in optimal_nodes:  // note: we dynamically add nodes in the loop
    for y in neighbors of x not in optimal_nodes:
        if path_length[x] == path_length[y] + d(x,y):
            add y to optimal_nodes

path = [start]
x = start
while x != goal:
    z = undefined
    for y in neighbors of x that are in optimal_nodes:
        if path_length[y] == path_length[x] + d(x,y):
            z = y if (x,y) is smaller than (x,z) according to Ord
    x = z
    append x to path

return path

警告:引用 Knuth 的话，我只是证明了它是正确的，并没有尝试过。

至于对性能的影响，它应该是最小的:搜索循环只访问得分比经典 A* 高 1 个单位的节点，并且重建阶段在属于 a* 的节点数量上是准线性的最短的路径。如果正如您所暗示的那样，在大多数情况下只有一条最短路径，那么影响会更小。您甚至可以针对这种特殊情况进行优化，例如通过记住经典案例中的 ancestor 节点，当有多个祖先时(即，当 path_length[y] == path_length_through_x)。搜索循环结束后，您将尝试像在经典 A* 中一样通过 ancestor 检索路径；如果在构建路径时遇到错误值，则只需执行完整路径重构。