Wyszukiwanie zaawansowane ?

Obiekt

Accelerating backtrack search with a best-first-search strategy

Pobierz

Tytuł: Accelerating backtrack search with a best-first-search strategy

Autor:

Mann, Zoltán Ádám ; Szép, Tamás

Data wydania:

2014

Typ zasobu:

artykuł

Współtwórca:

Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.

Tytuł publikacji grupowej:

AMCS, Volume 24 (2014)

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:

oai:zbc.uz.zgora.pl:78996

DOI:

10.2478/amcs-2014-0066

Strony:

901-916

Źródło:

AMCS, volume 24, number 4 (2014) ; kliknij tutaj, żeby przejść

Jezyk:

eng

Prawa do dysponowania publikacją:

Biblioteka Uniwersytetu Zielonogórskiego

Temat i słowa kluczowe:

best-first search backtrack branch-and-bound constraint satisfaction problems frequent restarting

Kolekcje, do których przypisany jest obiekt:

Data ostatniej modyfikacji:

2024-11-05

Data dodania obiektu:

2024-04-29

Liczba wyświetleń treści obiektu:

55

Wszystkie dostępne wersje tego obiektu:

https://zbc.uz.zgora.pl/repozytorium/publication/88827

Wyświetl opis w formacie RDF:

RDF

Wyświetl opis w formacie OAI-PMH:

OAI-PMH

Nazwa wydania Data
Accelerating backtrack search with a best-first-search strategy 2024-11-05

Obiekty

Podobne
AMCS, volume 12 (2002)
AMCS, volume 12 (2002)

The branch and bound algorithm for a backup virtual path assignment in survivable ATM networks

Walkowiak, Krzysztof Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.

2002
artykuł
AMCS, volume 18 (2008)
AMCS, volume 18 (2008)

Configuring a sensor network for fault detection in distributed parameter systems

Patan, Maciej (1975- ) Uciński, Dariusz Korbicz, Józef (1951- ) - ed. Sauter, Dominique - ed.

2008
artykuł
AMCS, Volume 21 (2011)
AMCS, Volume 21 (2011)

A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Arangú, Marlene Salido, Miguel A. Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.

2011
artykuł
AMCS, Volume 20 (2010)
AMCS, Volume 20 (2010)

Numbering action vertices in workflow graphs

Mann, Zoltán Ádám Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.

2010
artykuł
AMCS, volume 17 (2007)
AMCS, volume 17 (2007)

Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

Mann, Zoltán Ádám Orbán, András Farkas, Viktor Korbicz, Józef (1951- ) - red.

2007
artykuł
Więcej

Dane kontaktowe

Adres

Biblioteka Uniwersytetu Zielonogórskiego
al. Wojska Polskiego 71
65-762 Zielona Góra

Telefon

(+48) 68 328 21 55

E-Mail

repozytorium@uz.zgora.pl

Odwiedź nas!

Ta strona wykorzystuje pliki 'cookies'. Więcej informacji