Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Lyhimmän polun löytämiseen tarkoitettu algoritmi mielivaltaisissa (mutta yleensä selkeän geometrisissa) graafeissa. Dijkstra-algoritmi lisättynä jäljellä olevaa matkaa laskevalla heuristiikalla.
Dijkstra-algoritmi on olennaisesti leveyshaku, jossa jono on korvattu prioriteettijonolla ja solmun prioriteetti määräytyy alemmaksi sen perusteella, mikä on sinne kulkemisen hinta (matkan pituus / raskaus). Myös A* käyttää prioriteettijonoa, mutta prioriteettia edelleen madalletaan arvioidun matkan solmusta maaliin perusteella. Tietenkin A*:a voi käyttää vain tilanteissa, joissa on jokin järkevä peruste arvioida matkaa solmusta maaliin (esim. karteesisessa avaruudessa suora etäisyys).
A*:ssa on tärkeää, että heuristiikka ei koskaan yliarvioi matkaa solmusta maaliin. Muuten saatetaan menettää joitain lyhimpiä polkuja ja saada siten väärä tulos.
Jotta esteellisestä maastosta pystyy muodostamaan graafin A*:n käyttöön, riittää, että sijoitetaan kaikkien esteiden päihin (siis paikkoihin, joista ne voi ohittaa) solmu ja lasketaan niiden solmujen väliset etäisyydet, joiden välillä ei ole estettä. Ikosaedrimaailman toteutus vaatii lisäksi solmuja niihin kohtiin, joista voi ylittää ikosaedrin tahon rajat.