BEBRO konkurso užduotys 2018

 

Ryšių tinklai

Taškai: 12

Tarptautiniai ryšių tinklai pavaizduoti skirtingomis spalvomis. Tinklus sudaro ryšių linijos ir mazgai (taškai, kuriuose susikerta viena ar kelios linijos). Dvispalviai mazgai vaizduoja skirtingų tinklų ryšius. Skaičiai virš linijų rodo siuntimo tomis linijomis kainą. Kai pranešimas siunčiamas iš vieno tinklo mazgo į kito tinklo mazgą, siuntimo kainą sudaro:

 

(kelio, kuriuo pranešimas siunčiamas viename tinkle, kaina) + (kelio, kuriuo pranešimas siunčiamas kitame tinkle, kaina) × 2.


Pavyzdys:

 

Pigiausia kaina informacijai persiųsti iš mazgo A į F yra 21:


 

2+5+(3+4)*2=21 

 


Kokia yra mažiausia kaina pranešimui persiųsti iš mazgo A į Q?

 


Į atsakymo laukelį įrašykite sveikąjį skaičių.

 

 

Paaiškinimas

Šiame uždavinyje reikia rasti mažiausios kainos kelią grafe iš vieno mazgo į kitą, kreipiant dėmesį į pografių sujungimo taškus. Kelio grafe radimas – vienas svarbesnių informatikos uždavinių, taikomas daugelyje sričių. Pigiausiam keliui rasti galima naudoti, pavyzdžiui, Dijkstros algoritmą. Šis algoritmas taikomas daugelyje informatikos sričių, kai ieškoma trumpiausio kelio, pavyzdžiui., kompiuterių tinkluose, maršrutų parinkimo sistemose. Šį algoritmą naudoja „Google“ žemėlapiai trumpiausiam maršrutui rasti iš vienos geografinės vietos į kitą. Biologijoje šis algoritmas taikomas konstruojant infekcinių ligų plitimo tinklo modelį. Deja, dėl šiame uždavinyje pasirinkto būdo kainoms skaičiuoti Dijkstros algoritmas negali būti pritaikytas tiesiogiai.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Atsakymas

93

 

 
Informacija atnaujinta 2017-11-13 16:52:39
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.