un pas de la algoritmul lui Dijkstra este un* (citiți: „o stea”). În ceea ce privește găsirea căii, algoritmul lui Dijkstra va dori să încerce fiecare cale și fiecare vârf pentru a găsi calea cea mai scurtă între punctul său de plecare și destinație, în timp ce A* are un atribut suplimentar, o euristică, care ar trebui să-i permită să găsească calea cea mai scurtă fără a fi nevoie să verifice fiecare cale și vârf. Fiecare algoritm are cazurile sale de utilizare, dar, în general, atât Dijkstra, cât și A* pot găsi cea mai scurtă cale, dar a* o va face mai repede.

aș recomanda să știți puțin despre algoritmul lui Dijkstra înainte de a intra în acest articol, deoarece există o mulțime de puncte de comparație. Sau mai bine, citiți ultimul meu articol pe această temă! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

va trebui să configurez câteva lucruri pentru exemplele mele, plus să dau o definiție a ceea ce este o euristică. Pentru început, permiteți-mi să vă arăt tipul de grafic pe care vreau să îl folosesc pentru exemplele mele.

cu greu un grafic. Mai mult o tablă de șah.

acesta este un pic abstract, dar vreau să folosesc o placă în carouri ca grafic și vreau să permit mișcarea între pătratele sale. Dacă suprapun graficul echivalent cu vârfuri și margini, ar trebui să arate cam așa.

asta e prea linii. Poate nu atât de util…

să luăm centrul pătrat/vertex, E, de exemplu. Are opt vârfuri vecine, astfel încât să ne putem deplasa în sus, în jos, la stânga, la dreapta și în toate combinațiile diagonale ale fiecăruia. Și asta e tot ce am încercat să configurez aici: voi folosi o tablă de șah și voi permite mișcarea în opt direcții. Un pic lung, dar acum să începem să ne uităm la mișcare și la costul mișcării.

începând simplu, voi spune că deplasarea în sus, în jos, la stânga și la dreapta are un cost de mișcare de 1. Placa devine ocupată, așa că voi extrage Graficul și voi adăuga acel Cost de mișcare ca greutăți de margine.

pentru că suntem pathfinding, ne putem gândi la aceste greutăți ca distanța.

dacă aceste greutăți sunt distanțe și dacă relațiile și vecinii sunt așezate astfel, atunci geometria ne poate spune despre costul mișcărilor diagonale. Folosind teoria pitagoreică, ar trebui să obținem √(12 + 12) = √2, Care este aproximativ 1.41421356237 … care nu este un număr foarte frumos pentru a lucra cu. Deci, voi fura o idee (și voi cita sursele mele!), și înmulțiți și rotunjiți costurile în jos. Pentru ambele tipuri de mișcare, le voi multiplica cu zece, apoi le voi trunchia zecimalele. Acest lucru ne va oferi costuri finale de 10 pentru mișcările sus, jos, stânga și dreapta și 14 pentru mișcările diagonale.

numere rotunde frumoase pentru tot. Acest lucru înseamnă, de asemenea, că efectuarea mișcărilor diagonale este mai ieftină decât efectuarea a două mișcări non-diagonale în același pătrat (10 + 10 > 14)

euristica

simt că acestea sunt dificil de definit, așa că voi începe cu linia de deschidere a Wikipedia pe această temă:

în informatică, inteligență artificială și optimizare matematică, o euristică (din greacă „I find, discover”) este o tehnică concepută pentru rezolvarea mai rapidă a unei probleme atunci când metodele clasice sunt prea lente sau pentru găsirea unei soluții aproximative atunci când metodele clasice nu reușesc să găsească nicio soluție exactă. Acest lucru se realizează prin tranzacționarea optimalității, completitudinii, preciziei sau preciziei pentru viteză. Într-un fel, poate fi considerată o scurtătură.

este util? Ai înțeles? Pentru că nu înțeleg. Adică, am cam înțeles, și este o descriere exactă, dar dacă aceasta a fost prima dată când ai auzit despre o euristică, nu sunt sigur că ai obține imaginea completă a ceea ce sunt euristicile din asta. Poate dacă ți-aș spune despre o euristică de căutare a pathfinding-ului, ai înțelege mai bine.

cu algoritmul lui Dijkstra, accentul a fost pus pe o singură valoare: cea mai scurtă distanță de indexul de pornire. Ceea ce, dacă stai să te gândești, e cam ciudat. Aveți acest algoritm care încearcă să găsească căi noi și mai scurte către o anumită destinație, dar accentul său este întotdeauna pe locul în care a început. Imaginați-vă că cineva iese la cumpărături, dar merge înapoi tot drumul, încercând să-și supravegheze casa până când ajung la magazin. În viața reală, acest lucru, probabil, nu ar funcționa, dar poate dacă le-ai dat timp pentru a merge peste tot orașul, s-ar putea lucra în cele din urmă.

