Hamiltono ciklai. Prekių pristatymo į parduotuves optimaliausias kelias: UAB "Celestina"

Sąlyga. UAB „Celestina“ įsikūrusi Kaune. Ji užsiima ne maisto prekių prekyba. Kiekvieną dieną prekes reikia nuvežti į kitas parduotuves, kurios yra Jonavoje, Marijampolėje, Vilniuje, Alytuje, ir grįžti vėl i Kauną..
Kad vairuotojui nereiktų važiuoti didelių atstumų ir nešvaistyti degalų, tai vadovui aktualu parinkti optimaliausią maršrutą.
Tarkime, kad taškas A – Kaunas, B –Jonava, C – Vilnius, D – Alytus, E –Marijampolė.
Taikant pigiausios jungties algoritmą, pasirenkamas trumpiausias atstumas tarp bet kokių miestų. Maršrutą pradėsime nuo taško A. Tai pradžios taškas. Susidaro ciklas.
Pagal pigiausios jungties algoritmą optimaliausias kelionės maršrutas yra Kaunas-Jonava-Vilnius-Marijampolė-Alytus-Kaunas, kurio ilgis 305 km
2. Artimiausio kaimyno algoritmas
Taikant artimiausio kaimyno algoritmą, pasirenkamas trumpiausias atstumas nuo išeities ( Kaunas) iki kurio nors kito miesto. Kelionę pradėsime Kaune. Taigi gauname ciklą ABDECA = 31+72+47+124+93 = 367 km.
Pagal artimiausio kaimyno algoritmą optimaliausias kelionės maršrutas yra Kaunas-Jonava-Alytus-Marijampolė-Vilnius-Kaunas, kurio ilgis 367km.
3. Kartotinas artimiausio kaimyno algoritmas
Taikant kartotinio artimiausio kaimyno algoritmą, pasirenkamas trumpiausias atstumas nuo išeities taško (bet kurio miesto)
a) kelionę pradedame taške A (Kaunas). Tuomet gauname ciklą ABDECA=31+72+47+124+93=367km.
b) kelionę pradedame taške B (Jonava). Tuomet gauname ciklą BCDEAB=31+57+47+95+75=305km.
c) kelionę pradedame taške C (Vilnius).. Tuomet gauname ciklą CBADEC=75+31+57+47+124=334km
d) kelionę pradedame taške D (Alytus).. Tuomet gauname ciklą DEABCD=47+57+31+75+95=305km.
e) kelionę pradedame taške E (Marijampolė).. Tuomet gauname ciklą EDEBCE=47+57+31+75+124=334km.
Sudarius visus galimus variantus važiuoti pas artimiausią...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!