A*-algoritmi

Esimerkki A*-algoritmista.

A*-algoritmi (lausutaan A tähti) on tekoälyssä käytetty algoritmi ratkaisun etsimiseen hakupuusta. Sen tarkoituksena on evaluoida lehtisolmuja funktioin 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.