Hamiltono ciklai

HAMILTONO CIKLAI.
UŽDAVINIO SĄLYGA.
Studentai prieš mokslo metų pradžią sumanė pakeliauti po Lietuvos įžymias ir gražias vietas. Jie norėtų aplankyti šias vietas: Kryžių kalną, Zoologijos sodą, Grūto parką, Gedimino pilį ir Lietuvos pajūrį Palangą. Tačiau jie nori, kad šios kelionės išlaidos būtų minimaliausios, todėl jiems svarbu sudaryti tinkamą maršrutą, aplankant kiekviename mieste esantį objektą ir grįžti atgal į Šiaulius. Išvykimo vieta būtų Šiaulių miestas. Studentai keliautų vienu automobiliu, kuris 100 km suvartoja 10 litrų kuro, žinant kad šiai dienai kuro kaina siekia – 3.58 lt/l. Naudodamiesi algoritmais apskaičiuosime, kuriuo maršrutu studentai aplankys norimas vietas pigiausiai.
Kelių atstumai tarp norimų aplankyti vietovių pateikiami 1-oje lentelėje.
1 lentelė. Atstumų lenelė (km).
Palanga
Zoologijos
sodas
Gedimino
pilis
Šiauliai
30
130
160
250
Kryžių
kalnas
30
160
190
300
Palanga
130
160
200
260
Zoologijos
sodas
160
190
200
110
Gedimino
pilis
250
300
260
110
Sunaudojamų degalų kiekis tarp norimų aplankyti vietovių pateikiami 2-oje lentelėje
2 lentelė. Sunaudojamų degalų lentelė (l).
Km
Šiauliai
Kryžių
kalnas
Palanga
Zoologijos
sodas
Gedimino
pilis
Šiauliai
3
13
16
25
Kryžių
kalnas
3
16
19
30
Palanga
13
16
20
26
Zoologijos
sodas
16
19
21
11
Gedimino
pilis
25
30
26
11
UŽDAVINIO SPRENDIMAS.
Remdamiesi sunaudojamų degalų lentele, sudaromas svorinis grafas (1 pav.).
1 pav. Svorinis grafas.
PIGIAUSIOS JUNGTIES ALGORITMAS.
Grafe pažymima pigiausia briauna (nuo bet kurios vietos). Kita briauna pažymima taip pat pigiausia briauna, taip aplankomas kiekvienas miestas po vieną sykį. Gaunamas Hamiltono ciklas.
2 pav. Pigiausios jungties algoritmo svorinis grafas.
Išvykimo pradžia – Kryžių kalnas.
Maršrutas Kryžių kalnas → Šiauliai → Palanga → Zoologijos sodas → Gedimino pilis → Kryžių kalnas. Šiam maršrutui sunaudotų 77 litrus kuro ( 3+13+20+11+30). Kelionės išlaidos sudarytų 77*3.58=275,66litai.
ARTIMIAUSIO KAIMYNO ALGORITMAS.
Grafe pažymima pigiausia briauna, pradedame nuo namų, tai yra nuo Šiaulių, toliau pažymima kita pigiausia briauna. Tai daroma kol bus aplankytas kiekvienas miestas po vieną sykį. Gaunamas Hamiltono ciklas.
3 pav. Artimiausio kaimyno algoritmo svorinis grafas.
Išvykimo pradžia – Šiauliai
Maršrutas → Šiauliai → Kryžių kalnas → Palanga → Zoologijos sodas → Gedimino pilis →
Šiauliai. Šiam maršrutui sunaudotų 75 litrus kuro (3+16+20+11+25). Kelionės išlaidos sudarytų 75*3.58=268,50litai.
KARTOTINIS ARTIMIAUSIO KAIMYNO ALGORITMAS.
Pasirenkama bet kokia viršūnė ir taikomas artimiausio kaimyno algoritmas su pradiniu tašku pasirinktoje viršūnėje. Atliekame tokius veiksmus su visomis grafo viršūnėmis. Iš visų gautų Hamiltono ciklų išsirenkamas mažiausios kainos ciklas. 3 lentelėje pateikiami visi kartotinio artimiausio kaimyno algoritmo gauti ciklai....

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!