A* is een reeks stappen (een algoritme) die computers kunnen gebruiken om uit te zoeken hoe je snel ergens tussen twee plaatsen kunt komen. Als je een lijst van plaatsen hebt, en hoe moeilijk het is om van de ene naar de andere plaats te komen, kan A* je snel de snelste weg vertellen. Het is verwant aan Dijkstra's algoritme, maar doet slimme gokjes zodat het niet zo lang bezig is met het proberen van langzame manieren. Het is een goede serie stappen als je alleen het pad tussen twee plaatsen wilt weten. Als je veel paden van dezelfde kaart wilt, dan zijn er snellere manieren, die alle antwoorden in één keer vinden, zoals het Floyd-Warshall algoritme. A* werkt niet als je op één reis meerdere plaatsen wilt bezoeken (het handelsreizigersprobleem).
A*-algoritme
De stappen
A* heeft eerst een lijst nodig van alle plaatsen waar je heen kunt gaan, en dan een lijst van hoe ver de weg is tussen elke plaats. Het zal je dan vertellen wat de snelste weg is om van plaats A naar plaats Z te komen.
Als voorbeeld zeggen we dat A verbonden is met plaatsen B en C, en B en C zijn beide verbonden met D en E. D en E zijn beide verbonden met Z. Er zijn 4 mogelijke manieren om van A naar Z te gaan. Je kunt A-B-D-Z, A-C-D-Z, A-B-E-Z, of A-C-E-Z gaan. Een computer die A* gebruikt kijkt eerst hoe moeilijk het is om van A naar B te komen, en van A naar C. Dit zijn de "kosten" voor die plaatsen. De kosten van een plaats betekenen hoe moeilijk het is om van A naar die plaats te komen. Nadat de computer beide kosten heeft opgeschreven, bekijkt hij hoe moeilijk het is om van B naar D te komen, en telt dit op bij de kosten van B. Hij schrijft dit op als de kosten van D. Dan kijkt de computer hoe moeilijk het is om van C naar D te komen, en telt dit op bij de kosten van C. Dit is een andere kostprijs voor D, en als die lager is dan die welke hij al heeft, vervangt hij de oude. De computer wil alleen het beste pad weten, dus negeert hij het pad met de hoogste kosten. Hij onthoudt slechts een van A-B-D en A-C-D, afhankelijk van welke sneller is.
De computer gaat verder en vindt de snelste manier om bij E te komen. Tenslotte gaat hij van D naar Z en vindt de kosten, en van E naar Z en vindt de kosten. Hij krijgt de uiteindelijke kostprijs voor Z, en dit is de kleinste kostprijs die hij kan krijgen. Nu weet de computer welke weg het snelst is, en heeft hij het antwoord. De computer kan een soortgelijke reeks stappen uitvoeren, maar dan met veel meer plaatsen. Elke keer kijkt hij naar de plaats die het dichtst bij A ligt, en telt de kosten op van de buren van die plaats.
Men noemt de bovenstaande reeks stappen het algoritme van Dijkstra. Dijkstra's algoritme kan traag zijn, omdat het op veel plaatsen zal kijken die misschien de verkeerde kant opgaan vanuit Z. Als je de computer zou vragen hoe je van de ene stad in een naburige stad komt, zou Dijkstra's algoritme uiteindelijk in een andere staat kunnen gaan zoeken.
A* lost dit probleem op. A* laat je de computer een schatting geven van hoe ver het zal zijn van elke plaats naar het einde. De computer kan de gok gebruiken om ongeveer te zeggen hoe ver het zal zijn om van een bepaalde plaats naar Z te komen. In plaats van alleen maar de plaats te kiezen die het dichtst bij A ligt, kijkt hij naar de plaats die waarschijnlijk het laagste totaal heeft. Hij vindt dit totaal door de kosten bij de verwachte afstand op te tellen. Op deze manier kan hij alleen kijken in de richting waar het waarschijnlijk beter zal gaan. Het is niet erg als de gok niet perfect is, maar zelfs een simpele slechte gok kan het programma een stuk sneller laten gaan. Als je een pad probeert te vinden tussen twee plaatsen in de echte wereld, is een goede gok gewoon de afstand tussen hen in een rechte lijn. Het echte pad over wegen zal langer zijn, maar dit laat het programma het raden, en het zal niet de verkeerde kant op gaan.
In de literatuur over wiskunde of computerwetenschappen is deze gok vaak een functie van de plaats, en wordt hij een heuristiek genoemd. Elke plaats is een vertex, en elk pad tussen twee plaatsen is een edge. Dit zijn woorden uit de grafentheorie.