Keskustelu: Yleinen keskustelu: Lyhimmän reitin haku

Kuuluin vielä jokin aika sitten niiden vääräuskoisten lahkoon, joiden mielestä a* -hakualgoritmi löytää aina lyhimmän ja optimaalisimman reitin. Ei löydä. Koko algoritmi on ahterista.

Ahaa. Kiva kuulla. Kerrotko lisää?

Haluaisitko kenties perustella väitettäsi?

Minä kuulun edelleen siihen kulttiin joka uskoo, että nopein tie helpotukseen käy oman käden kautta. Agnostikoille jäänee pääteltäväksi, että millaisesta helpotuksesta puhun.

"Then he got angry. After he rolled some tinfoil over his head, she kissed me."

Wikipedian artikkelin mukaan algoritmin pitäisi löytää aina oikea tulos. Vaikka A* on tarkoitettu yleiseksi algoritmiksi niin kuitenkin ko. artikkelin mukaan se voisi erehtyä.

Voisitko antaa esimerkin tilanteesta missä A* antaa vääränlaisen reitin.

Mitenköhän musta tuntuu, että jollain on bugi koodissa.

Pakko sanoa, että onpas mielenkiintoinen keskustelu.

Minä kuulun niiden vääräuskoisten lahkoon jotka eivät tiedä mikä on "a*". Voisiko joku nerokas ihminen kertoa?

Minä kuulun niiden uskottomien joukkoon, jotka tietävät A*:n olevan reitinhakualgoritmi, mutta jotka eivät ole tutustuneet sen tai minkään muunkaan vastaavaan tarkoitukseen luodun virityksen toimintaan.

EDIT: Tietoa kansalle:
http://en.wikipedia.org/wiki/Pathfinding
http://en.wikipedia.org/wiki/A*_search_algorithm

Hmm, on varmaan niin, että nykyään pitäisi erilaisia hymiöitä ja pikku-ukkoja lisätä virkkeen perään ja lauseen sisään varmuuden vuoksi.

Ei tässä nyt ole kysymys niin vakavasta aiheesta. Kuitenkin kauan sitten eräs omasta mielestään pätevä pyknikko väitti, että tämä a* löytää aina lyhimmän reitin. Sitten olin tyytyväisenä siinä uskossa, kunnes ensimmäinen todellinen aiheeseen liittyvä koodausongelma osoitti, että ainakin suuremmilla graafeilla a* ei koskaan löydä oikeaa ratkaisua.

Että niin. Jokainen käyttää, mitä huvittaa. Tosin, kun nyt sitten ihan mielenkiinnosta kyyläsin joiltakin sivustoilta, mitä tuosta a*:stä oli sanottu, niin oli sanottu melko samoilla sanoilla, että algoritmin luotettavuus suppenee neliössä kohti ahteria suhteessa graafin monimutkaisuuteen.

JoinTuanJanohon kirjoitti:

Sitten olin tyytyväisenä siinä uskossa, kunnes ensimmäinen todellinen aiheeseen liittyvä koodausongelma osoitti, että ainakin suuremmilla graafeilla a* ei koskaan löydä oikeaa ratkaisua.

Voitko antaa esimerkkinä yhden tällaisen graafin? Tai asiaan liittyvän sivuston?

Minä olen toistaiseksi samaa mieltä "pätevän pyknikon" kanssa.

Itseasiassa itse olen kuullut ettei a* löydä aina optimaalisinta reittiä, vaan sen löytämä reitti on erittäin lähellä optimaalista reittiä.

Dijkstran algoritmi sen sijaan löytää optimaalisimman reitin, mutta käyttää laskuaikaakin paljon enemmän

ja vielä wikipediasta:

wikipedia kirjoitti:

Another algorithm is Dijkstra's algorithm, which is similar to A* except it always finds the optimal path (A* is a compromise of path length, and calculation time).

