A*-algoritmi

A*-algoritmi (lausutaan A tähti) on polunetsintäalgoritmi, joka etsii lyhyimmän reitin kahden pisteen välillä. Algoritmia voidaan käyttää myös tekoälyssä ratkaisun etsimiseen hakupuusta. Algoritmia voidaan hyödyntää muun muassa verkkojen reitityksessä ja GPS-paikannuksessa

Esimerkki A*-algoritmista.

Algoritmin julkaisivat Peter E. Hart, Nils J. Nilsson ja Bertram Raphael vuonna 1968.^[1] A*-algoritmi on samankaltainen kuin toinen yleisesti polunetsintään käytetty Dijkstran algoritmi.^[2] A* kehitettiin yhdistämällä heuristiikkaa ja formaali Dijkstran algoritmi.^[3]

Kuvaus

Algoritmin tarkoituksena on evaluoida lehtisolmuja funktion ${\displaystyle f(n)=g(n)+h(n)}$ avulla, missä ${\displaystyle g(n)}$ kuvaa kustannusta saavuttaa tietty solmu ja ${\displaystyle h(n)}$ on kustannusarvio solmusta maalitilaan. Tällöin ${\displaystyle f}$ approksimoi kustannusta lähtösolmusta maalisolmuun. A*-algoritmi on optimaalinen jos ${\displaystyle h}$ on luvallinen. Tämä tarkoittaa sitä, että ${\displaystyle h}$ ei koskaan yliarvioi kustannusta saavuttaa maalisolmu.^[4]