ett steg upp från Dijkstras algoritm är en* (läs: ”en stjärna”). När det gäller pathfinding vill Dijkstras algoritm prova varje väg och varje toppunkt för att hitta den kortaste vägen mellan startpunkten och destinationen, medan A* har ett extra attribut, en heuristisk, som borde göra det möjligt att hitta den kortaste vägen utan att behöva kontrollera varje väg och toppunkt. Varje algoritm har sina användningsfall, men generellt sett kan både Dijkstra och A* hitta den kortaste vägen, men A* kommer att göra det snabbare.

Jag skulle rekommendera att veta lite om Dijkstras algoritm innan du går in i den här artikeln, eftersom det finns många jämförelsepunkter. Eller ännu bättre, läs min senaste artikel om ämnet! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

Jag kommer att behöva ställa in några saker för mina exempel, plus ge en definition av vad en heuristisk är. För att börja, låt mig visa dig vilken typ av graf jag vill använda för mina exempel.

detta är lite abstrakt, men jag vill använda ett rutigt bräde som mitt diagram och jag vill tillåta rörelse mellan dess rutor. Om jag lägger över motsvarande graf med hörn och kanter, ska det se ut så här.

låt oss ta mittfältet/vertexen, E, till exempel. Den har åtta angränsande hörn, så vi kan flytta upp, ner, vänster, höger och i alla diagonala kombinationer av varje. Och det är verkligen allt jag försökte ställa upp här: Jag kommer att använda en schackbräda, och jag tillåter rörelse i åtta riktningar. Lite långvarig, men nu ska vi börja titta på rörelse och kostnaden för rörelse.

börja enkelt, jag säger att flytta upp, ner, vänster och höger har en rörelsekostnad på 1. Styrelsen blir upptagen, så jag ska extrahera grafen och lägga till den rörelsekostnaden som kantvikter.

om dessa vikter är Avstånd, och om relationerna och grannarna läggs ut så här, kan geometri berätta om kostnaden för diagonala rörelser. Med hjälp av Pythagorean Theorum borde vi få √(12 + 12) = √2, vilket är ungefär 1.41421356237 … vilket inte är ett mycket trevligt nummer att arbeta med. Så jag ska stjäla en IDE (och citera mina källor!), och multiplicera och runda kostnaderna ner. För båda typerna av rörelse, Jag ska flera dem med tio, och sedan trunkera deras decimaler. Detta ger oss slutliga kostnader på 10 för upp, ner, vänster och höger rörelser och 14 för diagonala rörelser.

heuristik

Jag känner att dessa är svåra för mig att definiera, så jag börjar med Wikipedias öppningsrad om ämnet:

i datavetenskap, artificiell intelligens och matematisk optimering är en heuristisk (från grekiska” I find, discover”) en teknik som är utformad för att lösa ett problem snabbare när klassiska metoder är för långsamma eller för att hitta en ungefärlig lösning när klassiska metoder misslyckas med att hitta någon exakt lösning. Detta uppnås genom att handla optimalitet, fullständighet, noggrannhet eller precision för hastighet. På ett sätt kan det betraktas som en genväg.

är det användbart? Fattar du? För jag fattar inte. Jag menar, jag förstår det, och det är en korrekt beskrivning, men om det här var det första du någonsin hört talas om en heuristik, är jag inte säker på att du skulle få den fullständiga bilden av vad heuristik är från detta. Kanske om jag bara berättar om en*s pathfinding heuristic, får du ett bättre grepp.

med Dijkstras algoritm var fokus på ett värde: det kortaste avståndet från startindexet. Vilket, när du tänker på det, är lite konstigt. Du har den här algoritmen som försöker hitta nya, kortare vägar till någon destination, men fokus ligger alltid på var den började. Föreställ dig att någon går ut för matvaror, men går bakåt hela vägen och försöker hålla ett öga på sitt hem tills de kom till affären. I verkliga livet, detta förmodligen inte skulle fungera, men kanske om du gav dem tid att gå över hela stan, Det kan så småningom fungera.

