Keskustelu: Ohjelmointikysymykset: C++: Lyhimmän reitin laskeminen

Hei!

Olen tekemässä ohjelmaa, jonka on tarkoitus laskea lyhin reitti paikasta A paikkaan B (Kartta informaatio on peräisin OpenStreetMapista). Olenkin jo onnistunut tekemään jonkinlaisen A* algoritmia höydyntämällä. Tällä hetkellä en ole vielä ladannut koko Suomen karttaa, vaan olen testannut algoritmia pienellä osalla Tokiota, pienellä osalla Manhattania ja lähes koko Oulun kartalla. Näillä alueilla reitin etsiminen kestää pahimmillaan noin 1-2 sekuntia. Minua kuitenkin mietityttää, että onko se liian hidas, kun tarkoituksena olisi ladata koko Suomen kartta ja laskea siitä lyhin reitti. Kysymys kuuluu näin, mikä olisi paras tapa laskea h, eli arveltu etäisyys pisteeseen B. Tällä hetkellä lasken sen näin. Etäisyys leveyssuunnassa+Etäisyys korkeussuunnassa. Tällöin algoritmi käy kokeilemassa melko paljon turhiakin paikkoja. Kannattaisiko siirtyä johonkin parempaan algoritmiin ja jos kannattaisi, niin mihin?

Käyttämäsi tapa on ehkä nopein muttei tietty kovin tarkka.

Tarkin tapa on pythagoraan lauseesta sovellettuna: sqrt((x2-x1)^2+(y2-y1)^2)
Mutta neliöjuuren takia se on vähän hitaampi. Tämä vastaa kysymykseen "Mikä etäisyys on?"

Mutta jos riittää kysyä "Onko piste enintään tietyn etäisyyden päässä?", tai "Törmääkö piste ympyrään?" niin ei tarvita neliöjuurta vaan voi tehdä:
if ((x2-x1)^2+(y2-y1)^2) < (etaisyys^2)) then OnAlueenSisalla();

User137: Algoritmin pullonkaula ei varmaankaan ole tämä lauseke vaan ne laskettavat reitit. (Mutta toki tuonkin laskeminen oikein antaa maantieajossa paremman tuloksen, korttelipohjaisessa kaupungissa tietenkään ei.)

Yksi optimointitapa on laskea valmiiksi joitakin pääreittejä ja muodostaa ensimmäinen arvio hyvästä reitistä niin, että mennään lähimmälle pääreitille ja sitä pitkin mahdollisimman lähelle kohdetta. Näin algoritmi ei päädy turhaan harhailemaan pikkuteillä. Ajatusta voi soveltaa usealla tasolla: (valtakunnalliset moottoritiet, kaupungin pääkadut, kaupungin pikkutiet). Löydettävä reitti ei välttämättä ole täsmälleen lyhin, mutta laskenta-aikaa säästetään huomattavasti, ja lisäksi reitistä tulee selkeä, koska se hyödyntää mahdollisimman paljon isoja teitä.

Se olikin vastaus tuohon ekaan kysymykseen eli pelkkä etäisyys pisteestä A -> B.

Tuokin algoritmi varmaan nopeutuu jos pystyt rajaamaan algoritmille kartasta vain sen pienen osan josta reitti haetaan.

Joo, siis perusohjeiksi antaisin itsekin että ei kannata käyttää syvyyshakua eikä toisaalta kannata hakea sitä reittiä jonka voidaan matemaattisesti todistaa olevan lyhin/nopein, vaan haetaan reitti joka 99% tapauksista on paras ja lopuissa 1% melko hyvä.

Ja mitä tulee pythagoraan lauseeseen, niin
- reitin suunnittelussa sinänsä ei kiinnosta mikä on kahden pisteen välinen etäisyys (linnuntietä), vaan mikä on kahden pisteen välinen ajomatka ja
- pythagoraan lauseella ei saada tarkkoja etäisyyksiä tiedettäessä ellipsoidipinnan koordinaatit. Jos koordinaatit mapataan 3d avaruuteen, niin pythagoraalla toki saa pisteiden keskinäiset etäisyydet, mutta se lyhin reitti menee sitten ellipsoidin sisällä eli maan pinnan alla. Ennemmin kannattaa käyttää vaikka Vincentyn kaavaa, jossa toki on omat epätarkkuutensa. Ei sillä että näistä millään olisi paljon käyttöä tässä sovelluksessa.

