我有一个可以从使用 A* 中受益的应用程序；但是，由于遗留原因，当有多个最佳路径可供选择时，我需要它继续生成与之前完全相同的路径。
例如，考虑这个迷宫
...X FX.S …… S = 开始 F = 完成 X = 墙 . = 空白空间
方向优先级向上；对; 向下; 左。使用广度优先，我们将找到路径 DLLLU；但是，使用 A*，我们立即向左走，最终找到路径 LULLD。
我尝试过确保在打破关系时始终朝着正确的方向扩展；并在从更重要的方向移动时覆盖PreviousNode指针，但在该示例中均无效。有没有办法做到这一点？
如果原始算法是 BFS，您正在寻找最短路径中的最小路径，其中“最小”是根据Ord边缘上的某些总顺序引起的词典顺序（当然“最短”是根据路径长度）。
amit 建议的调整权重的想法是很自然的，但我认为这不是很实用，因为权重需要具有与路径长度相当的位数以避免丢弃信息，这会使算法慢几个数量级。
值得庆幸的是，这仍然可以通过对 A* 进行两个简单且廉价的修改来完成：
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 个单位的节点，并且重建阶段在属于最短路径的节点数量上是准线性的。如果正如您所暗示的那样，在大多数情况下只有一条最短路径，则影响较小。您甚至可以针对这种特殊情况进行优化，例如通过ancestor在经典情况中记住一个节点，当有多个祖先时（即 when path_length[y] == path_length_through_x），您将其设置为一个特殊的错误值。ancestor搜索循环结束后，您将尝试像经典 A* 中那样检索路径；如果在构建路径时遇到错误值，您只需要执行完整路径重建。
我会将路径顺序的偏好直接构建到启发式函数中
我会先看看面包优先算法
为面包优先算法选择的每条路径定义一个函数：
考虑我们正在运行一个深度优先算法，并且它在第 n 个深度上由算法先前完成的决定： x_i \in {U,R,D,L} assign U=0,R=1,D=2, L=3
然后定义：
g(x_1,..,x_n) = sum_{i=1}^n x_i * (1/4)^i
当算法访问比这一个更深的节点时，让我们在每一步将这一步的 g 值固定为 g'，g() 函数会更大。
在未来的每一步中，当 {1..n} x_i 的 on 发生变化时，它会更大，因此 g 函数确实在运行深度优先时总是会升高。
注意：如果深度优先算法成功，它会选择 g() 值最小的路径
注意：g() < 1 因为 max(L,R,U,D)=3
将 g 添加到 A* 的启发式函数不会干扰最短路径长度，因为 min edge length>=1
像这样修改的 A* 将找到的第一个解决方案将是深度优先找到的解决方案
为你举例：
h_bread=g(DLLLU) = (23330)_4 * c
h_astar=g(LULLD) = (30332)_4 * c
()_4 是 base4 c 是一个常数 (4^{-5})
例如：h_bread < h_astar
我想出了两种方法来做到这一点。两者都需要继续算法，而队列顶部的距离到开始 g-value <= g(end-node)。由于 A* 中使用的启发式是admissable，这保证了属于某个最佳路径的每个节点最终都会被扩展。
第一种方法是，当我们遇到冲突时（即，我们发现两个具有相同 f 值的节点可能都是沿最佳路径的某个节点的父节点），我们通过回溯到第一个点来解决它沿着他们相遇的路径（我们可以在 中轻松做到这一点O(path-length)）。然后，我们只需检查两条路径的方向优先级，然后选择在 BFS 搜索中具有更高优先级的路径。
第二种方法仅适用于每个节点接触水平和垂直（可能对角）相邻节点的网格（即 4 连接网格图）。我们做和以前一样的事情，但不是回溯来解决冲突，我们从一开始就比较沿路径的节点，并找到它们不同的第一个地方。它们的第一个不同之处将是与以前相同的关键节点，我们可以从中检查方向优先级。
我们通过为每个节点存储迄今为止的最佳路径来做到这一点。通常这会很麻烦，但由于我们有一个 4 连通图，我们可以通过存储沿路径采取的每个方向来非常有效地做到这一点。这将只需要每个节点 2 位。因此，我们基本上可以使用整数对路径进行编码——使用 32 位寄存器，我们可以一次比较 16 个节点；32个节点，64位寄存器；和 64 个（！）节点一次使用 128 位寄存器（如 x86 和 x64 处理器中的 SSE 寄存器），即使对于具有 100 个节点的路径，这种搜索也非常便宜。
我实现了这两个，以及@generic human 的算法，以测试速度。在一个有 400 个塔的 50x50 网格上，
因此，由于我的应用程序使用 4 连通图，因此整数编码算法似乎最适合我。
我已经复制了一封写给这里教授的电子邮件。它包括对算法的更详细描述，以及它们工作的证明草图。
一般来说，没有重要的方法可以做到这一点：
广度优先搜索找到由考虑顶点的顺序确定的最低顺序的最短路径。在断开等长路径之间的联系时，此顺序必须优先于任何其他因素。
示例：如果按照 A、B、C 的顺序考虑节点，则Node A < Node C. 因此，如果在以 A 开头的最短路径和以 C 开头的最短路径之间存在联系，则将找到以 A 开头的最短路径。
另一方面，A* 搜索将找到由节点的启发式值确定的最低阶最短路径。因此，启发式必须考虑到每个节点的最低词典路径。找到它的唯一方法是 BFS。