2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Telegrafo tinklai

Taškai: 12

Paveiksle pavaizduotas tarptautinis duomenų tinklas. Kiekvieną tinklą sudaro mazgai, nuspalvinti ta pačia spalva. Dvispalviai mazgai vaizduoja skirtingų tinklų ryšius. Tarptinkliniam ryšiui taikomas mokestis. Jei pranešimas siunčiamas iš vieno tinklo mazgo į kitą tinklą, siuntimo kaina yra:

(kelio, kurį pranešimas turi nukeliauti pirmame tinkle, kaina) + (kelio iki gavėjo visuose kituose tinkluose kaina) × 2.

Kiekviena tinklų šaka turi savo kainą, parodytą grafe.

Pavyzdys:

Pigiausia kaina informacijai iš mazgo A į mazgą F perduoti yra 21:

A→B

B→C

C→E

E→F

2

5

3

4

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

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

Paaiškinimas

Šis uždavinys skirtas rasti mažiausios kainos kelią grafe iš vieno mazgo į kitus mazgus, kreipiant dėmesį į pografių susiejimo taškus. Kelio grafe radimas – vienas svarbių informatikos uždavinių, taikomas daugelyje sričių. Pigiausiam keliui rasti galima naudoti, pavyzdžiui, Dijkstros algoritmą. Dijkstros algoritmas taikomas daugelyje informatikos sričių trumpiausiam keliui rasti, pavyzdžiui, kompiuterių tinklų srityje (maršrutų parinkimo sistemose). Šis algoritmas taip pat taikomas „Google“ žemėlapiuose 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

Raktiniai žodžiai: pigiausio kelio paieška, grafai, pografiai, grafo apėjimas.

Atsakymas

Teisingas atsakymas: 93.

Atkreipsime dėmesį, kad pigiausias kelias ne visada yra trumpiausias. Kad pranešimas iš žaliojo tinklo nukeliautų iki violetinio tinklo, mažiausia kaina 5. Tačiau iš mazgo E keliaujant mazgais N, K, M į mazgą Q arba mazgais N, O, P, M į mazgą Q, kaina didesnė, negu keliaujant mazgais D, F, G, L, H, M į mazgą Q.

Tada:

  • Kaina kelio A, D, F, G, L, H, M, Q = 45 + (6 + 4 + 4 + 5 + 3 + 2) × 2 = 93
  • Kaina kelio A, B, E, N, K, M, Q = (2 + 3) + (12 + 4 + 35 + 2) × 2 = 111
  • Kaina kelio A, B, E, N, O, P, M, Q = (2 + 3) + (12 + 14 + 14 + 3 + 2) × 2 = 95
Interaktyvi užduotis