Kuinka kannattaa lähteä ratkaisemaan ongelmaa, jossa pitää saa selville lyhin reitti
Esim.
pisteestä A pisteeseen D, kun tiedetään, että A->B menee aikaa 1 A->C menee 2, C->D menee 1 ja B->C:n menee 0:lla.
Tosin ongelma on merkittävästi isompi (tuhansia vaihtoehtoisia reittejä) oikeasti, kuin tuossa esimerkkissä. Ensimmäisenä ja toistaiseksi ainuana tulee mieleen ratakaista jotenkin kaikki reitit ja katsoa mikä on nopein, mutta tästä tulee kooltaan todella valtava ratkaista. Onko olemassa esim. matriisi laskennan avulla tapahtuvaa ratkaisua.
Vastaus riippuu ongelman yksityiskohdista. Onhan noita valmiita algoritmeja joista valita. Onko reitti jo määritelty jollain tietyllä tietorakenteella?
Breadth first search tai depth first search eivät ole tarpeeksi tehokkaita vähänkään suuremmissa verkoissa. A*-reitinhakualgoritmi on jo parempi, jos sitä on mahdollista käyttää. "Algoritmi toimii minimoimalla sekä kuljettua matkaa että heurestisesti arvioitua jäljellä olevaa matkaa. Optimaalinen annetulla heuristisella funktiolla."
Tuossa englanniksi yksi esimerkkisivu:
http://computer.howstuffworks.com/routing-algorithm3.htm
suomeksi:
http://www.google.com/search?q=reitinhaku algoritmi
Noista pitäisi pystyä hakemaan lisätietoa.
Käytä Dijkstran algoritmia. Tuhansien reittien joukossa nopein reitti on nopeasti löydetty.
Aihe on jo aika vanha, joten et voi enää vastata siihen.