A*-algoritmi

Wikipediasta
Siirry navigaatioon Siirry hakuun
Esimerkki A*-algoritmista.

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ä]

  1. Introduction to A* algorithm mnemstudio.org. Arkistoitu 3.7.2018. Viitattu 3.7.2018. (englanniksi)
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.