Accelerating backtrack search with a best-first-search strategy - Mann, Zoltán Ádám; Szép, Tamás (Zielona Góra: Uniwersytet Zielonogórski)
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.
Keywords: best-first search; backtrack; branch-and-bound; constraint satisfaction problems; frequent restarting