egy lépés Dijkstra algoritmusától a* (olvassa el: “egy csillag”). Az útvonalkeresés szempontjából a Dijkstra algoritmusa minden utat és minden csúcsot ki akar próbálni, hogy megtalálja a legrövidebb utat a kiindulási pont és a cél között, míg az A* – nak van egy extra tulajdonsága, egy heurisztikus, amely lehetővé teszi, hogy megtalálja a legrövidebb utat anélkül, hogy minden utat és csúcsot ellenőriznie kellene. Minden algoritmusnak megvannak a maga Felhasználási esetei, de általánosságban elmondható, hogy mind a Dijkstra, mind az A* megtalálja a legrövidebb utat, de a* gyorsabban fogja megtenni.
azt javaslom, hogy ismerjen egy kicsit a Dijkstra algoritmusáról, mielőtt belemenne ebbe a cikkbe, mivel sok összehasonlítási pont van. Vagy még jobb, olvassa el a témáról szóló utolsó cikkemet! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629
be kell állítanom néhány dolgot a példáimhoz, plusz meg kell adnom annak meghatározását, hogy mi a heurisztika. Először hadd mutassam meg, hogy milyen típusú grafikont szeretnék használni a példáimhoz.
Ez egy kicsit absztrakt, de kockás táblát szeretnék használni grafikonomként, és lehetővé akarom tenni a négyzetek közötti mozgást. Ha átfedem az ekvivalens gráfot csúcsokkal és élekkel, akkor valahogy így kell kinéznie.
vegyük például a középső négyzetet/csúcsot, E-t. Nyolc szomszédos csúcsa van, így fel, le, balra, jobbra és mindegyik átlós kombinációjában mozoghatunk. És ez minden, amit itt próbáltam beállítani: egy sakktáblát fogok használni, és nyolc irányba engedem a mozgást. Egy kicsit hosszú szélű, de most kezdjük el a mozgást és a mozgás költségeit.
kezdve egyszerű, azt mondom, hogy a felfelé, lefelé, balra és jobbra mozgatás költsége 1. A tábla kezd elfoglalt lenni, ezért kivonom a grafikont, és hozzáadom a mozgás költségét élsúlyként.
távolság.
Ha ezek a súlyok távolságok, és ha a kapcsolatok és a szomszédok így vannak elrendezve, akkor a geometria elmondhatja nekünk az átlós mozgások költségeit. A Pythagorean Theorum használatával meg kell szereznünk √(12 + 12) = √2, ami nagyjából 1.41421356237 … ami nem túl szép szám dolgozni. Tehát ellopok egy ötletet (és idézem a forrásaimat!), és szorozzuk meg és kerekítsük le a költségeket. Mindkét típusú mozgás esetén tízszeresére szorozom őket, majd csonkolom a tizedesjegyüket. Ez 10-et ad nekünk a felfelé, lefelé, balra és jobbra, és 14-et az átlós mozgásokra.
heurisztika
úgy érzem, hogy ezeket nehéz meghatároznom, ezért a Wikipedia nyitó sorával kezdem a témát:
a számítástechnikában, a mesterséges intelligenciában és a matematikai optimalizálásban a heurisztika (görögül:” megtalálom, felfedezem”) egy olyan technika, amelyet egy probléma gyorsabb megoldására terveztek, ha a klasszikus módszerek túl lassúak, vagy hozzávetőleges megoldás megtalálására, ha a klasszikus módszerek nem találnak pontos megoldást. Ezt úgy érjük el, kereskedési optimalitás, teljesség, pontosság, vagy pontosság sebesség. Bizonyos értelemben ez egy parancsikonnak tekinthető.
hasznos ez? Érted már? Mert nem értem. Értem, és ez egy pontos leírás, de ha ez lenne az első, amit heurisztikáról hallottál, nem vagyok biztos benne, hogy ebből teljes képet kapnál arról, hogy mi a heurisztika. Talán ha mesélnék neked egy útkereső heurisztikáról, jobban megértenéd.
Dijkstra algoritmusával a hangsúly egy értékre összpontosult: a kezdő Indextől a legrövidebb távolságra. Ami, ha belegondolsz, elég furcsa. Ez az algoritmus megpróbál új, rövidebb utakat találni valamilyen célállomáshoz, de a hangsúly mindig arra irányul, hogy hol kezdődött. Képzelje el, hogy valaki elmegy élelmiszerért, de egész úton hátrafelé sétál, megpróbálja szemmel tartani az otthonát, amíg el nem ér a boltba. A való életben, ez valószínűleg nem működne, de talán ha időt adna nekik, hogy bejárják a várost, végül működhet.
ezt az ostoba analógiát követve az a* eltér a Dijkstra-tól, mert azt sugallja, hogy megfordul és előre halad. A*, mint a Dijkstra, azt is nyomon követi, hogy milyen messze van az otthontól, de egyedülálló tulajdonsága, hogy nyomon követi, hogy milyen messze van a rendeltetési helyétől is. A következő lépés megtételekor a Dijkstra megvizsgálja, hogy melyik út jelenleg a legrövidebb, de A* egy lépéssel tovább megy, és azt is megvizsgálja, hogy ez a lépés közelebb hozza-e a céljához. Egyszerűbben: az A* – nak van egy durva becslése a céltól való hátralévő távolságáról, és amikor ez a becslés közelebb kerül a nullához, tudja, hogy a helyes irányba halad. Ezt a heurisztikát fogjuk használni a példáinkban.
az algoritmus átlépése
Ez egy meglehetősen egyszerű példa lesz, de meg kell mutatnia az algoritmus alapvető áramlását és ismétlését. Gondoskodom arról, hogy hivatkozásaimban hivatkozásokat nyújtsak másokra, bonyolultabb példák, de ennek jó alapozónak kell lennie azok számára.
még egy különbség a Dijkstra és az A* között, hogy a Dijkstra-nak azonnal el kell kezdenie a hurkolást, de A* – nak egy kis beállítást kell tennie a kezdő csúcsához. Tegyük ezt meg most, és kapjunk egy kis képet arról, hogyan fog működni az asztal.
először hozzáadunk egy-t a nyitott készlethez. Másodszor, kitaláljuk az A távolságát a kezdetektől. Természetesen az A-tól A-ig terjedő távolság nulla, tehát ez hozzáadódik az asztalhoz, és ez lesz a szám az A négyzet bal felső sarkában. Harmadszor, meghatározzuk a heurisztikus távolságot. Ezt tetszőleges számú módon megtehetjük, csak az a fontos, hogy ezt a távolságot minden négyzetre ugyanúgy mérjük. “Ahogy a varjú repül” távolságot fogok használni az összes heurisztikus távolságra, ami azt jelenti, hogy újra felhasználhatom a Pitagorasz-tételt. Ebben az esetben kiszámítjuk a(202 + 302), és megállapítjuk, hogy A távolság 36,0555127546… L-től (tizedesjegyeket kerekítek a legközelebbi tizedig, hogy helyet takarítsak meg). Ezt hozzáadom az asztalhoz, és az A négyzet jobb felső sarkába helyezem. Végül az összeg. Hozzáadom a legrövidebb távolságot az elejétől a heurisztikus távolságig, hozzáadom az asztalhoz, és az A négyzet közepére helyezem.
Ez a kiindulópontunk, és most megnézhetjük A szomszédait, és hozzáadhatjuk értékeiket a táblázathoz.
először hozzáadjuk a B, E és F értéket a nyitott készlethez. Ezután megtalálhatjuk a legrövidebb távolságokat a kezdetektől, és mivel minden egy lépés a kezdetektől, csak 10-es lesz a B és E, és 14 az átlós lépés f-re.a heurisztikus távolsághoz a Pitagorasz-tételt használjuk minden négyzettől a végcsúcsig. Végül megkapjuk az összegeket, és hozzáadjuk az “A” – t minden korábbi csúcsoszlopukhoz.
Ezen a ponton mindent megtettünk az A-val, így átkerül a zárt halmazba, és szükségünk lesz egy új aktuális csúcsra. Annak meghatározásához, hogy melyik csúcsot kell megvizsgálni, megnézzük a nyitott halmazt, és megtaláljuk azt a csúcsot, amelynek a legalacsonyabb összege van. Jelenleg ez F, 36,1 összeggel. Szóval, ez lesz a jelenlegi csúcs, és elkezdjük kidolgozni a szomszédok értékeit.
f-nek nyolc szomszédja van, de itt csak öt fog változni. Először is, A van a zárt készlet most, így nem lehet megváltoztatni most. A fennmaradó héthez hozzáadjuk őket a nyitott készlethez (kivéve, ha már részei), majd dolgozzunk a távolságukon a kezdetektől. Ez nagyon hasonlóan fog működni, mint a Dijikstra algoritmusa, és hozzá fogjuk adni F távolságát az elejétől az egyes szomszédok F-től való távolságához. az asztalunkon F távolsága az elejétől 14, tehát ezekre 14+10=24 vagy 14+14=28 lesz kitöltve. A B és E azonban már rövidebb távolsággal rendelkezik a rajtig, így az asztalrekordjaik nem frissülnek. Ez öt csúcsot hagy, amelyek frissülnek, a C, I és K 28-at, a G és J pedig 24-et kap a kezdetektől való távolságukra. Ezután használja a Pitagorasz-tételt ezeknek a csúcsoknak a heurisztikus távolságaira, majd kiszámítja azok összegét, majd végül hozzáadja az “F” – et az előző csúcsoszlophoz a frissített csúcsokhoz.
f teljes, és a zárt halmazba kerül, és egy új aktuális csúcs kerül kiválasztásra, amely alapján a nyitott halmaz csúcsának a legalacsonyabb összege van. Nagyon közel van, de k egy tizeddel kisebb (és igen, ez a kerekítési különbség miatt van, de ebben az esetben kiderül, hogy jó nyakkendő-megszakító). K lesz az új csúcs, amelyet meg kell vizsgálni, Tehát kezdjük azzal, hogy megnézzük a szomszédait.
k-nak hat szomszédja van, amelyek közül három már a nyitott halmazban van, így az utolsó két h és l is hozzáadódik a nyitott halmazhoz. Most kiszámoljuk a távolságukat a kezdetektől. K távolsága az indulástól 28, tehát 28+10=38-mal fogunk dolgozni G, J és L esetén, és 28+14=42-vel H esetén.azonban G és J már kisebb távolságok vannak az induláshoz, így nem lesznek frissítve. Megtaláljuk az egyes heurisztikus távolságokat, kiszámítjuk az összegüket, és hozzáadunk “K” – t minden korábbi csúcshoz, amelyet frissítettünk.
K elkészült, és átkerült a zárt halmazba, és a következő csúcs a szabadban a legkisebb összeggel L, a rendeltetési helyünk!
most, hogy l az aktuális csúcs, az algoritmus véget ér, és a táblázatunkkal nyomon követhetjük az utat a kezdetig:
- l előző csúcsa k
- k előző csúcsa F
- F’ az előző csúcs a, A kezdő csúcs.
tehát ez azt jelenti, hogy a legrövidebb út egy > F > K > L.
az eredmények elemzése
Dijkstra algoritmusához képest az A* meglehetősen rendetlenséget hagyott maga után. Nézzünk meg néhány furcsa pontot. Induláskor nézzük meg a C csúcsot és annak távolságát a starttól: 28. Ez furcsának tűnik, mert a és C csak két vízszintes lépés távolságra van egymástól, így a legrövidebb távolság 20. Jelenleg úgy tűnik, hogy C úgy gondolja, hogy a legrövidebb útja az A-hoz két átlós lépés az F-en keresztül.
amikor Dijkstra algoritmusa befejeződik, nagyon teljes táblázatot kell adnia a kiindulási ponttól való távolságokról. Ezzel szemben az a*táblának rossz értékei vannak, és teljesen hiányzik a D csúcs, de ugyanazt a választ kapta, mint Dijkstra, és sokkal gyorsabban tette. Dijkstra szerette volna megnézni mind a 12 csúcsot, mielőtt kijelentette, hogy megtalálta a legrövidebb utat; a* csak 4-et kellett megnéznie, mielőtt megtalálta a helyes utat. Ez a sebességváltozás annak a heurisztikának köszönhető, amelyet használtunk: amilyen gyakran csak tudtunk, azt akartuk, hogy lezárjuk a távolságot a rendeltetési helyünkkel. Ha visszatérünk a Wikipedia heurisztika definíciójához, az A* a teljességet a sebességre cserélte.
próbáljunk meg egy másik kis példát, de akadályokkal a cél felé vezető úton.
kiindulási pont a bal felső csúcs, a* pedig megpróbálja megtalálni a legrövidebb utat a jobb alsó csúcshoz. A fekete négyzetek egy rést jelentenek a gráfban, és nem lehet áthaladni. Ha A * követi a heurisztikáját: “mindig közelebb kerülj a célhoz”, akkor ezek a fekete négyzetek zsákutcába vezetik.
ezen a ponton az a* A legkisebb összegeket fogja keresni, amelyek a kezdő csúcstól közvetlenül alatta és jobbra lévő négyzetek lesznek. Az A * mindkét utat felfedezi, de a lefelé vezető út egy másik zsákutcába fut, a jobb oldali út pedig utat talál a fekete négyzetek körül. Lehet, hogy kicsit másképp játszik, mint ez, de tegyük fel, hogy A* így kezelte ezt a forgatókönyvet. Még akkor is, ha zsákutcába került, képes volt visszamenni, és más utat találni, és nem kellett minden csúcsot megnéznie (a jobb felső csúcsot ismét átugorták). Ez azt jelenti, hogy amikor egy* csillag fut az abszolút legrosszabb, ez alapvetően olyan gyors, mint Dijkstra normál teljesítményét. Minden algoritmusnak tökéletesen érvényes Felhasználási esetei vannak, de az útkeresés és a legrövidebb utak megtalálása szempontjából az A* A jobb választás.