thumb|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 avulla, missä kuvaa kustannusta saavuttaa tietty solmu ja on kustannusarvio solmusta maalitilaan. Tällöin approksimoi kustannusta lähtösolmusta maalisolmuun. A*-algoritmi on optimaalinen jos on luvallinen. Tämä tarkoittaa sitä, että ei koskaan yliarvioi kustannusta saavuttaa maalisolmu.
Lähteet
Luokka:Algoritmit Luokka:Tekoäly