在 A* 搜索中，若多个节点拥有相同的 $f$ 值，需要通过平局策略决定扩展顺序。本文考察了九种常用的平局策略，并在一致启发式下构造了正成本实例，使得任意两种策略之间可以出现任意大的加法扩展差距。我们给出一个参数化的单位成本网格模型，证明在低 $h$ 与 FIFO、LIFO 之间的扩展计数比率可以无上界。进一步分析了单位成本搜索中，当非目标节点的启发值 $h=0$ 时，靠近目标的精确启发值会产生互补的极端行为：在完美区域内，低 $h$ 能最小化剩余扩展次数；而在每个 $h=1$ 的最终高原状态都是目标前驱的情形下，高 $h$ 能最大化总扩展次数。最后，考虑加权评估函数 $f_{\alpha}=g+\alpha h$，在 $h=0$ 于非目标的前提下，任意权重 $0\le\alpha$ 都会导致类似的极端扩展行为。
点评