Tehtävä. Mitkä algoritmit käyvät ratkaisuksi?
Tietoliikenneverkossa on n tietokonetta a1,...an.
Koneiden ai ja aj välillä on suora tietoliikenneyhteys ( esim. kaapeli ) ja yhteyteen liittyy viive p ( i, j ), joka on positiivinen reaaliluku. Viive kertoo kuinka kauan viestin kulkeminen näiden kahden koneen välillä kestää. Yhteydet eivät ole symmetrisiä, ts. voi olla p ( i,j ) erisuuri kuin p ( j,i ).
Lisäksi jokaiseen koneeseen ai liittyy oma viipeensä q (i ), joka kertoo, kuinka kauan koneen ai kautta kulkeva viesti joutuu odottamaan koneessa ai, ennen kuin pääsee jatkamaan matkaansa.
Monen koneen kautta kulkevan vistin vaatima kokonaisaika on summa matkan varrella olevien koneiden ja yhteyksien viipeistä. Mukaan lasketaan myös viestin lähettävän ja vastaanottavan koneen viipeet.
Tehtävänä on etsiä koneille j = 2,...,n NOPEIN REITTI koneesta a1 koneeseen aj. Anna tehtävälle tehokas ratkaisualgoritmi. Selitä lyhyesti ALGORITMIN IDEA ja ANALYSOI SEN AIKAVAATIVUUTTA. Aputietorakenteita ei tarvitse kommentoida.
Tietoliikenneverkossa on n tietokonetta a1,...an.
Koneiden ai ja aj välillä on suora tietoliikenneyhteys ( esim. kaapeli ) ja yhteyteen liittyy viive p ( i, j ), joka on positiivinen reaaliluku. Viive kertoo kuinka kauan viestin kulkeminen näiden kahden koneen välillä kestää. Yhteydet eivät ole symmetrisiä, ts. voi olla p ( i,j ) erisuuri kuin p ( j,i ).
Lisäksi jokaiseen koneeseen ai liittyy oma viipeensä q (i ), joka kertoo, kuinka kauan koneen ai kautta kulkeva viesti joutuu odottamaan koneessa ai, ennen kuin pääsee jatkamaan matkaansa.
Monen koneen kautta kulkevan vistin vaatima kokonaisaika on summa matkan varrella olevien koneiden ja yhteyksien viipeistä. Mukaan lasketaan myös viestin lähettävän ja vastaanottavan koneen viipeet.
Tehtävänä on etsiä koneille j = 2,...,n NOPEIN REITTI koneesta a1 koneeseen aj. Anna tehtävälle tehokas ratkaisualgoritmi. Selitä lyhyesti ALGORITMIN IDEA ja ANALYSOI SEN AIKAVAATIVUUTTA. Aputietorakenteita ei tarvitse kommentoida.
Vastaukset 4
Vanhimmat
http://en.wikipedia.org/wiki/A*_search_algorithm
Vilkaisepa myös http://en.wikipedia.org/wiki/Open_Shortest_Path_First
Cisco-yhtiöltä saat myös formaalit esitykset protokollasta.
Jos panet paremmaksi, olet sikarikas ensi vuonna.
Tehtävä palautuu tavalliseksi lyhimään reitin määräämiseksi suunnatussa verkostossa seuraavasti:
- Kukin verkon solmu (välityspalvelin) korvataan kahdella solmulla i1 JA i2. Tien (i1,i2) pituudeksi otetaan q(i).
- Kukin verkoston linkki [i,j] korvataan kahdella tiellä (i,j) ja (j,i), joiden pituuksiksi tulee p(i,j) ja p(j,i).
- Tie (i,j) alkaa solmusta i2 ja päättyy solmuun j1.
- Nopein reitti palvelimesta u palvelimeen v saadaan määräämällä lyhin reitti muunnetussa verkostossa solmusta u1 solmuun v1.
- Lyhimmän reitin määräämisalgoritmeja on suuri määrä. Googlaa Shortest Paths.
Onko joku lyhimmän polun algoritmi, joka EI käy ratkaisuksi tähän tehtävään?
Johnson´s algorithm?