Legjobbat először keresés
A legjobbat először keresés (best-first search) egy olyan keresőalgoritmus, amely feltérképezi a gráfot egy megadott szabály szerint kiválasztott legígéretesebb csomópont kiterjesztésével.
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ő függvénnyel, amely általában függhet az n tulajdonságaitól, a cél meghatározásától, az addig elvégzett keresési információktól, és elsősorban a problémakörrel kapcsolatos kiegészítő információktól.”[1][2] Egyes szerzők a legjobbat először keresés meghatározással kifejezetten olyan keresésre utalnak, amelynek heurisztikája megpróbálja megjósolni, hogy a bejárási út vége mennyire közel van a céltól, és így azokat az utakat járják be először, amelyeket a célhoz közelebb állónak becsülnek. Ezt a konkrét keresést mohó legjobbat először keresésnek (greedy best-first search)[2] vagy tisztán heurisztikus keresésnek (pure heuristic search) nevezik.[2]
Az aktuálisan legjobb bővítési jelölt hatékony kiválasztása jellemzően egy prioritásos sor (priority queue) segítségével valósul meg.
Az A* algoritmus és a B* algoritmus a legjobbat először keresési algoritmusok példái. 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 kiindulóponttól való távolságot is tartalmazzák.
Mohó LEK
[szerkesztés]Egy mohó algoritmus segítségével kiterjesztjük a szülő első utódját. Az utód meghatározása után:[3]
- Ha az utód heurisztikája jobb, mint a szülőé, akkor az utódot a prioritásos sor elejére állítják (a szülőt közvetlenül az utód mögé helyezve), és a ciklus újraindul.
- Más esetben az utódod hozzáadják a sorhoz (a heurisztikus értéke által meghatározott helyre), majd az eljárás kiértékeli a szülő fennmaradó utódait (ha vannak ilyenek).
Alább látható ezen algoritmus pszeudokódként, ahol a Sor egy prioritásos sort jelöl, amely a csomópontokat a céltól való heurisztikus távolságuk alapján rendezi. Ez az implementáció nyomon követi a meglátogatott csomópontokat, ezért irányítatlan gráfok esetén is használható, és módosítható az útvonal lekérdezéséhez.
Függvény LEK(start, cél): Csomópont
start.Feltárt ← Igaz;
Sor.Hozzáad(start);
Ciklus_Míg Sor.Elemszám != 0:
aktuális_csomópont ← Sor.Kivesz(aktuális_csomópont);
Ciklus I ← (1..aktuális_csomópont.Szomszédszám):
szomszéd ← aktuális_csomópont.Szomszédok[I]
Ha szomszéd.Feltárt = Hamis Akkor:
Ha szomszéd = cél Akkor:
LEK ← szomszéd;
Különben:
szomszéd.Feltárt ← Igaz;
Sor.Hozzáad(szomszéd);
Ha Vége
Ha Vége
Ciklus Vége
Ciklus Vége
LEK ← NULL;
Függvény Vége
Jegyzetek
[szerkesztés]- ↑ Pearl, J.. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 48.. o. (1984)
- ↑ a b c Russell, Stuart J., Norvig, Peter. Artificial Intelligence: A Modern Approach, 2, Upper Saddle River, New Jersey: Prentice Hall (2003). ISBN 0-13-790395-2
- ↑ Carnegie Mellon: Greedy Best-First Search when EHC Fails
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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.