plecând de la această analogie tâmpită, A* este diferită de cea a lui Dijkstra, deoarece sugerează întoarcerea și mersul înainte. A*, la fel ca Dijkstra, ține evidența cât de departe de casă este, dar caracteristica sa unică este că ține evidența cât de departe este de destinație, de asemenea. Când face următorul pas, Dijkstra va analiza care cale este în prezent cea mai scurtă, dar A* merge cu un pas mai departe și ia în considerare, de asemenea, dacă acel pas îl apropie de obiectivul său. Mai simplu, A * are o estimare aproximativă a distanței rămase până la obiectivul său, iar atunci când această estimare se apropie de zero, știe că se mișcă în direcția cea bună. Aceasta este euristica pe care o vom folosi în exemplele noastre.

trecerea prin algoritm

acesta va fi un exemplu destul de simplu, dar ar trebui să vă arate fluxul de bază și repetarea algoritmului. Voi asigurați-vă că pentru a oferi link-uri în referințele mele la alte exemple, mai complicate, dar acest lucru ar trebui să fie un primer bun pentru cei. Voi folosi un set-up similar cu modul în care am demonstrat lui Dijkstra.

încă o diferență între Dijkstra și A* este că Dijkstra începe să se bucleze imediat, dar A* trebuie să facă o mică configurare pentru vârful său de pornire. Să facem asta acum și să ne facem o idee despre cum va funcționa masa.

în primul rând, vom adăuga A la setul deschis. În al doilea rând, ne vom da seama de distanța lui A de la început. Firește, distanța de la A la A este zero, astfel încât va fi adăugat la masă, și voi avea ca să fie numărul din colțul din stânga sus al pătrat A lui. În al treilea rând, vom determina distanța euristică. Putem face acest lucru în orice număr de moduri, tot ce este important este să măsurăm această distanță în același mod pentru fiecare pătrat. Voi folosi o distanță „cum zboară cioara” pentru toate distanțele euristice, ceea ce înseamnă că pot folosi din nou Teorema lui Pitagora. În acest caz, vom calcula un zecimal(202 + 302) și vom constata că A este o distanță de 36.0555127546… de la L (voi rotunji zecimalele la cea mai apropiată zecime pentru a economisi spațiu). Voi adăuga acest lucru la masă, și puneți-l în colțul din dreapta sus al pătrat A lui. În cele din urmă, suma. Voi adăuga cea mai scurtă distanță de la început la distanța euristică, o voi adăuga la masă și o voi așeza în centrul pătratului lui A.

acesta este punctul nostru de plecare, iar acum ne putem uita la vecinii lui A și le putem adăuga valorile în tabel.

mai întâi, vom adăuga B, E și F la setul deschis. Apoi, putem găsi cele mai scurte distanțe de la început și, pentru că totul este la un pas de la început, va fi doar 10 pentru B și E și 14 pentru deplasarea diagonală la F. Pentru distanța euristică, vom folosi teorema pitagoreică de la fiecare pătrat la vârful final. În cele din urmă, vom obține sumele lor și vom adăuga „A” la fiecare dintre coloanele lor de vârf anterioare.

în acest moment, am făcut tot ce ne trebuie cu A, deci va fi mutat în setul închis și vom avea nevoie de un nou nod curent. Pentru a determina ce vârf ar trebui examinat în continuare, vom analiza setul deschis și vom găsi vârful care are cea mai mică sumă. Chiar acum, care este F cu o sumă de 36.1. Deci, vom face vertexul curent și vom începe să elaborăm valorile pentru vecinii săi.

f are opt vecini, dar doar cinci vor fi schimbate aici. În primul rând, A este în setul închis acum, deci nu poate fi schimbat acum. Pentru restul de șapte, le vom adăuga la setul deschis (cu excepția cazului în care fac deja parte din el) și apoi să lucrăm la distanțele lor de la început. Acest lucru va funcționa foarte mult ca algoritmul lui Dijikstra și vom adăuga distanța lui F de la început la distanța fiecărui vecin de la F. Pe masa noastră, Distanța lui F de la început este 14, așa că vom completa 14+10=24 sau 14+14=28 pentru acestea. Cu toate acestea, B și E au deja distanțe mai mici până la început, astfel încât înregistrările lor de tabel nu se actualizează. Asta lasă cinci vârfuri care vor fi actualizate, C, I și K obținând 28, iar G și J obținând 24 pentru distanța lor de la început. Apoi, utilizați teorema lui Pitagora pentru fiecare dintre distanțele euristice ale acestor vârfuri, apoi calculați sumele acestora și, în final, adăugați „F” la coloana anterioară a vârfurilor pentru vârfurile care au fost actualizate.

