Tájékozott keresési módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. június 29-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A tájékozott keresés (a heurisztikus keresés is , eng. informed search  , heurisztikus keresés ) az állapottérben történő megoldáskeresés stratégiája , amely egy adott feladathoz kapcsolódó tudást használ fel. A tájékozott módszerek általában hatékonyabb keresést tesznek lehetővé, mint a tájékozatlan módszerek .

Az adott feladattal kapcsolatos információk heurisztikus függvényként vannak megfogalmazva . A heurisztikus függvény a keresés minden lépésében további információk alapján kiértékeli az alternatívákat, hogy eldöntse, milyen irányban folytassa a keresést [1] .

Heurisztikus függvények

Az állapottér kereséssel összefüggésben a h ( n ) heurisztikus függvényt az iterációs fa csomópontjain a következőképpen definiáljuk :  

h ( n ) = az n csomóponttól a célcsomópontig vezető legolcsóbb út költségbecslése .

Ha n  a célcsomópont, akkor h ( n ) = 0.

A telepítendő csomópont kiválasztása az értékelési függvény alapján történik 

f ( n ) = az n csomóponton áthaladó legolcsóbb megoldási útvonal költségbecslése , f ( n ) = g ( n ) + h ( n ),

ahol a g ( n ) függvény határozza meg a kezdő csomóponttól az n csomópontig már megtett út költségét .

Ha a h ( n ) heurisztikus függvény soha nem becsüli túl a cél elérésének tényleges minimális költségét (vagyis a tényleges költség alacsonyabb becslése), akkor egy ilyen függvényt megengedhetőnek nevezünk . 

Ha a h ( n ) heurisztikus függvény kielégíti a feltételt

h ( a ) ≤ költség ( a , b ) + h ( b ),

ahol b az a  leszármazottja , akkor az ilyen függvényt szukcesszívnek nevezzük ( angol  konzisztens ).

Ha f ( n ) = g ( n ) + h ( n ) a kiértékelő függvény, h ( n ) az utódfüggvény, akkor az f ( n ) függvény monoton nem csökkenő bármely vizsgált út mentén. Ezért az egymást követő függvényeket monotonnak is nevezik ( eng.  monoton ).

Bármely utódfunkció elfogadható, de nem minden megengedett funkció utódja.

Ha h 1 ( n ), h 2 ( n ) érvényes heurisztikus függvények, és bármely n csomópontra igaz a h 1 ( n ) ≥ h 2 ( n ) egyenlőtlenség , akkor h 1 tájékozottabb heurisztika, vagy uralja h 2 .

Ha a probléma elfogadható h 1 és h 2 heurisztikával rendelkezik, akkor a h ( n ) = max( h 1 , h 2 ) heurisztika megengedett, és dominál az eredeti heurisztikák mindegyike felett [1] [2] .

Heurisztikus függvények összehasonlítása

A megengedett heurisztikák összehasonlításakor a tudatosság foka, valamint az egyes heurisztikák számításának térbeli és időbeli összetettsége számít. A tájékozottabb heurisztika csökkentheti a telepített csomópontok számát, bár ennek költsége lehet az az idő, amelybe az egyes csomópontokhoz szükséges heurisztika kiszámítása szükséges.

Az effektív elágazási tényező a csomópontutódok átlagos száma a  felsorolásfában a heurisztikus metszésmódok alkalmazása után [1] [2] . Az effektív elágazási tényező alapján meg lehet ítélni a használt heurisztikus függvény minőségét.

Egy ideális heurisztikus függvény (például egy keresőtábla ) mindig pontos értékeket ad vissza a legrövidebb megoldás hosszához, így a felsorolási fa csak optimális megoldásokat tartalmaz. Egy ideális heurisztikus függvény effektív elágazási tényezője közel 1 [1] .

Példák keresési feladatokra

A keresési algoritmusok és heurisztikus függvények tesztelésének modelljeként gyakran használnak permutációs rejtvényeket  - Tizenöt 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [ 10 ] , 6×6 [11] , Rubik-kocka [9] [12] , Hanoi tornya négy rúddal [11] [13] .

