Szerkesztő:Franky515/Legjobbat először keresés

A legjobbat először keresés egy olyan keresési algoritmus, amely feltérképezi a gráfot a megadott szabály szerint kiválasztott legígéretesebb csomópont kibontásával.

Judea Pearl az első legjobb keresést úgy jellemezte, hogy az " n " csomópont ígéretét egy "heurisztikus értékelési funkcióval becsülte meg $f(n)$ amely általában függhet az n leírásától, a cél leírásától, a keresés által az adott pontig gyűjtött információktól, és ami a legfontosabb, a problémakörrel kapcsolatos minden további ismerettől. "

Egyes szerzők a "legjobbat először keresést" használják, hogy kifejezetten egy olyan heurisztikus keresésre utaljanak, amely megpróbálja megjósolni, hogy egy út bejárása milyen közel van egy megoldáshoz azon a módon, hogy a megoldáshoz rövidebbnek ítélt útvonalakat térképezik fel először. Ezt a speciális keresést mohó legjobbat először keresésnek vagy tiszta heurisztikus keresésnek hívják.

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

Az A * keresési algoritmus egy példa a legjobbat előszor keresési algoritmusra, ahogy a B * is . A legjobbat először algoritmusokat gyakran használják a utvonalak találására kombinatorikus kereséssorán. Sem az A *, sem a B * nem egy 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.

Mohó LEK

Mohó algoritmus segítségével bontsa ki a szülő első utódját. Utód létrehozása után:

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 a háta mögé helyezésével), és a ciklus újraindul.
2. Máskülönben 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).

Lásd még

• Sugárkeresés
• A * keresési algoritmus
• Dijkstra algoritmusa

Külső linkek

• Wikibooks: Mesterséges intelligencia: Legjobbat Először Keresés