Teekonnaotsingu algoritmide visualiseerija
vaata, kuidas erinevad otsingualgoritmid võistlevad samal ruudustikul, rinne rinde järel
miks heuristikud on olulised 🖖
Valem f(n)=g(n)+h(n) paneb A*-i eelistama sõlmi, mis on seni odavad ja tunduvad sihtpunktile lähedal. Kui h ei ülehinda kunagi järelejäänud kulu, säilitab A* oma lühima tee garantii; tugevam lubatav h uurib vähem ebavajalikke lahtreid. Vaheta algoritmi rippmenüüd, et näha, mis juhtub, kui jätta ära heuristik (Dijkstra), senine kulu (Greedy) või kogu hindamine (BFS).
Üks tsükkel, neli iseloomu 🖖
Kõik neli algoritmi käivitavad täpselt sama tsükli: võtavad ootenimekirjast kõige lootustandvama ruudu (merevaigukollane rinne), märgivad selle külastatuks (indigo) ja lisavad selle vabad naabrid nimekirja tagasi. Nad erinevad ainult selle poolest, kuidas otsustavad, milline ruut tundub kõige lootustandvam. Järeldus: laiendatud sõlmede arv on tegelik tulemustabel — vähem indigo ruute tähendab, et algoritm jõudis sama sihini väiksema raisatud tööga.
Diagonaalid võivad garantii rikkuda 🖖
Lülita sisse 'Luba diagonaal' koos Manhattani heuristikuga ja A* võib vaikselt tagastada tee, mis pole lühim. Diagonaalne samm maksab siin vaid √2 ≈ 1.41, kuid Manhattani kaugus arvestab selle kui 2 — nii heuristik ülehindab, muutub lubamatuks ja optimaalsuse garantii kaob. Vaheta Eukleidilisele, mis ei ületa kunagi otsejoone kaugust, ja lühim tee tuleb tagasi.
Näiteülesanded
- avatud ruudustik - Hõredad takistused annavad peaaegu otsese A* tee väga väheste laiendustega.
- labürindilaadne - Tihedad takistused sunnivad A*-i tegema pikemaid ümbersõite ja rohkem laiendusi.
- nõrk heuristik - Nõrgem heuristik uurib sama tee leidmiseks palju rohkem lahtreid.
- Dijkstra uurib - Dijkstra algoritm eirab sihtpunkti ja levib ühtlaselt igas suunas.
- greedy lõks - Ahne Best-First tormab sihtpunkti poole ja võib sattuda ummikutesse.
- bfs + diagonaalid - BFS käsitleb diagonaal- ja ortogonaalsamme võrdse kuluga, mistõttu tema tee võib A* teest erineda.