Draugų lankymas
Taškai: 9
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
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.
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