Backtrack-style exhaustive search algorithms for NP-hard problems#R##N#tend to have large variance in their runtime. This is because ``fortunate''#R##N#branching decisions can lead to finding a solution quickly, whereas#R##N#``unfortunate'' decisions in another run can lead the algorithm to#R##N#a region of the search space with no solutions. In the literature,#R##N#frequent restarting has been suggested as a means to overcome this#R##N#problem.#R##N#In this paper, we propose a more sophisticated approach: a best-first-search heuristic#R##N#to quickly move between parts of the search space, always concentrating#R##N#on the most promising region. We describe how this idea can be efficiently#R##N#incorporated into a backtrack search algorithm, without#R##N#sacrificing optimality. Moreover, we demonstrate#R##N#empirically that, for hard solvable problem instances, the new approach#R##N#provides significantly higher speed-up than frequent restarting.
['Zoltán Ádám Mann', 'Tamas Szep']
Accelerating backtrack search with a best-first-search strategy