Olen tosiaan miettinyt, että olisiko järkevämpi toteuttaa ohjelma, joka laskee lyhyen mutta järkevämmän reitin, sen sijaan, että laskisin lyhimmän reitin. Ja mitä olen testannut tuota nykyistä ohjelmaa, niin reiteistä on kyllä järki kaukana :D (Ovi kartat- palvelun reitteihin tulee noin 15 km matkalla noin 3 km säästö pituudesta). Pythagoraan lauseen laskeminen on niin hidasta, että vaikka se vähentäisikin tarkasteltavia pisteitä, niin algoritmistä tulee käytännössä paljon hitaampi. Se mikä kestää nykyisellään 1-2 sekuntia, kestää yli 3 minuuttia (en jaksanut odottaa kauempaa) pythagoraan lauseen avulla.

Grez kirjoitti:

Joo, siis perusohjeiksi antaisin itsekin että ei kannata käyttää syvyyshakua eikä toisaalta kannata hakea sitä reittiä jonka voidaan matemaattisesti todistaa olevan lyhin/nopein, vaan haetaan reitti joka 99% tapauksista on paras ja lopuissa 1% melko hyvä.

Eihän A* ole sama asia kuin syvyyshaku.

Metabolix kirjoitti:

Yksi optimointitapa on laskea valmiiksi joitakin pääreittejä ja muodostaa ensimmäinen arvio hyvästä reitistä niin, että mennään lähimmälle pääreitille ja sitä pitkin mahdollisimman lähelle kohdetta. Näin algoritmi ei päädy turhaan harhailemaan pikkuteillä. Ajatusta voi soveltaa usealla tasolla: (valtakunnalliset moottoritiet, kaupungin pääkadut, kaupungin pikkutiet). Löydettävä reitti ei välttämättä ole täsmälleen lyhin, mutta laskenta-aikaa säästetään huomattavasti, ja lisäksi reitistä tulee selkeä, koska se hyödyntää mahdollisimman paljon isoja teitä.

Tarkoitatko, että ensin laskisin esimerkiksi A* algoritmilla lyhimmän reitin, jollekkin isommalle tielle. Sen jälkeen laskisin lyhimmän reitin "maalista" isomalle tielle. Ja viimeisenä samaa algoritmiä hyödyksi käyttäen, mutta kaikki pienet tiet karsien laskisin lyhimmän reitin näiden pisteiden välille. Ja sitten yhdistäisin nämä. Vai antaisin suuremman prioriteetin, mitä suurempi tie on kyseessä. Vai tarkoititko kumpaakaan näistä.

Jalmari91 kirjoitti:

Se mikä kestää nykyisellään 1-2 sekuntia, kestää yli 3 minuuttia (en jaksanut odottaa kauempaa) pythagoraan lauseen avulla.

Nyt kyllä kuulostaa, että olet tehnyt jotain väärin. (Et kai vain käyttänyt koodissa ^-merkkiä? Se ei suinkaan tarkoita useimmissa ohjelmointikielissä potenssilaskua.)

Jalmari91 kirjoitti:

Tarkoitatko, että

Molemmat ovat hyviä ajatuksia, itse tarkoitin näistä ensimmäistä.

Metabolix kirjoitti:

Jalmari91 kirjoitti:

Se mikä kestää nykyisellään 1-2 sekuntia, kestää yli 3 minuuttia (en jaksanut odottaa kauempaa) pythagoraan lauseen avulla.

Nyt kyllä kuulostaa, että olet tehnyt jotain väärin. (Et kai vain käyttänyt koodissa ^-merkkiä? Se ei suinkaan tarkoita potenssilaskua.)

Tiedän toki, että ^ tarkoittaa xor:ia. Eli toteutin sen näin sqrt(pow((x2-x1),2)+pow((y2-y1),2))

EDIT: Mitkähän näistä kannattaisi ajatella pieniksi teiksi ja mitä isoiksi http://wiki.openstreetmap.org/wiki/Key:highway .

