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  

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