A*-algoritmi

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.

KuvausMuokkaa

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

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