A* toimii siis niin, että kekoon tallennetaan siihen asti kuljetun matkan ja optimistisen (ei liian suuren) loppumatkan arvion summa. Kaikista mahdollisista vaihtoehdoista valitaan joka kerta pienin. En keksi tilannetta, jossa lyhyempi reitti jäisi algoritmilta huomaamatta. Suurilla graafeilla ongelmaksi tulee kylläkin keon kasvaminen suureksi.

Wikipediassa on tunnetusti virheitä, toisella sivulla todetaan:

Wikipedia: A* Search algorithm kirjoitti:

This makes A* complete and optimal, i.e., A* will always find the shortest route if any exists.

Dijkstran algoritmi toimii muuten lähes samalla tavalla, mutta se ei käytä arviota haun nopeuttamiseksi.

Antti Laaksonen kirjoitti:

Voitko antaa esimerkkinä yhden tällaisen graafin?

No siinä on noin miljoona solmua, ja jokaisesta solmusta on 2-n kappaletta reittejä muihin solmuihin. Solmujen jakauma on mahdollisimman epätasainen.

Antti Laaksonen kirjoitti:

A* toimii siis niin, että kekoon tallennetaan siihen asti kuljetun matkan ja optimistisen (ei liian suuren) loppumatkan arvion summa.

Mutta jos tehdään sellainen graafi, jossa puolet reiteistä suppenee nopeasti kohti päätepistettä, mutta päättyvätkin juuri ennen päätepistettä umpikujiin? Sitten toinen puoli reiteistä, jotka johtavat päätepisteestä ensin pitkään poispäin, ja vasta sitten alkavat lähentyä päätepistettä, niin miten a* löytäisi reitin?

Ilmeisesti on myös niin, että a* olettaa graafin olevan ennakko-odotusten mukainen. Eli siis, jos reitti suppenee kohti päätepistettä, se ei myöskään saa päättyä umpikujaan?

Edelliseen esimerkkiin olisi pitänyt vielä mainita, että osa reiteistä päättyy umpikujiin. Saattaisi tuo Dijkstran-algoritmikin kaatua sellaisessa sekamelskassa, mene ja tiedä.

Jos kaikki muut reitit päättyvät umpikujaan, A* ottaa lopulta tarkasteluun sen, joka näytti aluksi kaikkein huonoimmalta. A* ei missään vaiheessa hylkää muita reitinalkuja, vaan pitää kaikkia tallessa varmuuden vuoksi. A*:n ja Dijkstran algoritmin toimintaan eivät vaikuta mahdolliset umpikujat, koska kumpikaan ei lukkiudu mihinkään tiettyyn reittiin.

Oletko tarkistanut, että ohjelmasi toimii oikein ja muistia on riittävästi?

A* löytää aina lyhimmän reitin, jos käytetään sellaista heuristiikkaa, joka ei koskaan yliarvioi solmun etäisyyttä maalisolmuun. Mitä enemmän heuristiikka yliarvio etäisyyttä, sitä enemmän algoritmi muistuttaa syvyyshakua, joka kyllä löytää jonkun ratkaisun nopeasti, mutta yleensä optimaalista huonomman ratkaisun. Jos heuristiikka taas aliarvio etäisyyttä, muistuttaa algoritmi enemmän leveyshakua (0-heristiikalla dijkstran algoritmia), joka toimii hitaammin, mutta löytää aina lyhimmän reitin. Yleensä pyritään löytämään mahdollisimman tarkka heuristiikka, jolla siis löydetään lyhin ratkaisu mahdollisimman nopeasti. Tietyissä tapauksissa heuristiikkaa tarkoituksellisesti yliarviodaan, jotta algoritmi toimisi nopeammin.

Tässä verkko-ongelmassa on luultavasti kyse siitä, että heuristiikka ei ole avain kohdallaan ja siksi optimaalista reittiä ei löydy.

JoinTuanJanohon kirjoitti:

Antti Laaksonen kirjoitti:

A* toimii siis niin, että kekoon tallennetaan siihen asti kuljetun matkan ja optimistisen (ei liian suuren) loppumatkan arvion summa.

