Obiekt
Tytuł: 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) ; kliknij tutaj, żeby przejść
Jezyk:
Prawa do dysponowania publikacją:
Biblioteka Uniwersytetu Zielonogórskiego
Kolekcje, do których przypisany jest obiekt:
- 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)
- 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)
Data ostatniej modyfikacji:
2024-11-05
Data dodania obiektu:
2024-04-29
Liczba wyświetleń treści obiektu:
54
Wszystkie dostępne wersje tego obiektu:
https://zbc.uz.zgora.pl/publication/88827
Wyświetl opis w formacie RDF:
Wyświetl opis w formacie OAI-PMH:
-
International Journal of Applied Mathematics and Computer Science (AMCS)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 26 (2016)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24 (2014)
-
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)
- Controllability of nonlinear implicit fractional integrodifferential systems
- On an infinite dimensional linear-quadratic problem with fixed endpoints: The continuity question
- Minimum energy control of fractional descriptor positive discrete-time linear systems
- Improving the stability of discretization zeros with the Taylor method using a generalization of the fractional-order hold
- Efficiency analysis of control algorithms in spatially distributed systems with chaotic behavior
- Analytic results for oscillatory systems with extremal dynamic properties
- Further results on robust fuzzy dynamic systems with LMI D-stability constraints
- On infinite horizon active fault diagnosis for a class of non-linear non-Gaussian systems
- Fault diagnosis in a networked control system under communication constraints: A quadrotor application
- Nonlinear control for a diesel engine: A CLF-based approach
- A mathematical model for fluid-glucose-albumin transport in peritoneal dialysis
- A modified van der Pol equation with delay in a description of the heart action
- A hybrid algorithm for solving inverse problems in elasticity
- A finite-buffer queue with a single vacation policy: An analytical study with evolutionary positioning
- Accelerating backtrack search with a best-first-search strategy
- A primal sub-gradient method for structured classification with the averaged sum loss
- An analytical method for well-formed workflow/Petri net verification of classical soundness
- A system for deduction-based formal verification of workflow-oriented software models
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24, number 1 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 23 (2013)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 22 (2012)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 21 (2011)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 20 (2010)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 19 (2009)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 18 (2008)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 17 (2007)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 16 (2006)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 15 (2005)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 13 (2003)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 12 (2002)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 11 (2001)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 10 (2000)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 9 (1999)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 8 (1998)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 7 (1997)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 6 (1996)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 5 (1995)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 4 (1994)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 3 (1993)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 2 (1992)
-
International Journal of Applied Mathematics and Computer Science (AMCS),volume 1 (1991)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 26 (2016)
| Nazwa wydania | Data |
|---|---|
| Accelerating backtrack search with a best-first-search strategy | 2024-11-05 |