går av den här fåniga analogin, a* skiljer sig från Dijkstra eftersom det föreslår att man vänder sig och går framåt. A*, som Dijkstra ’ s, håller också reda på hur långt hemifrån Det är, men dess unika funktion är att det håller reda på hur långt det är från sin destination också. När du gör nästa steg kommer Dijkstra att titta på vilken väg som för närvarande är kortast, Men A* går ett steg längre och överväger också om det steget flyttar det närmare sitt mål. Mer enkelt har A* en grov uppskattning av sitt återstående avstånd till sitt mål, och när den uppskattningen kommer närmare noll vet den att den rör sig i rätt riktning. Detta är den heuristiska vi kommer att använda i våra exempel.

steg genom algoritmen

detta kommer att vara ett ganska enkelt exempel, men det ska visa dig algoritmens grundläggande flöde och upprepning. Jag ska se till att ge länkar i mina referenser till andra, mer komplicerade exempel, men det borde vara en bra primer för dem. Jag använder en inställning som liknar hur jag demonstrerade Dijkstra.

en ytterligare skillnad mellan Dijkstra och A* är att Dijkstra får börja looping omedelbart, men A* måste göra en liten inställning för sitt startpunkt. Så låt oss göra det nu, och få lite av en uppfattning om hur bordet kommer att fungera.

först lägger vi till A i den öppna uppsättningen. För det andra kommer vi att räkna ut A: S avstånd från början. Naturligtvis är avståndet från A till A noll, så det kommer att läggas till i tabellen, och jag kommer att ha det numret i det övre vänstra hörnet av A: S kvadrat. För det tredje bestämmer vi det heuristiska avståndet. Vi kan göra detta valfritt antal sätt, allt som är viktigt är att vi mäter detta avstånd på samma sätt för varje kvadrat. Jag kommer att använda ett” som kråka flyger ” avstånd för alla heuristiska avstånd, vilket innebär att jag kan använda Pythagoras teorem igen. I det här fallet kommer vi att beräkna Xiaomi (202 + 302) och upptäcka att A är ett avstånd på 36.0555127546… från L (jag runda decimaler till närmaste tiondel för att spara utrymme). Jag lägger till detta i bordet och placerar det i det övre högra hörnet av A: s torg. Slutligen summan. Jag lägger till det kortaste avståndet från början till det heuristiska avståndet, lägger till det i bordet och placerar det i mitten av A: s torg.

det är vår utgångspunkt, och vi kan nu titta på A: S grannar och lägga till sina värden i tabellen.

först lägger vi till B, E och f i den öppna uppsättningen. Därefter kan vi hitta sina kortaste avstånd från början, och eftersom allt är ett steg från början kommer det bara att vara 10 för B och E och 14 för diagonalen till F. För det heuristiska avståndet använder vi Pythagoras teorem från varje kvadrat till slutpunkten. Slutligen får vi sina summor och lägger till ”A” till var och en av deras tidigare vertexkolumner.

Vid denna tidpunkt har vi gjort allt vi behöver med A, så det kommer att flyttas till den stängda uppsättningen, och vi behöver ett nytt aktuellt toppunkt. För att bestämma vilket vertex som ska undersökas nästa tittar vi på den öppna uppsättningen och hittar vertexen som har den lägsta summan. Just nu är det F med en summa av 36,1. Så vi gör det till det nuvarande vertexet och börjar träna värdena för sina grannar.

f har åtta grannar, men bara fem kommer att ändras här. För det första är A i den stängda uppsättningen nu, så det kan inte ändras nu. För de återstående sju lägger vi till dem i den öppna uppsättningen (såvida de inte redan är en del av det), och låt oss sedan arbeta på avstånd från början. Detta kommer att fungera mycket som Dijikstras algoritm, och vi lägger till F: S avstånd från början till var och en av grannarnas avstånd från F. på vårt bord är F: S avstånd från start 14, Så vi fyller i 14+10=24 eller 14+14=28 för dessa. B och E har dock redan kortare avstånd till början, så deras tabellposter uppdateras inte. Det lämnar fem hörn som kommer att uppdateras, med C, i, och K får 28, och G och J får 24 för deras avstånd från start. Använd sedan Pythagoras teorem för var och en av dessa hörn heuristiska avstånd, beräkna sedan deras summor och lägg slutligen till ”F” i föregående vertexkolumn för de hörn som uppdaterades.