Mutta jos tehdään sellainen graafi, jossa puolet reiteistä suppenee nopeasti kohti päätepistettä, mutta päättyvätkin juuri ennen päätepistettä umpikujiin? Sitten toinen puoli reiteistä, jotka johtavat päätepisteestä ensin pitkään poispäin, ja vasta sitten alkavat lähentyä päätepistettä, niin miten a* löytäisi reitin?

Ilmeisesti on myös niin, että a* olettaa graafin olevan ennakko-odotusten mukainen. Eli siis, jos reitti suppenee kohti päätepistettä, se ei myöskään saa päättyä umpikujaan?

Edelliseen esimerkkiin olisi pitänyt vielä mainita, että osa reiteistä päättyy umpikujiin. Saattaisi tuo Dijkstran-algoritmikin kaatua sellaisessa sekamelskassa, mene ja tiedä.

Kuten jo on mainittu, A* löytää aina perille, vaikka olisi miljardeja reittejä joista kaikki paitsi yksi ovat umpikujia. Vain toteutus voi olla puutteellinen. Eikä Dijkstrakaan mihinkään kaadu, toteutus ehkä voi.

Eli jos et löydä hyvää reittiä tai reittiä ollenkaan on vika implementaatiossa.

Vai niin, tunnut olevan asiantuntija, koska fokusoit ongelman lonkalta implementointiin :-) Saattaahan tuo vika koodaajassakin olla, ja varmasti onkin. Mutta kaiketi mielenkiintoisen tehtävän saisi pukapostiin, jos haettaisiin ratkaisua kauppamatkustajan ongelmaan esimerkiksi Euroopan pääkaupungeilla. Väittävät jotkin heinähatut, ettei ko. lyhimmän reitin hakuun ole olemassa yleistä ratkaisua. Vaikuttaa siltä, että monella on sellainen mutu-tuntuma, että a*:llä reitti ratkeaisi. Eiköhän laiteta kisat pystyyn: a* vastaan muut pläjäykset :-)

JoinTuanJanohon kirjoitti:

Vaikuttaa siltä, että monella on sellainen mutu-tuntuma, että a*:llä reitti ratkeaisi. Eiköhän laiteta kisat pystyyn: a* vastaan muut pläjäykset :-)

Mikä olisi voittoon kelpuutettava ratkaisu? Ensiksi reitit pitäisi rajata, esim. luoda verkosto kaupunkien välille (tiet), ja jokaiselle tielle matkaan kulutettu aika. Sitten mentäisiin vain algoritmillä läpi jokaisen tien väliin kulutettu aika ja yhteensummattuna nopein reitti löytyisi.

Suurin ongelma tuossa onkin rajata nuo tiet ja laskea niiden matkustamiseen kuluva aika. Eli itse reitin löytäminen ja sen ohjelmoiminen on erittäin helppoa, mutta tehtävän lähtöasetelman luominen on paljon vaikeampaa.

Kilpailu olisi siis osallistujille erittäin helppo ja tylsä, kun se taas kilpailun järjestäjälle olisi erittäin vaikea.

edit:
Vanhaa materiaalia ja esimerkki flash-muodossa:
Eli kuvaa optimoimatonta reitinhaku-algoritmia
http://www.terolepisto.net/games/old/temp/pathfind.swf

Hyvä Lebe80. L. Euler, W. R. Hamilton, ynnä muut graafiteoria historian luoneet eivät onnistuneet rakaisemaan kauppamatkustajan ongelman yleistä ratkaisua. Tosin muutamia mielenkiintoisia poikkeuksia he onnistuivat ratkomaan, muun muassa Königsbergin siltojen ongelman. Kuitenkin, kun olet nyt tuon ongelman ratkaissut: "Sitten mentäisiin vain algoritmillä läpi jokaisen tien väliin kulutettu aika ja yhteensummattuna nopein reitti löytyisi.", niin täytyy kyllä nostaa hattua moisesta suorituksesta :-)

Mutta eihän kauppamatkustajan ongelmaa voida ratkaista ainakaan suoraan A*:llä. A* on tarkoitettu (lyhimmän) reitin löytämiseen pisteestä A pisteeseen B.

