SOURCE-LINKED INTELLIGENCE

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

arXiv · AI, language, vision and robotics · article · Sep 20, 2026 · UTC

In the A* search algorithm, the tie-breaking strategies for nodes with the same $f$-value determines which states A* expands on the final $f$-layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low-$h$ with FIFO and LIFO. In unit-cost search with $h > 0$ at non-goals, exact heuristic values near the goal lead to complementary extremal result

Read original source ↗ Open in workspace

recordType

paper

region

Global