Digital Library of Zielona Góra contains 65 497 digital objects
Object
Title: Accelerating backtrack search with a best-first-search strategy
Współtwórca:
Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Tytuł publikacji grupowej:
Abstract:
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.
Wydawca:
Zielona Góra: Uniwersytet Zielonogórski
Identyfikator zasobu:
DOI:
Strony:
Źródło:
AMCS, volume 24, number 4 (2014) ; click here to follow the link
Jezyk:
Licencja CC BY 4.0:
Prawa do dysponowania publikacją:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Jednostki organizacyjne > Wydział Informatyki, Elektrotechniki i Automatyki
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Typy utworów > Artykuły
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Czasopisma naukowe i serie wydawnicze UZ > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2014)
Last modified:
14 lip 2025
In our library since:
29 kwi 2024
Number of object content hits:
205
All available object's versions:
https://zbc.uz.zgora.pl/publication/88827
Show description in RDF format:
Show description in OAI-PMH format:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24, number 1 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24, number 2 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24, number 3 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24, number 4 (2014)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
| Edition name | Date |
|---|---|
| Accelerating backtrack search with a best-first-search strategy | 14 lip 2025 |
Objects Similar
Walkowiak, Krzysztof Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Patan, Maciej (1975- ) Uciński, Dariusz Korbicz, Józef (1951- ) - ed. Sauter, Dominique - ed.
Liu, Xinbo Wang, Wen Chen, Xin Sterna, Małgorzata Blazewicz, Jacek Kitowski, Zygmunt - ed. Piskur, Paweł - ed. Hożyń , Stanisław - ed.
Arangú, Marlene Salido, Miguel A. Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Mann, Zoltán Ádám Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Mann, Zoltán Ádám Orbán, András Farkas, Viktor Korbicz, Józef (1951- ) - red.