Kauppamatkustajan ongelmassa taas on kysymys lyhimmän sellaisen reitin löytämisestä, joka kulkee kerran ja vain kerran kaikkien graafin pisteiden kautta ja palaa lähtöpisteeseensä.

A* siis vastaa aivan eri kysymykseen.

Onkohan JoinTuanJanohon edes ymmärtänyt A*:n käyttötarkoitusta? Eihän noita lyhimpiä reittejä voi päästä heittää, vaan ne lasketaan.

arcatan kirjoitti:

Kauppamatkustajan ongelmassa taas on kysymys lyhimmän sellaisen reitin löytämisestä, joka kulkee kerran ja vain kerran kaikkien graafin pisteiden kautta ja palaa lähtöpisteeseensä.

A* siis vastaa aivan eri kysymykseen.

Kyllä kauppamatkustajan ongelma ratkeaa ihan hyvin A* algoritmilla pienissä tapauksissa. Ongelmaksi vain tulee se, että hakupuu kasvaa exponentiaalisesti kaupunkien määrän kasvaessa ja A*-algoritmin aika- ja tilavaatimukset tulevat vastaan. Exponentiaalinen hakupuu ei välttämättä olisi ongelma, jos tehtävään olisi hyvä heuristiikka, joka ohjaa ratkaisua riittävästi oikeaan suuntaan, muttä tässä tapauksessa näin ei ole.

arcatan kirjoitti:

Mutta eihän kauppamatkustajan ongelmaa voida ratkaista ainakaan suoraan A*:llä. A* on tarkoitettu (lyhimmän) reitin löytämiseen pisteestä A pisteeseen B.

A* ei ole pelkästään algoritmia lyhimmän reitin etsimiseen pisteestä A pisteeseen B, vaan pikemminkin algoritmi, jolla löydetään heuristiikan ja siirtymien painokertoimien mukaan lyhin tilasiirtymä alkutilasta A maalitilaa B. Kauppamatkustajan ongelmassa alkutila A on se, että olla lähtökaupungissa eikä olla käyty missään muissa kaupungeissa. Lopputila olisi se, että ollaan lähtökaupungissa ja ollaan käyty kaikissa kaupungeissa. Heuristiikan etäisyysarvio maalista riippuu siitä kuinka monessa kaupungissa ei olla vielä käyty (ja tietenkin kaupunkien keskinäisistä etäisyyksistä).

Hmm, ehkei se a* sitten olekaan niin syvältä ahterista, ja feenix kiteytti asian ytimekkäästi: "Eli jos et löydä hyvää reittiä tai reittiä ollenkaan on vika implementaatiossa." Täytyy palata sorvin ääreen, ja ruveta syventymään paremmin a* perimmäiseen olemukseen, koska nyt oleva (optimoitu) BruteForce -jauhin prosessoi ratkaisua tunti tolkulla per tapaus.

JoinTuanJanohon kirjoitti:

Täytyy palata sorvin ääreen, ja ruveta syventymään paremmin a* perimmäiseen olemukseen, koska nyt oleva (optimoitu) BruteForce -jauhin prosessoi ratkaisua tunti tolkulla per tapaus.

"Tunti tolkulla" kuulostaa vielä optimoimattomalta. Eli jos kyseessä olisi nyt maailman kartta, niin jaa alueita osiin. Esim. lääneiksi, osavaltioiksi, valtioiksi ja esim. maanosiksi. Näistä lähdet etsimään reittiä ensiksi isoimmaista pienimpään. (Aluksi reitti pelkillä maanosilla: Pohjois-Amerikka -> Aasia -> Eurooppa, joista jokaisesta sitten reitit hieman tarkemmin ja taas tarkemmin). Näin voit jättää suoraan kaikki "ylimääräiset" reitit pois.

edit:
Tietenkin joudutaan laskea maanosille, valtioille yms. viitteelliset etäisyydet, mutta laskenta-aika nopeutuu huomattavasti vaikka heittoja "optimaalisimman" reitin välillä syntyykin.