{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T10:14:18Z","timestamp":1760523258114},"reference-count":0,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"4","license":[{"start":{"date-parts":[[2014,12,1]],"date-time":"2014-12-01T00:00:00Z","timestamp":1417392000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p> Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is because \u201cfortunate\u201d branching decisions can lead to finding a solution quickly, whereas \u201cunfortunate\u201d 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-firstsearch 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.<\/jats:p>","DOI":"10.2478\/amcs-2014-0066","type":"journal-article","created":{"date-parts":[[2015,1,19]],"date-time":"2015-01-19T17:03:21Z","timestamp":1421687001000},"page":"901-916","source":"Crossref","is-referenced-by-count":1,"title":["Accelerating backtrack search with a best-first-search strategy"],"prefix":"10.61822","volume":"24","author":[{"given":"Zolt\u00e1n \u00c1d\u00e1m","family":"Mann","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Theory Budapest University of Technology and Economics, Magyar tud\u00f3sok k\u00f6r\u00fatja 2., 1117 Budapest, Hungary"}]},{"given":"Tam\u00e1s","family":"Sz\u00e9p","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Theory Budapest University of Technology and Economics, Magyar tud\u00f3sok k\u00f6r\u00fatja 2., 1117 Budapest, Hungary"}]}],"member":"37438","published-online":{"date-parts":[[2014,12,20]]},"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/24\/4\/article-p901.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/amcs-2014-0066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:28:50Z","timestamp":1709202530000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.sciendo.com\/article\/10.2478\/amcs-2014-0066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,1]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2014,12,20]]},"published-print":{"date-parts":[[2014,12,1]]}},"alternative-id":["10.2478\/amcs-2014-0066"],"URL":"https:\/\/doi.org\/10.2478\/amcs-2014-0066","relation":{},"ISSN":["2083-8492"],"issn-type":[{"value":"2083-8492","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,1]]}}}