REAL

Accelerating backtrack search with a best-first-search strategy

Mann, Zoltán Ádám and Szép, Tamás (2014) Accelerating backtrack search with a best-first-search strategy. International Journal of Applied Mathematics and Computer Science, 24 (4). pp. 901-916. ISSN 1641-876X

[img]
Preview
Text
Mann_Szep_BFS_2014.pdf

Download (597kB) | Preview

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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Zoltán Ádám Mann
Date Deposited: 22 Sep 2014 21:05
Last Modified: 03 Apr 2023 08:16
URI: http://real.mtak.hu/id/eprint/16009

Actions (login required)

Edit Item Edit Item