Object
Title: Accelerating backtrack search with a best-first-search strategy
Contributor:
Korbicz, Józef - red. ; Uciński, Dariusz - red.
Group publication title:
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.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Resource Identifier:
DOI:
Pages:
Source:
AMCS, volume 24, number 4 (2014) ; click here to follow the link
Language:
Rights:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Repository > Faculties > Faculty of Computer, Electrical and Control Engineering
- Repository > Types of work > Articles
- Repository > Scientific journals and UZ publishing series > International Journal of Applied Mathematics and Computer Science (AMCS)
- Repository > Scientific journals and UZ publishing series > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2014)
Last modified:
Apr 29, 2024
In our library since:
Apr 29, 2024
Number of object content hits:
38
All available object's versions:
https://zbc.uz.zgora.pl/repozytorium/publication/88827
Show description in RDF format:
Show description in OAI-PMH format:
-
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)
| Edition name | Date |
|---|---|
| Accelerating backtrack search with a best-first-search strategy | Apr 29, 2024 |
