2014 2015 2016 2017 2018

Autobusų stotelė

Taškai: 6

Penki bebrų nameliai sustatyti kaip nupiešta paveiksle.
Bebrai nori įrengti autobusų stotelę vienoje iš devynių šešiakampiais pažymėtų vietų.
Paveiksle nurodyti atstumai tarp šešiakampių.
Bebrai nori, kad atstumų suma nuo jų namų iki autobusų stotelės būtų kiek įmanoma mažesnė.
Pažymėkite autobusų stotelės vietą.

 

 

Paaiškinimas

Tai klasikinis grafų teorijos medžio centro paieškos uždavinys.  
Sprendžiame optimizavimo problemą. Ji panaši į realaus pasaulio transporto tinklų uždavinį, kai miesto planuotojams reikia parengti optimalų metro, autobusų, traukinių ir kito transporto linijų  planą.
Informatikoje sukurta daugybė algoritmų optimaliam sprendimui ieškoti. Šiam uždaviniui (kai viršūnių nėra daug) taikomas visiško perrinkimo algoritmas. Jei tinklai didesni (viršūnių daug), toks algoritmas nėra taikomas. Jei reikiamos vietos išrikiuojamos į vieną eilę, galima taikyti medianos skaičiavimo algoritmą. Optimalios viršūnės ieškoma dinaminio programavimo metodu.

Atsakymas

Vienas iš sprendimų – išbandyti visas 9 galimas autobusų stotelės įrengimo vietas ir
apskaičiuoti atstumus. Tam reikėtų atlikti daug skaičiavimų.
Pagalvokime ir raskime gudresnį sprendimą.
Tarkime,  autobusų stotelė bus kelių sankirtoje.
Tada visų atstumų suma nuo namelių iki stotelės bus:
30 + 20 + 10 + 30 + 20 = 110
Jeigu stotelę perkelsime į kairę pusę x metrų, pirmieji du atstumai sutrumpės x metrų, o likusieji trys atstumai nuo namelių iki stotelės pailgės x metrų:
(30 - x) + (20 - x) + (x + 10) + (30 + x) + (x + 20) = 110 +x
Toks pats rezultatas gaunamas perkėlus stotelę per x metrų į dešinę aukštyn:
(30 + x) + (20 + x) + (x +10) + (30 -x) + (-x + 20) = 110 +x
Jeigu stotelę perkelsime į dešinę pusę žemyn per x metrų, atstumų suma bus:  
(30 + x) + (x + 20) + (10 + x) + (x + 30) + (20 - x) = 110 + 3x

Interaktyvi užduotis