Blu*_*eft 10 algorithm graph a-star path-finding
我有一个应用程序将受益于使用A*; 但是,由于遗留原因,我需要它继续生成与之前有多个最佳路径可供选择的路径完全相同的路径.
例如,考虑这个迷宫
...X FX.S .... S = start F = finish X = wall . = empty space
方向优先级Up; 对; 下; 离开了.使用广度优先,我们将找到路径DLLLU; 然而,使用A*我们立即离开,最终找到路径LULLD.
我一直试着确保在打破领带时始终朝着正确的方向扩展; PreviousNode从更重要的方向移动时覆盖指针,但在该示例中都不起作用.有没有办法做到这一点？
如果原始算法是BFS,那么您正在寻找最小的最短路径,其中"最小"是根据Ord边缘上某些总顺序引起的词典顺序(当然"最短"是根据路径长度).
由amit建议调整权重的想法是很自然的,但我认为这不是很实用,因为权重需要具有与路径长度相当的位数以避免丢弃信息,这将使得算法数量级更慢.
值得庆幸的是,仍然可以通过对A*的两个简单且廉价的修改来完成:
start,以goal在该DAG,这是需要的解决方案.原理上,经典的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经典案例中的节点,当存在多个祖先(即何时path_length[y] == path_length_through_x)时,您将其设置为特殊错误值.搜索循环结束后,您将尝试检索ancestor经典A*中的路径; 如果在构建路径时遇到错误值,则只需要执行完整路径重建.
我想出了两种方法来做到这一点。两者都需要在队列顶部的距离开始 g 值 <= g(end-node) 时继续算法。由于 A* 中使用的启发式是可接受的，这保证了属于某个最佳路径的每个节点最终都会被扩展。
第一种方法是，当我们遇到冲突时（即，我们发现两个具有相同 f 值的节点，可能都是最佳路径上某个节点的父节点），我们通过回溯到第一个点来解决它沿着他们相遇的路径（我们可以在 中轻松做到这一点O(path-length)）。然后，我们只需检查两条路径的方向优先级，并选择在 BFS 搜索中具有更高优先级的路径。
第二种方法仅适用于每个节点接触水平和垂直（可能还有对角线）相邻节点的网格（即 4 个连接的网格图）。我们做与以前相同的事情，但我们不是回溯来解决冲突，而是从头开始比较路径上的节点，并找到它们第一个不同的地方。它们的第一个不同之处是与之前相同的关键节点，我们可以从中检查方向优先级。
我们通过存储每个节点迄今为止的最佳路径来做到这一点。通常这会很麻烦，但由于我们有一个 4 连通图，我们可以通过存储沿着路径的每个方向来非常有效地做到这一点。每个节点只需要 2 位。因此，我们本质上可以使用整数对路径进行编码——使用 32 位寄存器，我们可以一次比较 16 个节点；32个节点，64位寄存器；并且一次有 64(!) 个节点，具有 128 位寄存器（如 x86 和 x64 处理器中的 SSE 寄存器），使得即使对于具有 100 个节点的路径而言，这种搜索也非常便宜。
我实现了这两个以及@generic human 的算法来测试速度。在有 400 个塔的 50x50 网格上，
因此，由于我的应用程序使用 4 连通图，因此整数编码算法似乎最适合我。
我复制了我写给这里一位教授的电子邮件。它包括对算法的更详细描述，以及它们工作的证明草图。