- Tytuł:
- Accelerating backtrack search with a best-first-search strategy
- Autorzy:
-
Mann, Z. Á.
Szép, T. - Tematy:
-
best first search
backtrack
branch and bound
constraint satisfaction problem (CSP)
frequent restarting
algorytm wyszukiwania
system backtrack
metoda podziału i ograniczeń
programowanie z ograniczeniami - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Oficyna Wydawnicza
- Powiązania:
- https://bibliotekanauki.pl/articles/329816.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł