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.

Esimerkki A*-algoritmista.

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.