A depth-first approach to target-value search

TECHNICAL PUBLICATION:

SoCS 2009

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)

citation

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.