A depth-first approach to target-value search
In this paper, we consider how to improve the scalability and efficiency of target-value-path search on directed acyclic graphs. To this end, we introduce a depth-first heuristic search algorithm and a dynamic-programming method to compute the heuristic's pattern database in linear (in the number of edges) time. We show the benefits of the new approach over previous work on this problem (c.f. Kuhn et. Al. "Heuristic search for the target-value problem.")
- download PDF (366K)
Schmidt, T.; Zhou, R.; de Kleer, J.; Price, R.; Kuhn, L. A depth-first approach to target-value search. International Symposium on Combinatorial Search (SoCS 2009); 2009 July 8-10; Lake Arrowhead, CA.