F är klar och kommer att flyttas till den stängda uppsättningen, och ett nytt aktuellt toppunkt kommer att väljas baserat på vilket toppunkt i den öppna uppsättningen som har den lägsta summan. Det är väldigt nära, men K är en tiondel mindre (och ja, det här beror på en avrundningsskillnad, men i det här fallet visar det sig vara en bra slipsbrytare). K blir det nya vertexet att undersöka, så låt oss börja med att titta på sina grannar.

k har sex grannar, varav tre redan finns i den öppna uppsättningen, så de två sista h och L kommer också att läggas till i den öppna uppsättningen. Nu beräknar vi deras avstånd från början. K: S avstånd från start är 28, Så vi kommer att arbeta med 28+10=38 för G, J och L, och 28 + 14=42 för H. G och J har dock redan mindre avstånd att starta, så de kommer inte att uppdateras. Vi hittar de heuristiska avstånden för varje, beräknar deras summor och lägger till ”K” till varje tidigare toppunkt som uppdaterades.

K är komplett och flyttas till den stängda uppsättningen, och nästa toppunkt i det Öppna med den minsta summan är L, vår destination!

nu, att l är det aktuella vertexet, slutar algoritmen och vi kan använda vårt bord för att spåra sökvägen tillbaka till början:

• l: s tidigare vertex är k
• k: s tidigare vertex är f
• f’ tidigare vertex är A, startvertexen.

så det betyder att den kortaste vägen är en > F > K > L.

analysera resultaten

jämfört med Dijkstras algoritm har A* lämnat en röra bakom sig. Låt oss titta på några udda punkter. Börja med att titta på vertex C och dess avstånd till början: 28. Det verkar konstigt eftersom A och C bara är två horisontella rör sig bort från varandra, så det kortaste avståndet ska vara 20. Just nu verkar C tro att den kortaste vägen till A är två diagonala rörelser genom F.

När Dijkstras algoritm är klar bör den ge en mycket komplett tabell över avstånd från utgångspunkten. Omvänt har A*: S tabell felaktiga värden och saknar helt vertex D. men det fick samma svar som Dijkstra skulle ha, och det gjorde mycket snabbare. Dijkstra skulle ha velat titta på alla 12 hörn innan de förklarade att den hittade den kortaste vägen; A* behövde bara titta på 4 innan den hittade rätt väg. Denna förändring i hastighet beror på den heuristiska vi använde: så ofta vi kunde ville vi stänga avståndet med vår destination. Om vi går tillbaka till Wikipedias definition för heuristik, har A* handlat fullständighet för hastighet.

låt oss prova ett annat litet exempel, men med ett hinder på vägen till destinationen.

utgångspunkten är det övre vänstra vertexet, och A* försöker hitta den kortaste vägen till det nedre högra vertexet. De svarta rutorna representerar ett gap i diagrammet och kan inte korsas. Om A * följer sin heuristiska ”kom alltid närmare destinationen”, kommer de svarta rutorna att leda den till en blindände.

vid denna tidpunkt kommer a* att leta efter de minsta summorna, som kommer att vara rutorna precis nedanför och till höger om startpunkten. A * kommer att utforska båda vägarna, men den nedåtgående vägen kommer att springa in i en annan återvändsgränd, och höger väg kommer att hitta en väg runt de svarta rutorna. Det kan spela lite annorlunda än det här, men låt oss anta att det här är hur ett* hanterat detta scenario. Även när det drogs i döda ändar kunde det gå tillbaka och hitta en annan väg, och det behövde inte titta på varje toppunkt (det övre högra toppunktet hoppade över igen). Det betyder att när en * stjärna körs på sitt absolut värsta, är det i princip lika snabbt som Dijkstras normala prestanda. Varje algoritm har helt giltiga användningsfall, men när det gäller att hitta och hitta de kortaste vägarna är A* det bättre valet.