Nejlepší první vyhledávání - Best-first search - Wikipedia

Graf a strom
vyhledávací algoritmy
Výpisy
související témata

Nejlepší první vyhledávání je vyhledávací algoritmus který zkoumá a graf rozšířením nejslibnějšího uzlu vybraného podle zadaného pravidla.

Judea Pearl popsal nejlepší první vyhledávání jako odhad příslibu uzlu n „heuristickou vyhodnocovací funkcí které obecně mohou záviset na popisu n, popis cíle, informace shromážděné při vyhledávání až do tohoto bodu a nejdůležitější informace o veškerých dalších znalostech o problémové doméně. “[1][2]

Někteří autoři použili „vyhledávání od začátku“, aby odkazovali konkrétně na vyhledávání pomocí heuristický že se pokouší předpovědět, jak blízko je konec cesty k řešení (nebo cíli), takže cesty, které jsou považovány za blíže k řešení (nebo cíli), jsou nejprve prodlouženy. Tento konkrétní typ vyhledávání se nazývá chamtivý nejlepší první vyhledávání[2] nebo čisté heuristické vyhledávání.[3]

Efektivní výběr aktuálního nejlepšího kandidáta na prodloužení se obvykle provádí pomocí a prioritní fronta.

The * Vyhledávací algoritmus je příkladem prvního vyhledávacího algoritmu, jak je B *. Při hledání cesty se často používají algoritmy nejlepší první kombinatorické vyhledávání. Ani A *, ani B * nejsou chamtivým vyhledávačem typu „best-first“, protože kromě odhadované vzdálenosti k cíli zahrnují i ​​vzdálenost od začátku.

Chamtivý BFS

Používat chamtivý algoritmus, rozšířit prvního nástupce rodiče. Po vygenerování nástupce:[4]

  1. Pokud je heuristika nástupce lepší než její nadřazená položka, je nástupce nastaven na přední část fronty (s nadřazeným prvkem vloženým přímo za ni) a smyčka se restartuje.
  2. Jinak je nástupce vložen do fronty (na místě určeném jeho heuristickou hodnotou). Postup vyhodnotí zbývající nástupce (pokud existují) rodiče.

Viz také

Reference

  1. ^ Pearl, J. Heuristika: Strategie inteligentního vyhledávání pro řešení počítačových problémů. Addison-Wesley, 1984. str. 48.
  2. ^ A b Russell, Stuart J.; Norvig, Peter (2003), Umělá inteligence: moderní přístup (2. vyd.), Upper Saddle River, New Jersey: Prentice Hall, ISBN  0-13-790395-2. 94 a 95 (poznámka 3).
  3. ^ Korf, Richard E. (1999). Msgstr "Algoritmy vyhledávání umělé inteligence". V Atallah, Michail J. (ed.). Handbook of Algorithms and Theory of Computation. CRC Press. ISBN  0849326494.
  4. ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

externí odkazy