Legjobbat először keresés

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

A legjobbat először keresés egy olyan keresőalgoritmus, amely feltérképezi a gráfot egy megadott szabály szerint kiválasztott legígéretesebb csomópont bejárásával. Judea Pearl a legjobbat először keresést úgy jellemezte, mint becslés az n csomópont ígéretességére egy "heurisztikus kiértékeléssel , ami jellemzően függ az n tulajdonságaitól, a cél leírásától, az eddig elvégzett keresés információitól és elsősorban a problémakörrel kapcsolatos minden egyéb információtól."[1][2]Egyes szerzők a "legjobbat először keresés" algoritmust említik, hogy kifejezetten egy olyan heurisztikus keresésre utaljanak, amely egy bejárási út végének megjóslásával próbálja meghatározni milyen közel van az egy megoldáshoz, és így azokat az utakat járják be először, amelyek a legközelebb állnak megoldáshoz. Ezt a speciális keresést mohó legjobbat először keresésnek[2] vagy tiszta heurisztikus keresésnek nevezik.[3]

A bejárásra alkalmas legjobb jelölt hatékony kiválasztását általában egy prioritási sorrend használatával valósítják meg.

Az A* keresési algoritmus egy példa a legjobbat először keresési algoritmusra, úgy ahogy a B* is. A legjobbat először algoritmusokat gyakran használják útvonalak megtalálására kombinatorikus keresések során. Sem az A*, sem a B* nem mohó legjobbat először keresés, mivel a célig vezető becsült távolságon túl a kezdetektől való távolságot is tartalmazzák.

Legjobbat először keresés működése

Mohó LEK[szerkesztés]

A mohó algoritmus segítségével bejárjuk a szülő első utódját. Utód létrehozása után:[4]

  1. Ha az utód heurisztikája jobb, mint a szülőé, akkor az utódot a sor elejére állítják (a szülő közvetlenül az utód mögé helyezésével), és a ciklus újraindul.
  2. Egyébként az utód bekerül a sorba (a heurisztikus értéke által meghatározott helyre). Az eljárás kiértékeli a szülő fennmaradó utódait (ha vannak ilyenek).

Jegyzetek[szerkesztés]

  1. Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
  2. a b Sablon:Russell Norvig 2003
  3. Sablon:Russell Norvig 2003
  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

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Best-first search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk[szerkesztés]

Kapcsolódó szócikkek[szerkesztés]