Hledejte podle první nejlepší shody

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. ledna 2015; kontroly vyžadují 8 úprav .

Best -first search je vyhledávací  algoritmus , který zkoumá graf rozšiřováním nejslibnějších uzlů vybraných v souladu se stanoveným pravidlem .

Judea  Pearl popsala nejlepší -první vyhledávání , která obecně může záviset na povazehodnotu nějaké „heuristické funkce hodnocenítím, že jako skóre uzlu vzala [1] [2]

Někteří autoři použili vyhledávání best-first specificky k popisu vyhledávání pomocí heuristiky, která měří blízkost k cílovému stavu, takže cesty s nejlepším heuristickým skóre jsou považovány za první. Tento konkrétní typ vyhledávání se nazývá greedy best-first search . [2]

Efektivní výběr aktuálního nejlepšího kandidáta pro pokračování ve vyhledávání lze realizovat pomocí prioritní fronty .

Algoritmus vyhledávání A* (A-star) je příkladem optimálního vyhledávání typu best-first. Algoritmus best-first se často používá pro hledání cesty v kombinatorickém vyhledávání.

Algoritmus

OTEVŘENO = [Výchozí stav] dokud není OPEN prázdná opakovat: 1. Odstraňte nejlepší uzel z OPEN, říkejme mu N. 2. Pokud je N cílovým stavem, traste cestu zpět k počátečnímu uzlu (prostřednictvím záznamů k rodičům z N) a vraťte cestu. 3. Vytvořte seznam potomků uzlu N. 4. Vyhodnoťte každé dítě, přidejte ho do OPEN a zaznamenejte N jako jeho rodiče. Dokončit

V této verzi není algoritmus úplný , protože s jeho pomocí není vždy možné najít cestu mezi dvěma uzly, i když jeden existuje. Algoritmus se například „zasekne“ ve smyčce, pokud narazí na slepou uličku – uzel s potomkem, který je jeho rodičem. Algoritmus se vrátí ke svému nadřazenému prvku, přidá stub uzel dítěte do seznamu OPENa znovu k němu přejde a tak dále.

Další verze rozšiřuje algoritmus pomocí dalšího seznamu CLOSEobsahujícího všechny uzly, které byly vyhodnoceny a nebudou předmětem kontroly. Tím se zabrání přehodnocení jakéhokoli uzlu a negenerují se nekonečné smyčky.

OTEVŘENO = [počáteční stav] ZAVŘÍT=[] dokud není OPEN prázdná opakovat: 1. Odeberte nejlepší uzel z OPEN, říkejme mu N, přidejte jej do CLOSE. 2. Pokud je N cílovým stavem, traste cestu zpět k počátečnímu uzlu (prostřednictvím záznamů k rodičům z N) a vraťte cestu. 3. Vytvořte seznam potomků uzlu N. 4. Pro každé dítě opakujte: A. Pokud dítě není v seznamu CLOSE: Vyhodnoťte jej, přidejte jej do OPEN a zaznamenejte N jako jeho rodiče. b. Jinak: pokud je tato nová cesta lepší než předchozí, změňte položku na nadřazenou. Dokončit

Algoritmus popsaný tímto pseudokódem v obou verzích se jednoduše ukončí, když není nalezena žádná cesta. Praktické implementace mohou vyžadovat speciální řešení této situace.

The Greedy Best-First Search

Použití chamtivého algoritmu rozšiřuje první dítě rodičů. Po vygenerování dětí [3] :

  1. Pokud je heuristické skóre dítěte lepší než jeho rodiče, dítě je umístěno na začátek fronty (s rodiči opět hned za ním) a smyčka se restartuje.
  2. V opačném případě je dítě zařazeno do fronty (v místě určeném jeho heuristickou cenou). Poté se hodnotí zbytek dědiců (pokud existují) rodiče.

Poznámky

  1. ↑ Pearl J. Heuristika: Inteligentní vyhledávací strategie pro řešení počítačových problémů. - Addison-Wesley, 1984. - S. 48.
  2. ↑ 1 2 Russell SJ, Norvig P. Umělá inteligence: Moderní přístup . — 2. - Upper Saddle River, New Jersey: Prentice Hall, 2003. - s. 94-95 (pozn. 3). — 1132 s. — ISBN 0-13-790395-2 . .
  3. ↑ Greedy Best-First Search when EHC Fails Archived 11. června 2010 na Wayback Machine , Carnegie Mellon.

Odkazy

  • Wikibooks: Artificial Intelligence: Best-First Search
 Algoritmy pro vyhledávání grafů
Neinformované metody
Informované metody
Zkratky
Minimální kostra
jiný