A*-algoritmi
![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Pathfinding_A_Star.svg/250px-Pathfinding_A_Star.svg.png)
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. Algoritmia voidaan hyödyntää muun muassa verkkojen reitityksessä ja GPS-paikannuksessa
Algoritmin julkaisivat Peter E. Hart, Nils J. Nilsson ja Bertram Raphael vuonna 1968.[1] A*-algoritmi on samankaltainen kuin toinen yleisesti polunetsintään käytetty Dijkstran algoritmi.[2] A* kehitettiin yhdistämällä heuristiikkaa ja formaali Dijkstran algoritmi.[3]
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.[4]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Peter E. Hart & Nils J. Nilsson & Bertram Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths ieeexplore.ieee.org. doi:10.1109/TSSC.1968.300136. Viitattu 5.6.2024. (englanniksi)
- ↑ Dian Rachmawati1 & Lysander Gustin: Analysis of Dijkstra’s Algorithm and A* Algorithm in Shortest Path Problem (PDF) iopscience.iop.org. 2019. doi:10.1088/1742-6596/1566/1/012061. Viitattu 5.6.2024. (englanniksi)
- ↑ Introduction to A* theory.stanford.edu. Viitattu 5.6.2024. (englanniksi)
- ↑ Introduction to A* algorithm mnemstudio.org. Arkistoitu 3.7.2018. Viitattu 3.7.2018. (englanniksi)