Abstract
Finding optimal solutions for NP-hard combinatorial problems, such as the N-puzzle or the Traveling Salesman Problem, is often computationally prohibitive. Traditional approaches typically force a choice between fast but suboptimal approximation algorithms and slow but optimal heuristic searches. This paper introduces a middle-ground strategy through two algorithms: Joint and Local Path A (LPA). These methods utilize an initial approximated path as a "rough draft" and apply localized A* searches to refine and shorten the path. Experimental results on the 15-puzzle demonstrate that this hybrid approach can produce high-quality solutions with a fraction of the computational cost required by global optimal solvers.
Introduction
In the realm of combinatorial optimization, researchers frequently encounter a trade-off between solution quality and computational feasibility. Approximation algorithms offer polynomial-time performance but often yield excessively long or "messy" paths. Conversely, heuristic search algorithms like A* guarantee optimality but suffer from exponential growth in time and memory requirements as problem complexity increases.
Presented at AAAI-86, Ratner and Pohl's work addresses this gap. They propose that instead of seeking global optimality from scratch, one can start with a "good enough" solution and use targeted local searches to polish it. This approach ensures that the total computation remains bounded by a polynomial function of the problem size while significantly improving the quality of the final output.
Methodology
The core of the proposed strategy involves treating an approximated path as a baseline for local optimization. The authors introduce two primary algorithms to implement this philosophy.
Local Path A (LPA)
LPA employs a sliding window mechanism. It traverses the initial approximated path, selecting segments of a fixed maximum length, $d_{max}$. For each segment, it performs a local A search to find a shorter alternative. If a shortcut is found, the original segment is replaced. A parameter $\delta_{anchor}$ controls the step size of the sliding window, determining how far the search advances after each iteration.
The Joint Algorithm
The Joint algorithm is based on the observation that in many approximation schemes—such as those using macro-operators—the most significant inefficiencies occur at "joints," the points where the algorithm transitions between different sub-goals. The algorithm first partitions the path into optimal segments of length $d_{max}$. It then focuses its local search efforts specifically on the nodes connecting these segments, smoothing out the transitions to eliminate unnecessary moves.
Post-Processing and Initial Approximation
To further refine results, a "Squeeze" process is used to identify and remove trivial cycles (e.g., a sequence of moves that returns the puzzle to a previous state). For the initial approximation, the authors utilize Korf’s Macro-Operator algorithm, which solves the puzzle by reaching a sequence of sub-goals. While fast, this method typically results in very long paths that are ripe for optimization.
Experimental Results
The algorithms were benchmarked using a standard set of 50 randomly generated 15-puzzle problems. Two admissible heuristics were tested: $h_1$ (Manhattan distance) and $h_2$ (Manhattan distance plus a penalty for tile reversals).
The hybrid approach yielded impressive gains in both efficiency and path quality. While an optimal solver like Iterative Deepening A might expand upwards of 50 million nodes to solve a single 15-puzzle instance, the Joint and LPA algorithms achieved high-quality results by expanding only 6,000 to 12,000 nodes.
Key insights from the experiments include:
- Path Quality: Initial macro-operator paths averaged 143 moves. After applying the "Squeeze" and local search optimizations, average path lengths dropped to approximately 86 moves.
- Heuristic Impact: The more informed $h_2$ heuristic roughly halved the number of nodes expanded compared to $h_1$ without compromising solution quality.
- Reliability: Unlike other heuristic methods of the time, such as HPA, which often failed to find solutions within time limits, Joint and LPA* consistently produced "reasonable" paths.
Conclusion
The Joint and LPA* algorithms represent a powerful paradigm for practical problem-solving. By localizing the NP-hardness of search to small, constant-distance segments, the authors transform a globally exponential problem into a series of manageable local tasks. While the final solution quality depends on the initial approximation and the topology of the state-space graph, these methods offer a robust alternative for applications where speed and "good enough" solutions are prioritized over absolute optimality. Future work may involve automating parameter tuning for $d_{max}$ and exploring applications in domains with different graph characteristics.
Summary updated