F este complet și va fi mutat în setul închis, iar un nou nod curent va fi ales pe baza nodului din setul deschis care are cea mai mică sumă. Este foarte aproape, dar K este cu o zecime mai mică (și da, acest lucru se datorează unei diferențe de rotunjire, dar în acest caz, se dovedește a fi un bun tie breaker). K va fi noul vârf de examinat, așa că să începem prin a ne uita la vecinii săi.

k are șase vecini, dintre care trei sunt deja în setul deschis, astfel încât ultimele două h și l vor fi adăugate și la setul deschis. Acum, vom calcula distanțele lor de la început. Distanța lui K de la început este 28, deci vom lucra cu 28+10=38 pentru G, J și L și 28 + 14=42 pentru H. Cu toate acestea, G și J au deja distanțe mai mici pentru a începe, deci nu vor fi actualizate. Vom găsi distanțele euristice pentru fiecare, le vom calcula sumele și vom adăuga „K” la fiecare vârf anterior care a fost actualizat.

K este complet și mutat la setul închis, iar următorul vârf în aer liber cu cea mai mică sumă este L, destinația noastră!

acum, că l este vertexul curent, algoritmul se termină și putem folosi tabelul nostru pentru a urmări calea înapoi la început:

• vertexul anterior al lui L este k
• vertexul anterior al lui K este f
• F’ vertexul anterior este a, vertexul de pornire.

deci, aceasta înseamnă că cea mai scurtă cale este un> F> K> L.

analizând rezultatele

în comparație cu algoritmul lui Dijkstra, A* a lăsat destul de multă mizerie în spatele ei. Să ne uităm la câteva puncte ciudate. Începând, uitați-vă la vârful C și la distanța sa până la început: 28. Acest lucru pare ciudat, deoarece A și C sunt la doar două mișcări orizontale una de cealaltă, deci cea mai scurtă distanță ar trebui să fie 20. Chiar acum, C pare să creadă că cea mai scurtă cale către A este de două mișcări diagonale prin F.

când algoritmul lui Dijkstra se termină, ar trebui să ofere un tabel foarte complet al distanțelor de la punctul de plecare. În schimb, tabelul A*are valori greșite și lipsește complet vertex D. dar a primit același răspuns pe care l-ar avea Dijkstra și a făcut-o mult mai repede. Dijkstra ar fi vrut să se uite la toate cele 12 noduri înainte de a declara că a găsit calea cea mai scurtă; A* trebuia doar să se uite la 4 înainte de a găsi calea cea bună. Această schimbare de viteză se datorează euristicii pe care o foloseam: de câte ori am putut, am vrut să închidem distanța cu destinația noastră. Dacă ne întoarcem la definiția Wikipedia pentru euristică, A* a schimbat completitudinea pentru viteză.

să încercăm un alt exemplu mic, dar cu o obstrucție pe drumul spre destinație.

punctul de plecare este vârful din stânga sus, iar A* încearcă să găsească cea mai scurtă cale către vârful din dreapta jos. Pătratele negre reprezintă un decalaj în grafic și nu pot fi traversate. Dacă A * își urmează euristica „întotdeauna apropiați-vă de destinație”, acele pătrate negre o vor duce într-o fundătură.

în acest moment, a* va căuta cele mai mici sume, care vor fi pătratele chiar sub și în dreapta vertexului de pornire. A * va explora ambele căi, dar calea descendentă va rula într-o altă fundătură, și calea spre dreapta va găsi o cale în jurul pătrate negre. S-ar putea juca un pic diferit decât acest lucru, dar să presupunem că acest lucru este modul în care un* manipulat acest scenariu. Chiar și atunci când a fost tras în fundături, a fost capabil să se întoarcă și să găsească o altă cale și nu a fost nevoie să se uite la fiecare vârf (vârful din dreapta sus a fost omis din nou). Aceasta înseamnă că atunci când o stea * rulează la cel mai rău absolut, este practic la fel de rapidă ca performanța normală a lui Dijkstra. Fiecare algoritm are cazuri de Utilizare perfect valide, dar în ceea ce privește găsirea și găsirea celor mai scurte căi, A* este cea mai bună alegere.