A* Search for Soft Constraints Bounded by Tree Decompositions
Martin Sachenbacher, Brian Charles Williams · 2005
Abstract. Some of the most efficient methods for solving soft constraints are based on heuristic search using an evaluation function that is mechanically generated from the problem. However, if only a few best solutions are needed, significant effort can be wasted pre-computing heuristics that are not used during search. Recently, a scheme for depth-first branch-and-bound search has been proposed that avoids the problems of pre-computation by interleaving search with the generation of heuristics using tree decomposition and dynamic programming. In this paper, we extend this idea to A * search, which has the advantage of expanding a minimal number of search nodes to find optimal solutions, and allows to generate solutions in best-first order. The approach uses tree decomposition and dynamic programming to generate only those heuristics that are specifically required to generate a next best solution. The time complexity of the approach is thus optimal among all search algorithms having access to the same heuristics, while its space complexity is bounded by structural parameters of the constraint graph (induced width) in the worst case, and is even lower in the average case.