Tehtävä. Mitkä algoritmit käyvät ratkaisuksi?
Voiko Johnson'in algoritmia käyttää?
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.
Voiko Johnson'in algoritmia käyttää?
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
Vanhimmat
Ei vielä vastauksia
Aloittaja odottaa vastauksia. Kerro oma näkemyksesi ensimmäisenä.