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.

Kuvaus

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

Lähteet