ACCELERATING BACKTRACK SEARCH WITH A BEST-FIRST-SEARCH STRATEGY

作者：Mann Zoltan Adam^*; Szep Tamas

来源：International Journal of Applied Mathematics and Computer Science, 2014, 24(4): 901-916.

DOI：10.2478/amcs-2014-0066

• best-first search
• backtrack
• branch-and-bound
• constraint satisfaction problem
• frequent restarting

Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is because %26quot;fortunate%26quot; branching decisions can lead to finding a solution quickly, whereas %26quot;unfortunate%26quot; 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.

• 出版日期2014-12