A*-sökalgoritm
A* är en uppsättning steg (en algoritm) som datorer kan använda för att räkna ut hur man snabbt kan ta sig mellan två platser. Om du har en lista över platser och hur svårt det är att ta sig från den ena platsen direkt till den andra, kan du med hjälp av A* snabbt få reda på den snabbaste vägen. Den är besläktad med Dijkstras algoritm, men gör smarta gissningar så att den inte spenderar lika lång tid på att försöka hitta långsamma vägar. Det är en bra serie steg om du bara vill ha vägen mellan två platser. Om du ska fråga efter många vägar från samma karta finns det snabbare metoder som hittar alla svaren på en gång, till exempel Floyd-Warshall-algoritmen. A* fungerar inte om du vill besöka flera platser på en och samma resa (Travelling salesman-problemet).
Stegen
A* behöver först en lista över alla platser du kan åka till och sedan en lista över hur långt vägen är mellan dem. Därefter får du veta vilket som är det snabbaste sättet att ta sig från plats A till plats Z.
Som exempel kan vi säga att A är ansluten till platserna B och C, och B och C är båda anslutna till D och E. D och E är båda anslutna till Z. Det finns fyra sätt att gå från A till Z. Du kan gå A-B-D-Z, A-C-D-Z, A-B-E-Z eller A-C-E-Z. En dator som använder A* tittar först på hur svårt det är att ta sig från A till B och från A till C. Detta är "kostnaden" för dessa platser. Kostnaden för en plats innebär hur svårt det är att ta sig från A till den platsen. Efter att ha skrivit ner båda kostnaderna tittar datorn på hur svårt det är att ta sig från B till D och lägger till detta till B:s kostnad. Den skriver ner detta som D:s kostnad. Sedan tittar datorn på hur svårt det är att ta sig från C till D och lägger till detta till C:s kostnad. Detta är en annan kostnad för D, och om den är lägre än den som redan finns kommer den att ersätta den gamla kostnaden. Datorn vill bara veta den bästa vägen, så den ignorerar vägen med den högre kostnaden. Den kommer bara att komma ihåg en av A-B-D och A-C-D, beroende på vilken som är snabbast.
Datorn fortsätter och hittar det snabbaste sättet att ta sig till E. Slutligen går den från D till Z och hittar en kostnad, och från E till Z och hittar en kostnad. Den får fram en slutlig kostnad för Z, och detta är den minsta kostnad som den kan få fram. Nu vet datorn vilken väg som är snabbast, och den har svaret. Datorn kan göra en liknande serie steg, men med många många fler platser. Varje gång tittar den på den plats som ligger närmast A och lägger ihop kostnaderna för den platsens grannar.
Man kallar denna serie steg för Dijkstras algoritm. Dijkstras algoritm kan vara långsam, eftersom den tittar på många platser som kan gå åt fel håll från Z. Om du frågar datorn hur du ska ta dig från en stad till en närliggande stad kan Dijkstras algoritm hamna i en annan stat.
A* löser detta problem. Med A* kan du ge datorn en gissning om hur långt det kommer att vara från varje plats till slutet. Datorn kan använda gissningen för att ungefär säga hur långt det tar att ta sig från en viss plats till Z. I stället för att bara välja den plats som ligger närmast A att titta på, tittar den på den plats som förmodligen kommer att ha den lägsta totalsumman. Den får fram denna totalsumma genom att addera kostnaden till den förväntade sträckan kvar. På så sätt kan den bara titta i den riktning där det förmodligen kommer att bli bättre. Det är okej om gissningen inte är perfekt, men även en enkel dålig gissning kan få programmet att gå mycket snabbare. Om du försöker hitta en väg mellan två platser i den verkliga världen är en bra gissning bara avståndet mellan dem i en rak linje. Den verkliga vägen över vägar kommer att vara längre, men detta gör att programmet kan gissa sig fram, och det kommer inte att gå i fel riktning.
I litteraturen om matematik och datavetenskap är denna gissning ofta en funktion av platsen och kallas en heuristik. Varje plats är en vertex och varje väg mellan två platser är en kant. Detta är ord från grafteori.
