标准 A* 在最终平台上的平局打破策略下的扩展计数

在 A* 搜索算法中，对于具有相同 $f$ 值的节点，平局打破策略决定了 A* 在最终 $f$ 层上扩展哪些状态。对于九种标准平局打破策略，我们证明，在一致启发式下，每一对策略都存在正代价实例，使其中任一策略相对于另一策略具有任意大的加性扩展差距。一个参数化的单位代价网格示例还给出了低 $h$ 结合 FIFO 与 LIFO 之间无界的扩展计数比。在非目标状态满足 $h > 0$ 的单位代价搜索中，目标附近的精确启发式值会导致互补的极值结果：在完美区域内的共同配置中，低 $h$ 最小化剩余扩展次数；而当最终平台上每个满足 $h=1$ 的状态都是目标前驱时，高 $h$ 最大化总扩展次数。最后，对于评估函数 $f_α = g + αh$，当非目标状态满足 $h>0$ 时，每个启发式权重 $0 \leq α<1$ 都会消除对平局打破的敏感性，并且所有平局打破策略都会扩展相同的状态集合。