A Formal Characterization of the Local Search Topology of the Gap Heuristic
This provides theoretical insights for researchers in heuristic search and optimization, but it is incremental as it builds on existing work on the pancake puzzle.
The paper tackles the problem of analyzing the local search topology of the gap heuristic for the pancake puzzle, showing that in non-goal states without gap-decreasing moves, there exists a move that keeps gaps constant, and it classifies such states into those requiring 2 or 3 actions to reduce gaps.
The pancake puzzle is a classic optimization problem that has become a standard benchmark for heuristic search algorithms. In this paper, we provide full proofs regarding the local search topology of the gap heuristic for the pancake puzzle. First, we show that in any non-goal state in which there is no move that will decrease the number of gaps, there is a move that will keep the number of gaps constant. We then classify any state in which the number of gaps cannot be decreased in a single action into two groups: those requiring 2 actions to decrease the number of gaps, and those which require 3 actions to decrease the number of gaps.