Dijkstran algoritmi ja Best-First-Search#
Dijkstran algoritmi toimii käymällä graafin kärkipisteissä aloittaen kohteen aloituspisteestä. Sen jälkeen se tutkii toistuvasti lähintä vielä tutkimatonta kärkeä ja lisää sen kärkipisteet tutkittavien kärkipisteiden joukkoon. Se laajenee lähtöpisteestä ulospäin, kunnes se saavuttaa päämäärän. Dijkstran algoritmi löytää taatusti lyhimmän polun lähtöpisteestä maaliin, kunhan minkään reunan kustannukset eivät ole negatiiviset. (Kirjoitan ”lyhin polku”, koska usein on useita yhtä lyhyitä polkuja). Seuraavassa kaaviossa vaaleanpunainen neliö on lähtöpiste, sininen neliö on päämäärä, ja tiilenpunaiset alueet osoittavat, mitkä alueet Dijkstran algoritmi tutki. Vaaleimmat tiilenpunaiset alueet ovat ne, jotka ovat kauimpana lähtöpisteestä, ja muodostavat siten etsinnän ”rajan”:
Ahnelias Best-First-Search-algoritmi toimii samalla tavalla, paitsi että sillä on jonkinlainen arvio (jota kutsutaan heuristiikaksi) siitä, kuinka kaukana päämäärästä mikä tahansa huippu on. Sen sijaan, että se valitsisi alkupistettä lähimpänä olevan pisteen, se valitsee tavoitetta lähimpänä olevan pisteen. Greedy Best-First-Search ei löydä taatusti lyhintä polkua. Se toimii kuitenkin paljon nopeammin kuin Dijkstran algoritmi, koska se käyttää heuristista funktiota ohjaamaan tietä kohti päämäärää hyvin nopeasti. Jos päämäärä on esimerkiksi lähtöpisteen eteläpuolella, Greedy Best-First-Search pyrkii keskittymään etelään johtaviin polkuihin. Seuraavassa kaaviossa keltainen kuvaa solmuja, joilla on korkea heuristinen arvo (korkeat kustannukset päästä tavoitteeseen), ja musta kuvaa solmuja, joilla on matala heuristinen arvo (matalat kustannukset päästä tavoitteeseen). Se osoittaa, että Greedy Best-First-Search voi löytää polkuja hyvin nopeasti verrattuna Dijkstran algoritmiin:
Kummatkin esimerkit havainnollistavat kuitenkin yksinkertaisinta tapausta – kun kartalla ei ole esteitä ja lyhin polku on todella suora. Tarkastellaan edellisessä kappaleessa kuvattua koveraa estettä. Dijkstran algoritmi tekee enemmän töitä, mutta löytää taatusti lyhimmän polun:
Greedy Best-First-Search taas tekee vähemmän töitä, mutta sen polku ei selvästikään ole yhtä hyvä:
Ongelma on siinä, että Greedy Best-First-Search -algoritmi on ”ahnehtijamainen”, ja se yrittää liikkua kohti päämäärää, vaikkei se olisikaan oikea tie. Koska se ottaa huomioon vain päämäärään pääsyn kustannukset ja jättää huomiotta tähänastisen polun kustannukset, se jatkaa matkaa, vaikka kulkemastaan polusta olisi tullut todella pitkä.
Eikö olisi mukavaa yhdistää molempien parhaat puolet? A* kehitettiin vuonna 1968 yhdistämään heuristisia lähestymistapoja kuten Greedy Best-First-Search ja muodollisia lähestymistapoja kuten Dijsktran algoritmi. Se on sikäli hieman epätavallinen, että heuristiset lähestymistavat antavat yleensä likimääräisen tavan ratkaista ongelmia takaamatta, että saat parhaan vastauksen. A* on kuitenkin rakennettu heuristiikan päälle, ja vaikka heuristiikka itsessään ei anna takuuta, A* voi taata lyhimmän polun.