A „Tizenöt” feladványban a Manhattan távolságon alapuló h m heurisztika alkalmazható . Pontosabban, minden lapkára kiszámítják a Manhattan távolságot az aktuális pozíciója és a kezdeti pozíciója között; a kapott értékeket összegzik.

Megmutatható, hogy ez a heurisztika megengedhető és szukcessziós: értéke nem változhat ±1-nél nagyobb mértékben egy mozdulattal.

Heurisztikus függvények felépítése

Nyugodt feladat

A "Tizenöt" rejtvény megoldásához használt h m heurisztikus függvény az optimális megoldás hosszának alacsonyabb becslése. Ezenkívül h m ( n ) a rejtvény egyszerűsített változatának optimális megoldásának pontos hossza, amelyben a lapkák a helyükre mozgathatók. Az eredeti rejtvényben van egy korlátozás: "egy cellában ne legyen két vagy több lapka", ami az egyszerűsített változatban nem szerepel. Az olyan problémát, amelynél kevesebb korlátozás van a lehetséges cselekvésekre vonatkozóan , laza problémának nevezzük ; a relaxált probléma megoldásának költsége érvényes heurisztika az eredeti feladatra [1] , mivel az eredeti probléma bármely megoldása a relaxált probléma megoldása is egyben.  

Részfeladat

Az elfogadható heurisztika alapulhat az eredeti probléma egy részprobléma megoldásának költségén  . A főprobléma bármely megoldása egyben megoldást jelent minden részfeladatára [1] .

A „Tizenöt” rejtvény megoldási feladatának egy részfeladata lehet az 1., 2., 3. és 4. lapkák helyére való mozgatása, ennek a részprobléma megoldásának költsége az eredeti feladatra érvényes heurisztika.

Sablon adatbázisok

A mintaadatbázisok [ 1] egyfajta  érvényes heurisztika, amely azon az elgondoláson alapul, hogy egy részprobléma minden lehetséges példányához eltárolják a megoldási költség pontos értékét [1] [6] [12] .

A "Tizenöt" rejtvény sablonjára a jobb oldali ábra látható: a részfeladat definíciója tartalmazza az első oszlopban és az első sorban található hét zseton pozícióit. A sablon konfigurációinak száma . Mindegyik konfiguráció esetében az adatbázis tartalmazza a minimális számú lépést, amely szükséges ahhoz, hogy ezt a konfigurációt az ábrán látható részfeladat célkonfigurációjává lehessen fordítani. Az adatbázis a fordított szélesség keresési módszerrel [2] [6] épül fel .

Keresési algoritmusok

Keresés az első legjobb találat alapján

A legjobb első keresés egy olyan megközelítés, amelyben a telepítendő csomópontot egy f ( n ) kiértékelő függvény alapján választják ki .  A legalacsonyabb pontszámmal rendelkező csomópont kerül kiválasztásra a telepítéshez.

Keresés A*

Az A* keresés  az első legjobb találat keresésének legismertebb típusa. Az n csomóponton keresztül a legolcsóbb megoldási útvonal f ( n ) becslését használja :

f ( n ) = g ( n ) + h ( n ), ahol g ( n ) a kezdő csomóponttól az n csomópontig vezető út költsége , h ( n ) az n csomóponttól a célig vezető út költségének becslése .

Ha h ( n ) soha nem becsüli túl a cél elérésének költségét (vagyis megfizethető), akkor az A* keresése optimális.

IDA*

Az A* algoritmus iteratív elmélyítéssel A* ( IDA* ) az iteratív elmélyítés gondolatának alkalmazása a heurisztikus keresés kontextusában.

A tájékozatlan iteratív mélyítési algoritmus leállítja a bővítést, ha a d keresési mélység meghaladja az aktuális l mélységhatárt . A tájékozott IDA* algoritmus leállítja a telepítést, ha az aktuális n csomóponton keresztüli útköltség becsült f (n) értéke meghaladja az aktuális útköltség - korlátot .

