A depth-first approach to target-value search


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.


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.”

Read more from SRI