Keresés az első legjobb találat alapján
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. január 11-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .A legjobb első keresés egy olyan keresési algoritmus , amely egy adott szabály szerint kiválasztott legígéretesebb csomópontok kibontásával vizsgálja meg a gráfot .
Judea Pearl a legjobb első keresést úgy írta le , hogy csomópontpontként , amely általában a természettől függhet,valamilyen „értékelési heurisztikus függvény értékét vette [1] [2]
Egyes szerzők a „legjobb először” keresést kifejezetten a keresések leírására használták olyan heurisztikával, amely a célállapothoz való közelséget méri, így a legjobb heurisztikus pontszámmal rendelkező útvonalakat veszik először figyelembe. Ezt a keresési típust mohó legjobb első keresésnek nevezik . [2]
Az aktuális legjobb jelölt hatékony kiválasztása a keresés folytatásához prioritási sor használatával valósítható meg .
Az A* (A-csillagos) keresési algoritmus egy példa az optimális legjobb első keresésre. A legjobb-első algoritmust gyakran használják az útkereséshez a kombinatorikus keresésben.
Algoritmus
OPEN = [Kiinduló állapot] amíg ki nem ürül az OPEN ismétlés: 1. Távolítsa el a legjobb csomópontot az OPEN-ből, nevezzük N-nek. 2. Ha N a célállapot, kövesse az útvonalat a kezdőcsomópontig (az N-ből származó szülői bejegyzéseken keresztül), és adja vissza az útvonalat. 3. Hozzon létre egy listát az N csomópont leszármazottairól. 4. Értékeljen minden gyermeket, adja hozzá az OPEN-hez, és rögzítse N-t szülőjeként. BefejezEbben a verzióban az algoritmus nem teljes , mivel segítségével nem mindig lehet utat találni két csomópont között, még ha van is. Például egy algoritmus "elakad" egy hurokban, ha zsákutcába kerül - egy csomópontba, amelynek a szülője egy gyermek. Az algoritmus visszatér a szülőhöz, hozzáadja a gyermek csonk csomópontját a listához OPEN, majd ismét rákeres, és így tovább.
A következő verzió kiterjeszti az algoritmust egy további lista használatával, CLOSEamely tartalmazza az összes kiértékelt csomópontot, és nem lesz felülvizsgálva. Ez elkerüli a csomópontok újraértékelését, és nem generál végtelen hurkokat.
OPEN = [kezdeti állapot] ZÁRÁS=[] amíg ki nem ürül az OPEN ismétlés: 1. Távolítsa el a legjobb csomópontot az OPEN-ből, nevezzük N-nek, és adja hozzá a CLOSE-hoz. 2. Ha N a célállapot, kövesse az útvonalat a kezdőcsomópontig (az N-ből származó szülői bejegyzéseken keresztül), és adja vissza az útvonalat. 3. Hozzon létre egy listát az N csomópont leszármazottairól. 4. Minden gyermeknél ismételje meg: a. Ha a gyermek nem szerepel a ZÁRÁS listán: Értékelje ki, adja hozzá a NYITÁS-hoz, és rögzítse N-t szülőként. b. Ellenkező esetben: ha ez az új elérési út jobb, mint az előző, módosítsa a bejegyzést a szülőre. BefejezAz ezen pszeudokód által leírt algoritmus mindkét verzióban egyszerűen leáll, ha nem található elérési út. A gyakorlati megvalósítások speciális kezelést igényelhetnek ebben a helyzetben.
The Greedy Best-First Search
A mohó algoritmus használatával a szülők első gyermeke bővül. Gyermekek létrehozása után [3] :
- Ha a gyermek heurisztikus pontszáma jobb, mint a szülőé, a gyermek a sor elejére kerül (a szülők ismét közvetlenül mögötte), és a hurok újraindul.
- Ellenkező esetben a gyermek sorba kerül (a heurisztikus költsége által meghatározott helyen). Ezt követően a szülő többi örökösét (ha van ilyen) értékelik.
Jegyzetek
- ↑ Pearl J. Heuristics: Intelligens keresési stratégiák számítógépes problémamegoldáshoz. - Addison-Wesley, 1984. - S. 48.
- ↑ 1 2 Russell SJ, Norvig P. Artificial Intelligence: A Modern Approach . — 2. - Upper Saddle River, New Jersey: Prentice Hall, 2003. - 94-95. o. (3. jegyzet). — 1132 p. — ISBN 0-13-790395-2 . .
- ↑ Greedy Best-First Search, amikor az EHC meghiúsul Archiválva : 2010. június 11. a Wayback Machine -nél , Carnegie Mellon.
Linkek
- Wikikönyvek: Mesterséges intelligencia: Legjobb első keresés
| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||