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.
Etsi tietoliikenneverkossa
4
192
Vastaukset
- Asentaja (työtön)
http://en.wikipedia.org/wiki/A*_search_algorithm
- Hitaan polun kulkija
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. - netw
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.- nopein reitti-algoritmi
Onko joku lyhimmän polun algoritmi, joka EI käy ratkaisuksi tähän tehtävään?
Johnson´s algorithm?
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Porvarimedia: Räsänen vei Lindtmanilta pääministerin paikan
Lisäksi suomalaiset ovat innostuneet tuhlaaman, koska kuluttavat inflaation verran enemmän rahaa. Eikö porvarimedialla723034Ruotsi laskee jälleen bensaveroa, Riikka irvailee tumput suorana
Euron bensa oli persujen vaalilupaus, mutta kohta alkaa olla kolmosella alkavia litrahintoja. Meanwhile in Sverige: "632609SE TAPAHTUI - Pekka Aittakumpu: Avioero
Perussuomalaisten kansanedusta Pekka Aittakumpu käy parhaillaan avioero prosessia. Aittakumpu on siviiliammatiltaan past1292482Anita ei saanut Heikkiä pihalle
Kemijärven kaupunginvaltuusto ei tehnyt tietoisesti laitonta päätöstä. Heikki johtaa kaupunginhallitusta yhäkin.891486Martina Aitolehden rinnalla nähty Matias Petäistö yllättää - Uusi aluevaltaus TV:ssä!
Matias Petäistö on tuttu Erikoisjoukot-realityn tiukkana kouluttajana. Hän on myös tuttu näky Martina Aitolehden parina,341306Drone-epäily Uudellamaalla
Ihmisiä kehotetaan siirtymään sisätiloihin. https://www.is.fi/kotimaa/art-2000012008358.html1021023Emotionalisuuden puute.
Joillain ihmisillä ei vain ole sitä "jotain". Heille kaikki täytyisi "vääntää" rautalangasta. Mutta heistä ei vaan o193994Sait mut mies heikoksi
Yllätti tämä asia nyt kyllä. Olet ollut mielessä koko ajan. Ei riitä pelkkä kevät nyt syyksi. Veit jalat alta. Pannaan m85960Sofia Belorf esittelee Dubain kotinsa
Lääniä on kattohuoneistossa. https://www.is.fi/tv-ja-elokuvat/art-2000011999877.html157893Huulitäytteet ja tekotisssit
Kylillä kulkiissa olen huomannut että tässäkin tuppukylässä on hameväki alkanut muokkaamaan ulkonäköään huulitäytteillä73880