我有一个应用程序，使用A*算法会使它受益匪浅；然而由于历史原因，当出现多条最佳路径时，我需要它继续生成完全相同的路径。
例如，考虑这个迷宫：
...X FX.S ....
S = 起点 F = 终点 X = 墙 . = 空地
假定我们按照上、右、下、左的方向优先级来寻路，在广度优先算法中，我们将找到路径DLLLU；然而，在使用A*算法时，我们会立即朝左移动，并最终找到路径LULLD。
我尝试过在选择方向时始终展开正确的方向，以及在从较重要的方向移动时覆盖PreviousNode指针，但在该示例中均不起作用。是否有一种方法可以解决这个问题？
Ord引起的词典顺序（当然，“最短”是按照路径长度）。调整权重的想法是自然的，但我认为这不是很实用，因为权重需要具有与路径长度可比的位数，以避免丢弃信息，这将使算法变得慢得多。幸运的是，这仍然可以通过对A*进行两个简单而廉价的修改来完成：start到goal的字典顺序最小路径，这是所需的解决方案。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个单位的节点，并且重构阶段在属于最短路径的节点数几乎线性。如果像你所暗示的那样，在大多数情况下只有一条最短路径，则影响更小。甚至可以针对这种特殊情况进行优化，例如通过记住一个祖先节点（如经典情况），当存在多个祖先时（即当path_length[y] == path_length_through_x 时）将其设置为特殊错误值。一旦搜索循环结束，您尝试通过ancestor检索路径，就像经典A*一样；仅在构建路径时遇到错误值时才需要执行完整的路径重构。
n中呈指数增长，但属于最佳路径的节点数量是线性的。 - BlueRaja - Danny Pflughoeft我会将路径顺序的偏好直接建立在启发式函数中。
我会首先查看广度优先算法。
为广度优先算法选择的每条路径定义一个函数：
假设我们正在运行深度优先算法，并且它在第n层。算法之前所做的决策为：x_i \in {U,R,D,L}，其中U=0，R=1，D=2，L=3。
然后定义：
g(x_1,..,x_n) = sum_{i=1}^n x_i * (1/4)^i
h_bread=g(DLLLU) = (23330)_4 * c
h_astar=g(LULLD) = (30332)_4 * c
()_4是基于4进制的 c是一个常数（4^{-5}）
以您的例子为例：h_bread < h_astar
我实现了这两个算法，以及@generic human的算法，来测试速度。在一个50x50的网格上有400个塔。
因此，由于我的应用程序使用4连通图，似乎整数编码算法对我最好。
我复制了一封我写给教授的电子邮件在这里。它包括更详细的算法描述，以及证明它们有效性的草图。
一般来说，没有非平凡的方法可以做到这一点：
广度优先搜索找到的是按照顶点被考虑的顺序确定的最低阶路径。当在等长路径之间进行抉择时，这个顺序必须优先考虑于其他任何因素。
例如：如果节点按照A、B、C的顺序被考虑，则节点A < 节点C。因此，如果有一个以A开头的最短路径和一个以C开头的最短路径之间存在抉择，那么将选择以A开头的路径。
另一方面，A*搜索将找到由节点的启发式值确定的最低阶路径。因此，启发式函数必须考虑到每个节点的最低词典路径。而找到这个路径的唯一方法就是BFS。
h(v)在[0,1]范围内，A将会像BFS一样运行，除了最后一步... - amitw(u,v) = 1 + f(u)*prio(u,v)，其中：(1) 所有边的加权总和不超过1。(2)f(u)是基于源点到目标点的距离（可能是启发式的？）计算出来的，并且单调递减，这样每个 f(u) 都比在最短路径中跟随它的所有节点“更重要”[可能具有 Zeno 性质并呈指数衰减]。然而，我无法想出一种证明它有效的方法，并且还怀疑它可能会漏掉一些细节。 - amit