Introduction
In heuristic search, a fundamental trade-off exists between memory usage and time efficiency. Best-First Search algorithms, such as A, are time-efficient because they maintain a closed list of all visited nodes, allowing them to detect and ignore duplicates. However, this comes at the cost of exponential memory requirements. Conversely, Depth-First Search (DFS) and its iterative-deepening variants (like IDA) utilize only linear memory but are "forgetful." On graphs containing cycles or multiple paths to the same state—common in domains like grid navigation or the Rubik's Cube—DFS can explore the same states repeatedly, leading to redundant computation.
This paper introduces a method to bridge this gap by giving DFS the "memory" of a Best-First Search without sacrificing its linear space complexity. The core idea is to automatically learn a Finite State Machine (FSM) that identifies and prunes redundant operator sequences in constant time.
Methodology
The proposed approach consists of a preprocessing learning phase followed by an optimized search phase.
1. The Learning Phase
Before the main search begins, the algorithm performs a limited-depth Breadth-First Search (BFS) on the problem domain. This phase identifies "duplicate operator strings"—different sequences of moves that lead to the same state. For example, in a 2D grid, the sequence [Up, Right] and [Right, Up] are duplicates because they terminate at the same coordinate.
As shown in the figure above, the BFS identifies states reached through multiple paths (marked with asterisks). The algorithm then defines "forbidden words": if two sequences reach the same state, the more expensive one (or one chosen by a tie-breaking rule) is marked as forbidden.
2. FSM Construction and Pruning
Using an algorithm similar to Aho-Corasick string matching, these forbidden sequences are compiled into a Finite State Machine (FSM). Each state in the FSM represents a prefix of a forbidden operator sequence.
During the actual DFS, the algorithm maintains the current state of the FSM. Before applying any operator, the DFS performs a simple table lookup in the FSM. If applying that operator would complete a "forbidden word," the branch is pruned immediately. Because this check is a constant-time lookup, it adds virtually zero overhead to the search process.
Experimental Results
The technique was evaluated on several classic combinatorial problems, demonstrating significant reductions in the effective branching factor and total nodes generated.
- Grid Search: This method achieved a theoretical breakthrough, reducing the complexity of DFS from $O(3^r)$ (exponential) to $O(r^2)$ (polynomial).
- Fifteen Puzzle: The brute-force branching factor dropped from 2.13 to 1.98. In practical IDA searches, this resulted in a 72% reduction* in nodes generated.
- Twenty-Four Puzzle: Using Weighted IDA, the FSM pruning achieved a 94.23% savings* in nodes, enabling the solution of problems that previously timed out.
- Rubik’s Cube: For the 3x3x3 version, the branching factor was reduced from 13.50 to 13.26. While the numerical change is small, the exponential nature of the search means this reduction saves billions of nodes in deep searches.
Discussion and Limitations
While highly effective, the method has trade-offs. Although the DFS remains linear in memory, the FSM table itself requires storage; for the 15-puzzle, the FSM reached over 55,000 states. Furthermore, the effectiveness of the pruning is tied to the depth of the initial BFS; shallow learning may fail to capture long-cycle duplicates.
Future work may involve more sophisticated selection of duplicate strings to optimize FSM size and handling domains where operator availability changes dynamically based on the state. Nevertheless, this "compilation of structure" represents a powerful way to enhance DFS with the strengths of Best-First Search.
Summary updated