Diskrečiosios struktūros. Kursinis darbas

Ištrauka

KURSINIS DARBAS
Užduoties Nr. C25

1. Užduotis (nr. 25)
Turime n miestų, o taip pat žinomi atstumai tarp visų miestų porų. Pirmame
mieste esantis aerouostas turi vienintelį lėktuvą, kuris turi užtikrinti keleivių
susisiekimą tarp visų miestų. Kiekvieną rytą aerouostas žino priverstinių tiesioginių
skrydžių tarp miestų porų sąrašą. Reikia rasti skrydžių maršrutą, tenkinantį sąlygas:
1. Maršrutas turi prasidėti ir baigtis pirmame mieste ir aplankyti visus
miestus;
2. Turi padengti visus nurodytus priverstinius tiesioginius skrydžius;
3. Maršruto ilgis turi būti trumpiausias.
2. Užduoties analizė
Kadangi lėktuvas gali užtikrinti susisiekimą tarp visų miestų porų, tai turime
omenyje, kad nagrinėsime pilnąjį (kiekviena viršūnė yra tiesiogiai sujungta su
kiekviena kita viršūne), svorinį (nes miestai vienas nuo kito yra nutolę tam tikru
atstumu) grafą. Taip pat žinome, kad kiekvieną rytą aerouostas sužino priverstinių
tiesioginių skrydžių tarp miestų porų sąrašą, kas reiškia, kad grafas yra orientuotas
(yra skirtumas, ar priverstinis maršrutas yra iš pirmojo miesto į antrąjį, ar iš antrojo į
pirmąjį). Taip pat žinome, kad maršrutas turi prasidėti pirmame mieste, apkeliauti
visus miestus ir vėl grįžti į pirmąjį, todėl iš to suprantame, kad reikės ieškoti
Hamiltono maršruto. Tačiau negalime būti garantuoti, kad grafas turės Hamiltono
maršrutą (ciklą), padengiantį visus priverstinius tiesioginius skrydžius, pvz., turime 2
grafus su vienodu viršūnių skaičiumi (šiuo atveju, 4). Pirmame grafe priverstinių
skrydžių sąrašas yra toks: 1->2, 2->3 (1 pav.). Antrame grafe priverstinių skrydžių
sąrašas yra toks: 1->2, 3->2 (2 pav.). Priverstiniai skrydžiai žymimi raudonomis
rodyklėmis. Kaip matome, 1 grafe Hamiltono maršrutas yra įmanomas, o antrajame –ne.
Šio uždavinio sprendimui nėra optimalaus algoritmo, kuris duotajame grafe
surastų maršrutą, kuris padengtų visas viršūnes, grįžtų į pirmąją ir dar iš visų
įmanomų maršrutų jis būtų trumpiausias. Todėl šio uždavinio sprendimui taikysiu
pilnąjį visų maršrutų perrinkimą, t.y. sprendimo idėja yra tokia:
1) Generuojamas maršrutas, neatsižvelgiant į priverstinių tiesioginių skrydžių
sąrašą: maršruto ilgis yra lygus n+1 (n - viršūnių skaičius), maršruto pradžia ir
2 pav. 1 pav. pabaiga – 1 miestas, o miestų seka, esanti tarp pirmojo ir paskutiniojo maršruto
sekos elemento, generuojama naudojant kėlinių generavimo algoritmą;
2) Sugeneravus naują maršrutą, einama per priverstinių maršrutų sąrašą ir
tikrinama, ar sugeneruotas maršrutas padengia kiekvieną priverstinį skrydį. Jei
maršrutas tenkina sąlygą, tai jis įterpiamas į galimų maršrutų sąrašą, jei ne –
generuojamas naujas maršrutas;
3) Kai jau patikrinti visi sugeneruoti maršrutai, tada galimų maršrutų sąraše
apskaičiuojamas kiekvieno maršruto ilgis ir iš jų išrenkamas trumpiausias. Jei
galimų maršrutų sąrašas yra tuščias, išvedama, kad nėra jokio galimo maršruto.