2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Draugų lankymas

Taškai: 6

Linos draugai gyvena A, B, C, D, E kaimeliuose. Ji nori juos visus aplankyti per vieną dieną, naudodamasi viešuoju transportu. Kiekvieną kaimelį Lina aplanko tik vieną kartą ir tą pačią dieną sugrįžta namo. Nurodyta kiekvieno atstumo tarp kaimelių kaina. Didžiausia vieno atstumo kaina – 3 monetos.

Visų draugų aplankymas Linai kainuos 11 monetų, jeigu ji pasirinks tokį maršrutą:

Namai → B → E → A → D → C → Namai.

Kokiu maršrutu keliaudama Lina išleistų mažiausiai monetų? Jei tokie maršrutai keli, pakanka surasti vieną jų.

Spustelėk kaimelių pavadinimų raides, kad pažymėtum maršrutą.

Namai → ____ → ____ → ____ → ____ → ____ → Namai

Paaiškinimas

Optimalaus sprendimo paieška – pagrindinis informatikos uždavinys. Galima vizualizuoti šio optimizavimo uždavinio aprašą grafu, kur draugų kaimeliai būtų mazgai, o atstumai tarp jų – grafo briaunos. Šis uždavinys taptų trumpiausio kelio (mažiausiai monetų) uždaviniu. Tai panašu į garsųjį Keliaujančio pirklio uždavinį.

Tokius uždavinius sudėtinga spręsti kompiuteriu. Vengiant gausybės sprendimų tikrinimo, dažniausiai pasirenkamas euristinis algoritmas. https://lt.wikipedia.org/wiki/Keliaujan%C4%8Dio_pirklio_u%C5%BEdavinys

Raktiniai žodžiai: keliaujančio pirklio uždavinys, optimizavimas.

Atsakymas

Galimi du teisingi atsakymai:

Namai → B → E → C → A → D → Namai

Namai → D → A → C → E → B → Namai

Abu teisingi sprendimai yra atvirkštiniai vienas kitam. Daugiau teisingų atsakymų nėra, nes vienas kelionės atstumas iš namų arba namo Linai kainuoja 3 monetas arba 2 monetas, todėl jei kitiems keturiems atstumams, ir lieka po 1 monetą, vis tiek iš viso bus 9 monetos.

Kiti sprendimai brangesni:

10 monetų: Namai → A → D → C → E → B → Namai

10 monetų: Namai → A → E → B → C → D → Namai

10 monetų: Namai → B → C → E → A → D → Namai

10 monetų: Namai → B → E → A → C → D → Namai

10 monetų: Namai → B → E → C → D → A → Namai

10 monetų: Namai → C → B → E → A → D → Namai

10 monetų: Namai → D → A → E → B → C → Namai

10 monetų: Namai → D → A → E → C → B → Namai

10 monetų: Namai → D → C → A → E → B → Namai

10 monetų: Namai → D → C → B → E → A → Namai

11 monetų: Namai → B → E → A → D → C → Namai

11 monetų: Namai → C → D → A → E → B → Namai

Interaktyvi užduotis