BEBRO konkurso užduotys 2018

 

Mokami keliai

Taškai: 9

Benas nusprendė važiuoti iš Hamperio į Mugą. Žemėlapyje miestai žymimi apskritimais su raidėmis, linijos rodo dvipusio eismo kelius. Keliai gali kirstis, jų sankirtos pažymėtos skrituliais. Skaičius prie kelio rodo mokesčio sumą, kurią reikia sumokėti automobiliui įvažiuojant į šį kelią. Automobiliai gali keisti kryptį sankirtose, bet privalo sumokėti mokestį už kelią, į kurį įvažiuoja. Pavyzdžiui, iš B į C galima nuvykti važiuojant 18 ir 6 keliu ir tai kainuotų 24 = 18 + 6.

Kokį mažiausią kelių mokestį turi susimokėti Benas, kad nuvyktų iš Hamperio į Mugą?

Paaiškinimas

Grafų teorijoje trumpiausio kelio problema yra radimas kelio tarp dviejų svorinio grafo viršūnių, kad briaunų svorių suma būtų mažiausia.

Problema beieškant trumpiausio kelio tarp dviejų apmokestintų kelių sankirtos, kurių apmokestinimas neturi įtakos nuvažiuotam atstumui, gali būti suvesta į klasikinę trumpiausio kelio problemą, kuri vaizduoja susikirtimus panaudojant papildomas viršūnes ir kraštines. Klasikinė trumpiausio kelio problema gali būti išspręsta naudojantis Dijkstros algoritmu.

https://lt.wikipedia.org/wiki/Dijkstros_algoritmas

 

Atsakymas

Paveiksle pažymėtas pigiausias maršrutas:


 

Norint įrodyti, kad šis maršrutas yra optimaliausias, būtina palyginti visus galimus variantus.

Tačiau galima peržvelgti kelius ir įsitikinti, kad reikia vengti brangių kelių: kelio iš B į Mugą, taip pat kelio iš A į F ir iš B į F.

Pažymėkime sankirtas

Peržvelgiame maršrutus ir telieka patikrinti du maršrutus

Galimi maršrutai

Kaina

Hamperis – A – C – k – D – Mugas

13 + 6 + 9 + 7 + 6 = 41

Hamperis – A – G – E – D – Mugas

13 + 7 + 9 + 7 + 6 = 42

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39