Korbicz, Józef - red. ; Uciński, Dariusz - red.
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.
Zielona Góra: Uniwersytet Zielonogórski
AMCS, volume 24, number 4 (2014) ; kliknij tutaj, żeby przejść
Biblioteka Uniwersytetu Zielonogórskiego
2024-04-29
2024-04-29
42
https://zbc.uz.zgora.pl/publication/88827
Nazwa wydania | Data |
---|---|
Accelerating backtrack search with a best-first-search strategy | 2024-04-29 |
Walkowiak, Krzysztof Korbicz, Józef - red. Uciński, Dariusz - red.
Patan, Maciej (1975- ) Uciński, Dariusz Korbicz, Józef - ed. Sauter, Dominique - ed.
Arangú, Marlene Salido, Miguel A. Korbicz, Józef - red. Uciński, Dariusz - red.
Mann, Zoltán Ádám Korbicz, Józef - red. Uciński, Dariusz - red.
Mann, Zoltán Ádám Orbán, András Farkas, Viktor Korbicz, Józef - red.