Az IDA* algoritmust az A*-hoz képest minimális memória többletterhelés és az IDDFS-hez képest viszonylag kis számú telepített csomópont (a heurisztika sikeres megválasztása esetén) jellemzi.

Pszeudokód

[tizennégy]

csomópont jelenlegi g csomópont költsége a megoldás elindításához gyökér..f csomópont minimális útköltség becslés a csomóponton keresztül h ( csomópont ) heurisztikus költségbecslés az útvonal csomópont fennmaradó részére..cél költség ( csomópont , succ ) útköltség függvény is_goal ( csomópont ) cél függvény utódainak ellenőrzése ( csomópont ) csomópont telepítési funkciója eljárás ida_star ( root , cost (), is_goal (), h ()) bound  := h ( root ) ciklus t  := search ( root , 0, bound ) if t = FOUND then return FOUND if t = ∞ then return NOT_FOUND kötött  := t end ciklusvég eljárás függvény keresés ( csomópont , g , kötött ) f  := g + h ( csomópont ) ha f > kötött then return f if is_goal ( node ) then return FOUND min  := ∞ for succ in utódokban ( csomópont ) do t  := search ( succ , g + költség ( csomópont , succ ), kötött ) ha t = TALÁLT , akkor visszatér TALÁLT ha t < min , akkor min  := t vége a return min vége függvényhez

MA*

SMA*

SMA  *

RBFS

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 5 6 7 8 Stuart Russell, Peter Norvig. Megengedhető heurisztikus függvények összeállítása // Artificial Intelligence: a modern approach = Artificial Intelligence: A Modern Approach. - 2. kiadás - M . : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .
  2. ↑ 1 2 3 Stefan Edelkamp, ​​​​Stefan Schrödl. Heurisztikus keresés: elmélet és alkalmazások. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
  3. ↑ Alexander Reinfeld. A Nyolcas Rejtvény teljes megoldása és a csomópont-rendezés előnyei az IDA*-ban. – 1993.
  4. ↑ Daniel R. Kunkle. A 8 rejtvény megoldása minimális mozdulatszámmal: Az A* algoritmus alkalmazása. – 2001.
  5. ↑ Richard E. Korf. Mélység-első iteratív-mélyítés: Optimálisan elfogadható fakeresés. – 1985.
  6. ↑ 1 2 3 4 Joseph C. Culberson, Jonathan Schaeffer. Mintaadatbázisok. – 1998.
  7. ↑ Richard E. Korf, Peter Schultze. Nagyszabású párhuzamos szélesség – első keresés. – 2005.
  8. ↑ Richard E. Korf, Larry A. Taylor. Optimális megoldások keresése a huszonnégy rejtvényre . – 1996.
  9. ↑ 1 2 Richard E. Korf. Legutóbbi fejlődés az elfogadható heurisztikus függvények tervezésében és elemzésében. – 2000.
  10. ↑ Richard E. Korf, Ariel Felner. Disjunkt Pattern Database heuristics . – 2002.
  11. ↑ 1 2 Ariel Felner, Richard E. Korf, Sarit Hanan. Additív minta adatbázis-heurisztika . – 2004.
  12. ↑ 1 2 Richard E. Korf. Optimális megoldások keresése a Rubik-kockára mintaadatbázisok segítségével. – 1997.
  13. ↑ Richard E. Korf, Ariel Felner. A heurisztikus keresés közelmúltbeli fejlődése: esettanulmány a hanoi négycsapos tornyok problémájáról. – 2007.
  14. ↑ Előadásjegyzetek alapján : IDA* Archivált 2012. június 22-én a Wayback Machine -nél

Irodalom

  • Stefan Edelkamp, ​​Stefan Schrödl. Heurisztikus keresés: elmélet és alkalmazások. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
  • Stuart Russell, Peter Norvig. Megengedhető heurisztikus függvények összeállítása // Artificial Intelligence: a modern approach = Artificial Intelligence: A Modern Approach. - 2. kiadás - M . : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .

Linkek

 Grafikon keresési algoritmusok
Tájékozatlan módszerek
Tájékozott módszerek
Parancsikonok
Minimálisan átívelő fa
Egyéb