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

arXiv:2609.23293v1 Announce Type: new Abstract: 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 results: low-h minimizes the number of remaining expansions from a common configuration within the perfect region, while high-h maximizes the total number of expansions when every final-plateau state with h=1 is a goal predecessor. Finally, with the evaluation function f_{alpha} = g + alpha h, when h>0 at non-goals, every heuristic weight 0 leq alpha<1 eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

Source: arXiv cs.AI | 2026-09-23