online read us now
Paper details
Number 4 - December 2014
Volume 24 - 2014
Accelerating backtrack search with a best-first-search strategy
Zoltán Ádám Mann, Tamás Szép
Abstract
Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is
because “fortunate” branching decisions can lead to finding a solution quickly, whereas “unfortunate” decisions in another
run can lead the algorithm to a region of the search space with no solutions. In the literature, frequent restarting has been
suggested as a means to overcome this problem. In this paper, we propose a more sophisticated approach: a best-first-search
heuristic to quickly move between parts of the search space, always concentrating on the most promising region. We describe how this idea can be efficiently incorporated into a backtrack search algorithm, without sacrificing optimality. Moreover, we demonstrate empirically that, for hard solvable problem instances, the new approach provides significantly
higher speed-up than frequent restarting.
Keywords
best-first search, backtrack, branch-and-bound, constraint satisfaction problem, frequent restarting