A*-algoritmi
(Ohjattu sivulta A*)
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[muokkaa | muokkaa wikitekstiä]
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.[1]
Lähteet[muokkaa | muokkaa wikitekstiä]
- ↑ Introduction to A* algorithm mnemstudio.org. Arkistoitu 3.7.2018. Viitattu 3.7.2018. (englanniksi)