Ei kannata käyttää myöskään pow-funktiota, joka tekee hitaan yleisen potenssilaskun, vaan ihan tavallista kertolaskua. Mutta tästä huolimatta hitaus kuulostaa omituiselta. Syynä ei luultavasti ole tuo lasku vaan jokin muu seikka hakualgoritmissa (tai siis siinä, mitä se päätyy tutkimaan).

Metabolix kirjoitti:

Ei kannata käyttää myöskään pow-funktiota, joka tekee hitaan yleisen potenssilaskun, vaan ihan tavallista kertolaskua. Mutta tästä huolimatta hitaus kuulostaa omituiselta. Syynä ei luultavasti ole tuo lasku vaan jokin muu seikka hakualgoritmissa (tai siis siinä, mitä se päätyy tutkimaan).

Oli varmaan joku näppäilyvirhe, koska nyt se toimii, mutta ei siitä ole juurikaan apua. Pitää varmaan käyttää tuota Metabolix:n ideaa, sen sijaan, että laskisin lyhimmän, mutta epäkäytännöllisen reitin hitaasti.

^ kyllä tarkoitti pseudona potenssimerkkiä... ja tietysti se on hitaampi kun aiempi algoritmi, se vaan antaa suoran reitin, ei kiertotietä.

User137 kirjoitti:

^ kyllä tarkoitti pseudona potenssimerkkiä... ja tietysti se on hitaampi kun aiempi algoritmi, se vaan antaa suoran reitin, ei kiertotietä.

Siis kyllä minä sen tajusin, mutta kun Metabolix arveli, että minä olin laittanut koodiin ^ merkin, mikä tarkoittaa mm. C ja C++ xor:ia.

EDIT: Luin muuten tuota wikipedian artikkelia A* algoritmistä, niin tajusin, että minun alkuperäinen tapa laskea h on joissain tapauksissa virheellinen, koska sen pitää tietenkin olla AINA lyhyempi, kuin todellinen matka :D Siihenhän se koko algoritmi tietenkin perustuukin.

Ja jotta saataisiin sekotettua pakkaa, niin karttojen reiteissähän tärkeintä on oikeasti löytää nopein reitti, eikä niinkään lyhin. :)

Usein esimerkiksi navigaattorit osaa kertoa joko nopeimman tai lyhimmän reitin käyttäjän valinnan mukaan. Silti väitän että navigaattori ei hae matemaattisen taatusti nopeinta tai lyhintä reittiä, vaan tietyissä erikoistilanteissa se antaa jonkun 2. tai 3. parhaan, jossa ei kuitenkaan ole suurta eroa. Tämä siksi, että reittilasku on taatusti optimoitu jonkin verran myös nopeuden puolesta.

Minun on edelleen hyvin vaikea ymmärtää mitä täällä vielä höpistään tuosta pythagoraasta. Jos itse ottaisin vaikka openstreetmap materiaalin, niin muodostaisin sen pohjalta materiaalin, josta löytyy risteyspisteet ja näiden väliset ajomatkat (ajomatkan laskemiseen käyttäisin vaikka Vincentyä). Sitten kun reittiä haettaisiin, niin jos lähtö tai kohdepiste ei ole risteyskohdassa, niin otettaisiin etäisyydet molempiin suuntiin lähimpään risteyskohtaan sitten näiden 2-4 risteyskohdan välillä etsittäisiin mahdolliset reitit karsien esim. vääriin suuntiin lähteviä ja tunnetun reitin pidemmin toteuttavia pois.

Jalmari91 kirjoitti:

Eli toteutin sen näin sqrt(pow((x2-x1),2)+pow((y2-y1),2))

Ihan kiinnostaa, että mitkä noi x ja y on? Eli oliko esim. Y ihan vaan pituuskoordinaatti ja sitten x on leveyskoordinaatti jaettuna 2,44:llä? Siis meinaan että jos koordinaatteja vaan suoraan tökit niin silloinhan systeemisi suosisi voimakkaasti pohjois-etelä suunnassa liikkumista.

Lebe80 kirjoitti:

Ja jotta saataisiin sekotettua pakkaa, niin karttojen reiteissähän tärkeintä on oikeasti löytää nopein reitti, eikä niinkään lyhin. :)

