A*-algoritmi

Esimerkki A*-algoritmista.

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

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

Kuvaus

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