Trasų tyrinėjimas

Taškai: 6

Bebrė Onutė yra dviratininkė. Ji tyrinėja vienakryptes trasas, einančias per kaimus, pažymėtus raidėmis nuo A iki Z. Nurodytos visų trasų kryptys ir ilgiai. Šie duomenys pateikti geltonose vėliavėlėse.
Po kiekvienos kelionės bebrė po akmeniu palieka žymą: mėlyną raštelį su užrašytu tam tikru skaičiumi. Ką reiškia skaičiai, surašyti mėlynuose lapeliuose, paliktuose po akmenimis?

A. Trumpiausias atstumas nuo kaimo A iki kito kaimo, aplankant kuo mažiau kaimų.
B. Trumpiausias atstumas nuo kaimo A iki kito kaimo.
C. Trumpiausias atstumas nuo kaimo A iki kito kaimo, kiekvienoje sankryžoje pasukant į kairę.
D. Trumpiausias atstumas nuo kaimo A iki kito kaimo, kiekvienoje sankryžoje pasukant į dešinę.

Paaiškinimas

Trumpiausio mašruto radimo problema yra vadinama trumpiausio kelio problema. Ši problema yra vienas iš pagrindinių informatikos uždavinių, taikomų kasdieniniame gyvenime. Trumpiausio kelio algoritmas taikomas atstumams tarp vietovių rasti automatiškai, pavyzdžiui, mašruto paieškai MapQuest ar Google Maps svetainėse. Dijkstra’os algoritmas yra vienas populiariausių algoritmų, kuriuo ieškoma trumpiausio mašruto. Šiame algoritme priskiriamos pradinės atstumų reikšmės, o tada pažingsniui ieškoma geresnių sprendinių. Sujungus vietoves keliais, gaunamas grafas – labai svarbi duomenų struktūra informatikoje.

Reikšminiai žodžiai: algoritmas, trumpiausio kelio problema, Dijkstra’os algoritmas, grafas.

Atsakymas

Teisingas atsakymas yra B.
 
Norint rasti teisingą atsakymą, atstumai iki kiekvieno kaimo, atsižvelgiant į skirtingas nuorodas nuo A iki D, turi būti skaičiuojami taip:
A – neteisingas, nes  D = 45, Z = 52;
C – neteisingas, nes  C = 33, D = 45, Z = 52;
D – neteisingas, nes  C = 51, D = 45, Z = 52.
Taigi skaičius, užrašytas mėlyname lapelyje, nurodo trumpiausią atstumą nuo kaimo A iki kito kaimo (B atsakymas).
Ieškant trumpiausio kelio, galima naudoti Dijkstra’os algoritmą:
1.    Kiekvienam atstumui tarp sankryžų (kaimų), pradedant nuo pradinio kaimo A, priskirti nulines reikšmes.
2.    Pažymėti A kaip pradinę sankryžą.
3.    Pradedant nuo pradinės sankryžos, apskaičiuoti visus atstumus iki kiekvienos neaplankytos sankryžos. Apskaičiuoti kiekvienos gretimos sankryžos visus atstumus iki kitų sankryžų ir palyginti naujus rezultatus su esamais, o pradinę padėtį suteikti mažiausią reikšmę turinčiai sankryžai.
4.    Atlikus visus skaičiavimus, pradinę padėtį nurodyti kaip aplankytą. Aplankytoji sankryža nebus daugiau lankoma.
5.    Pasirenkti neaplankytą sankryžą su mažiausia reikšme, ją pažymėti kaip pradinę sankryžą ir grįžti prie 3 žingsnio.
6.    Jeigu paskutinė sankryža (Z) tampa aplankytąja, tada sustoti. Algoritmas baigtas.

 

 
Informacija atnaujinta 2016-10-18 10:55:36
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.