Juu kuten Grez sanoi, yleensä sen saa valita, haluaako nopeimman vai lyhyimmän. Muuten olisinkin tehnyt sellaisen joka etsii nopeimman, mutta kun OpenStreetMapissa ei ole läheskään joka tielle laitettu nopeusrajoitusta. Toki sen voisi arvata, mutta silloin ei välttämättä tulisi kovin luotettavaa tulosta.

Grez kirjoitti:

Minun on edelleen hyvin vaikea ymmärtää mitä täällä vielä höpistään tuosta pythagoraasta. Jos itse ottaisin vaikka openstreetmap materiaalin, niin muodostaisin sen pohjalta materiaalin, josta löytyy risteyspisteet ja näiden väliset ajomatkat (ajomatkan laskemiseen käyttäisin vaikka Vincentyä). Sitten kun reittiä haettaisiin, niin jos lähtö tai kohdepiste ei ole risteyskohdassa, niin otettaisiin etäisyydet molempiin suuntiin lähimpään risteyskohtaan sitten näiden 2-4 risteyskohdan välillä etsittäisiin mahdolliset reitit karsien esim. vääriin suuntiin lähteviä ja tunnetun reitin pidemmin toteuttavia pois.

Esimerkiksi tuolla on selitetty A* algoritmi. Eli tuo h voidaan laskea esimerkiksi pythagoraan lauseella. Tosin tajusin, että minun ei tarvitse laskea sitä tuolla, koska minulla on jo funktio, jolla voi laskea tarkan etäisyyden maaliin. Algoritmin nopeus perustuukin juuri tuon h:n laskemiseen, koska sen ansiosta meidän ei tarvitse käydä joka paikassa, koska jos jo kuljettu matka+lyhin mahdollinen matka maaliin on pitempi kuin jos tunnettu lyhyin matka, niin se ei voi olla lyhyempi kuin tunnettu lyhyin matka.

Grez kirjoitti:

Jalmari91 kirjoitti:

Eli toteutin sen näin sqrt(pow((x2-x1),2)+pow((y2-y1),2))

Ihan kiinnostaa, että mitkä noi x ja y on? Eli oliko esim. Y ihan vaan pituuskoordinaatti ja sitten x on leveyskoordinaatti jaettuna 2,44:llä? Siis meinaan että jos koordinaatteja vaan suoraan tökit niin silloinhan systeemisi suosisi voimakkaasti pohjois-etelä suunnassa liikkumista.

Todellisuudessa käytän tietenkin longitudia ja latitudia, mutta kirjoitin ne huvikseen x ja y. Etäisyydet lasken tuolla tavalla.

Jalmari91 kirjoitti:

Etäisyydet lasken tuolla tavalla.

Mihin silloin voit enää käyttää summaa tai Pythagoraan lausetta? Et kai vain yritä laskea erikseen siirtymää itä-länsisuunnassa ja pohjois-eteläsuunnassa ja sitten yhdistää näitä? Eihän se toimi.

Mietitäänpä kuvitteellista tilannetta, jossa ollaan menossa kohdasta 0N, 0W kohtaan 90N, 90W. Jos lasketaan ensin matkan itä-länsisuunnassa ja sitten pohjois-eteläsuunnassa, päädytään kiertämään neljännes maapallosta länteen ja sitten neljännes pohjoiseen. Toisin päin taas mennään ensin pohjoisnavalle ja sitten ollaankin jo perillä – siis aivan eri tulos! Sama ongelma esiintyy muissakin tapauksissa mutta onneksi hieman vähemmän radikaalisti.

Metabolix kirjoitti:

Mihin silloin voit enää käyttää summaa tai Pythagoraan lausetta? Et kai vain yritä laskea erikseen siirtymää itä-länsisuunnassa ja pohjois-eteläsuunnassa ja sitten yhdistää näitä? Eihän se toimi.

Tajusinkin sen juuri hetki sen jälkeen kun lähetin tuon viestin ja ehdinkin editoida sen tuohon aikaisempaan kirjoitukseen.

Jalmari91 kirjoitti:

Eli tuo h voidaan laskea esimerkiksi pythagoraan lauseella. Tosin tajusin, että minun ei tarvitse laskea sitä tuolla, koska minulla on jo funktio, jolla voi laskea tarkan etäisyyden maaliin

Ja tuo vähensi merkittävästä tarkasteltavien pisteiden määrää.