Reitinhakualgoritmit

Reitinhakualgoritmit ovat algoritmeja, joiden tarkoituksena on löytää polku kahden solmun välillä graafissa tai tilan representaatiossa ja samalla minimoida kustannukset, kuten matkan pituus tai liikkumiskustannus. Ne ovat keskeisiä esimerkiksi tie- ja liikennejärjestelmien suunnittelussa, robotiikassa sekä videopelien tekoälyssä. Reitinhakualgoritmit jaetaan yleisiin graafihakualgoritmeihin, jotka etsivät optimaalisen polun kaikista mahdollisista poluista, sekä heuristisiin hakualgoritmeihin, jotka käyttävät arvioivaa heuristiikkaa nopeuttaakseen etsintää. Heuristiikat voivat nopeuttaa etsintää, mutta ne voivat rikkoa optimointitarkoitusta, jos ne ovat epäadekvaatteja.

Yleisimpiä esimerkkejä ovat Dijkstra ja A*. Dijkstra etsii yksittäisen lähdepisteen ja minimoi polun kustannuksen kaikissa suunnissa; sen aikakompleksisuus on noin O((V+E) log V, kun käytetään binary heap -prioriteettijärjestystä. A* lisää heuristiikan, kuten Manhattan- tai Euclidean-etäisyyden, mikä yleensä vähentää tutkittavien solmujen määrää. Vasteisesti BFS (unweighted-verkko) hakee lyhyimmän polun reittiverkossa, ja Bellman-Ford kestää negatiivisia reuna-arvoja mutta on useammin hidas. Floyd-Warshall laskee kaikkien parien etäisyydet O(V^3) -ajalla ja vaatii muistia.

D*-Lite ja samankaltaiset lähestymistavat soveltuvat dynaamisiin ympäristöihin, joissa esteet voivat siirtyä, ja Jump Point Search nopeuttaa ruutumuotoisiin karttoihin sovitettua A*:ta. Reitinhakualgoritmit valitaan ympäristön ominaisuuksien mukaan ja huomioidaan sekä aikavaatimukset että muistivaatimukset.