Kelionė upeliais aukštyn (2014)
Taškai: 9
Norėdamas grįžti namo, bebriukas turi įveikti keletą upelių. Kad įgytų energijos kelionei, jis sugriaužia 15 šakelių. Keliaudamas bebriukas turi įveikti įvairias kliūtis. Tam reikalinga energija, kurios sąnaudos atitinka suvalgytų šakelių skaičių:
| Kliūtis | Energijos sąnaudos |
|
|
2 |
 |
3 |
 |
5 |
Paveiksle pavaizduoti upeliai ir juose esančios kliūtys. Raidės A, B, C, D ir E žymi galimus bebriuko kelius.
Kurį iš pateiktų maršrutų turėtų pasirinkti bebriukas?
Primename, kad keliauti jis pradeda turėdamas 15 šakelių energijos.
A. Pradžia → A → C → E → Namai
B. Pradžia → A → C → E → D → Namai
C. Pradžia → B → C → D → E → Namai
D. Pradžia → B → C → D → Namai
Ši upelių sistema vaizduoja tinklą – svarbų informatikos duomenų vaizdavimo būdą. Vadinamieji tinklo mazgai yra upelio kliūtys, žymimos raidėmis A, B, C, D ir E, taip pat žodžiai Pradžia ir Namai. Energijos suvartojimas kliūtims įveikti – tai tarsi atstumas tarp sujungtų mazgų. Taigi bebriukas ieško trumpiausio kelio tarp mazgo „Pradžia“ ir mazgo „Namai“.
Informatikoje tokie uždaviniai paprastai sprendžiami taikant grafų teoriją – tinklas atvaizduojamas grafu. Buvo sukurta keletas trumpiausiojo kelio paieškos algoritmų, vienas kurių pavadintas žymaus informatiko E. Dijkstra vardu – vadinamasis Dijkstra trumpiausiojo kelio algoritmas. Kitas gana žinomas algoritmas – Floyd-Warshall trumpiausiojo kelio algoritmas.
Teisingas atsakymas:
Pradžia → B → C → D → E → Namai
Skirtingiems maršrutams reikalingas skirtingas energijos kiekis.
Štai kaip skaičiuojama:
Pradžia → A → C → E → Namai: 2 + 5 + 5 + 5 = 17
Pradžia → A → C → E → D → Namai: 2 + 5 + 5 + 2 + 3 + 5 = 22
Pradžia → B → C → D → E → Namai: 3 + 3 + 2 + 2 + 5 = 15.
Pradžia → B → C → D → Namai: 3 + 3 + 2 + 3 + 5 = 16
Pradžia → B → C → D → E → Namai – vienintelis maršrutas, kuriam bebriukas turi pakankamai energijos (suvalgęs 15 šakelių).