Lyhyimmän reitin laskenta

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Pulma olisi seuraava:
Käytettävissä on verkko jossa on solmuja ja solmujen välissä kulkureittejä joilla kullakin on oma pituus. Pitäisi löytää lyhin tai pisin reitti solmusta A solmuun B. Netistä löytyi ongelmaan ratkaisuja, mutta en löytänyt sitä menetelmää minkä jo aikaa sitten löysin. Tämä menetelmä perustui siihen että homma tehdäänkin käänteisesti, eli määräpisteestä lasketaan lähtöpisteeseen päin ja tällä saadaan huomattavasti pienennettyä tarvittavien laskujen määrää. Onko jollain tietoa tai linkkiä missä tuota periaatetta olisi selvitetty? En muista ihan tarkkaan miten ko. systeemi meni ja sille olisi nyt tarvetta..

Kommentit (3)

Vierailija
cryo
Pulma olisi seuraava:
Käytettävissä on verkko jossa on solmuja ja solmujen välissä kulkureittejä joilla kullakin on oma pituus. Pitäisi löytää lyhin tai pisin reitti solmusta A solmuun B. Netistä löytyi ongelmaan ratkaisuja, mutta en löytänyt sitä menetelmää minkä jo aikaa sitten löysin. Tämä menetelmä perustui siihen että homma tehdäänkin käänteisesti, eli määräpisteestä lasketaan lähtöpisteeseen päin ja tällä saadaan huomattavasti pienennettyä tarvittavien laskujen määrää. Onko jollain tietoa tai linkkiä missä tuota periaatetta olisi selvitetty? En muista ihan tarkkaan miten ko. systeemi meni ja sille olisi nyt tarvetta..

Ei nyt heti tule mieleen muita takaperoisalgoritmeja kuin backtracking, oletko tutustunut siihen?

Yleensä tuollainen ongelma kai ratkaistaan A*:llä.

Vierailija

Hmm...XLispillä ja Lispillä näitä reitityksiä joskus tehtiin...löytyiskö noiden kielien palstoilta jotain.

Algoritmi varmasti löytyy..

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006
cryo
Tämä menetelmä perustui siihen että homma tehdäänkin käänteisesti, eli määräpisteestä lasketaan lähtöpisteeseen päin ja tällä saadaan huomattavasti pienennettyä tarvittavien laskujen määrää. Onko jollain tietoa tai linkkiä missä tuota periaatetta olisi selvitetty?



linkki tuossa jo mainitsikin, että reittien optimointiin käytettävistä algoritmeista yleisin on A* - samaa sarjaa ovat myös depth first, breadth first ja hill climbing, eroina näissä neljässä on se, mitä verkosta tiedetään (tiedetäänkö solmujen välistä etäisyyttä, osataanko laskea "linnunreitti" solmusta maaliin). Monimutkaisissa verkoissa nämä algoritmit saattavat olla käytännössä liian hitaita, niihin on sitten kehitetty erilaisia suboptimaalisia ratkaisuja.

Kaikki nuo algoritmit (itsessään) toimivat myös "takaperin". Takaperoisesta ratkomisesta voi olla hyötyä, jos ei voi käyttää suuntaavaa hakua (eli ei tiedä estimaattia, "linnunreittiä", solmusta maaliin, esim. depth first ja breadth first) ja maalisolmun ympäristössä tilanne on selkeämpi kuin lähtösolmun ympäristössä, jolloin eteenpäin ratkova algoritmi hukkuu helpommin verkon syövereihin. Jos voi käyttää suuntaavaa versiota (hill-climbing ja A* eli voidaan laskea "linnunreitti" solmusta maaliin), niin tällaista ongelmaa ei yleensä ole.

Uusimmat

Suosituimmat