Keliaujančio pirklio uždavinys
•Kiekvienai nagrinėjamo grafo briaunai bus priskirtas skaičius. Tie skaičiai gali turėti įvairias reikšmes: gali parodyti išlaidas, atstumą, laiką, pakelės medžių skaičių ir pan. Jei grafo briaunoms skirti kokie nors skaičiai, juos vadinsime briaunų svoriais, o patį grafą – svoriniu grafu. Kalbėdami apie pigiausią, trumpiausią, greičiausią ir t.t. maršrutą, mes vartosime sąvoką optimalus maršrutas. Uždavinių tikslas – rasti optimalų maršrutą, kuris prasideda ir baigiasi nurodytoje viršūnėje ir eina per kiekvieną viršūnę lygiai vieną kartą.
•Ciklas, kuris prasideda kurioje nors grafo viršūnėje ir, patekęs į kiekvieną kitą grafo viršūnę lygiai vieną kartą, vėl grįžta į pradinę viršūnę, vadinamas Hamiltono ciklu. Deja, nėra universalaus būdo atsakyti į klausimą, ar grafas turi Hamiltono ciklą. Paprastai, kuo grafe daugiau briaunų, tuo tikėtiniau, kad jis turi Hamiltono ciklą.
Dirako teorema
Tarkime, kad jungusis grafas turi ne mažiau kaip tris viršūnes. Jei kiekviena grafo viršūnė yra gretima bent pusei viršūnių, tai grafas turi Hamiltono ciklą.
•Grafas, turintis N viršūnių, ir jei kiekviena viršūnė yra gretima visoms likusioms, vadinamas pilnuoju grafu. Pilnasis N-viršūnis grafas turi (N-1)!=1´2´3´…´N Hamiltono ciklų. Pusė jų pakartoja kitą pusę atvirkščia tvarka.
•Pilnojo svorinio grafo optimalaus Hamiltono ciklo radimo uždavinys daug kur taikomas ir paprastai vadinamas keliaujančiojo pirklio uždaviniu (KPU), nors nebūtinai sąlygoje kalbėsime apie prekybą.
KPU sprendimo jėgos algoritmas
•Surašome visus svorinio grafo Hamiltono ciklus.
•Sudedame kiekvieno Hamiltono ciklo visų briaunų svorius (jų suma vadinama ciklo svoriu).
•Iš visų išrenkame mažiausio svorio ciklą – jis ir yra uždavinio sprendinys.
•Šis algoritmas turi tik vieną trūkumą – jis reikalauja patikrinti visų grafo ciklų svorius. O kuo didesnis viršūnių skaičius, tuo daugiau ciklų mums reikės rasti ir patikrinti. Taigi, algoritmus galėtume suskirstyti į gerus (kuriuos dar vadinsime efektyviais) ir blogus (juos dar vadinsime neefektyviais).
•Apytikrio algoritmo terminą vartosime, kalbėdami apie algoritmą, dažniausiai duodantį sprendinį, pakankamai artimą optimaliam.
Artimiausiojo kaimyno algoritmas
•Kelionę pradedame iš namų.
•Kad ir kur bebūtume, kitą dar neaplankytą viršūnę renkamės tą, į kurią nuvykti pigiausia (t.y. artimiausią kaimyną). Jei tokių viršūnių yra kelios, galime rinktis bet kurią. Taip elgiamės, kol aplankome visas viršūnes.
•Iš paskutinės grįžtame namo.
Kartotinis artimiausiojo kaimyno algoritmas
•1 žingsnis. Pasirenkame bet kokią viršūnę ir taikome artimiausiojo kaimyno algoritmą.
•2 žingsnis. Kartojame 1 žingsnį su visomis grafo viršūnėmis.
•3 žingsnis. Iš visų 2 žingsnyje gautų Hamiltono ciklų išrenkame geriausią sprendinį.
•4 žingsnis. Perrašome 3 žingsnyje gautą sprendinį, pradiniu tašku imdami namų viršūnę.
Pigiausios jungties algoritmas
•1 žingsnis. Pirmiausia išrenkame mažiausio svorio briauną. (Jei tokių yra daugiau nei viena – renkamės bet kurią). Šią briauną pasižymime.
•2 žingsnis. Ieškome kitos nepažymėtos briaunos ir pasižymime ją, išskyrus atvejus, kai •ji sudaro mažesnį ciklą; •ji yra trečia pažymėta briauna, išeinanti iš vienos viršūnės. •Jei tokių briaunų yra daugiau nei viena, rinkis bet kurią.
•3, 4, … žingsniai. Kartojame 2 žingsnį, kol susidarys visas Hamiltono ciklas.
JUNGIANTIEJI MEDŽIAI IR
ŠTEINERIO MEDŽIAI
•Bendras visų šio tipo uždavinių bruožas – reikia sujungti keletą objektų (svorinių grafų viršūnių) taip, kad iš kiekvieno objekto galima būtų patekti į bet kurią kitą ir kad bendras sudaryto tinklo svoris būtų minimalus. Jungiant objektus į tinklą, neatsižvelgiama į tai, kiek nepatogūs ar komplikuoti gali būti keliai, jungiantys konkrečius objektus. Vienintelis tikslas, sprendžiant tokius uždavinius, yra sudaryti kiek galima mažesnio bendro svorio tinklą. Tokio tipo uždaviniai yra vadinami minimalaus tinklo uždaviniais. Uždavinio sprendinys - pradinio grafo pografis. Sprendinio pografio viršūnės turi apimti visas pradinio grafo viršūnes. Sprendinio pografis taip pat turi tenkinti šias dvi papildomas sąlygas:
•Jis turi būti jungusis. Tai išplaukia iš to, kad tinklas turi jungti visas grafo viršūnes.
•Jame neturi būti ciklų (t.y. turi būti neįmanoma apeiti sprendinio pografio ar jo dalies ir sugrįžti į pradinę viršūnę).
Medžių savybės
Jungusis grafas, neturintis ciklų, vadinamas medžiu.
•1 savybė. Jei grafas yra medis, tai bet kurias dvi jo viršūnes jungia vienas ir tik vienas kelias. Ir atvirkščiai, grafas, kurio bet kurias dvi viršūnes jungia tik vienas kelias, yra medis.
•2 savybė. Visos medžio briaunos yra tiltai. Atvirkščiai, jungusis grafas, kurio visos briaunos – tiltai, yra medis.
•3 savybė. N viršūnių medis turi N-1 briauną. Atvirkščias teiginys teisingas ne visada.
•4 savybė. Jungusis N viršūnių ir N-1 briaunos grafas yra medis.
•Tarkime, kad G yra jungusis svorinis grafas. Tarp visų grafo G jungiančiųjų medžių yra vienas (galbūt keli), kurio bendras svoris yra mažiausias. Toks medis vadinamas grafo G minimaliuoju jungiančiuoju medžiu. Todėl ieškodami minimalaus tinklo mes spręsime minimaliojo jungiančiojo medžio (MJM) uždavinius.
Kruskalo algoritmas MJM radimui
•1 žingsnis. Randame pigiausią briauną (jei tokių yra ne viena, renkamės bet kurią). Ją pasižymime.
•2 žingsnis. Ieškome pigiausios dar nepažymėtos briaunos ir ją pasižymime. Jikiu būdu negalime sudaryti ciklo.
•3, 4 ir t.t. žingsniai. Kartojame 2 žingsnį tol, kol pažymėtų briaunų galai (viršūnės) panaudos visas grafo viršūnes. Pažymėtos briaunos ir sudaro ieškomą minimalųjį jungiantįjį medį. Kruskalo algoritmas yra efektyvus algoritmas, kurio sprendinys optimalus.
• Jei nereikalaujama, kad tinklo viršūnės (mazgai) būtų grafo viršūnės (kitaip tariant, leista kurti tinkle naujus mazgus), tai minimalus jungiantysis medis gali ir nebūti geriausias viršūnių sujungimo būdas.
•Trumpiausias iš visų tinklų, jungiančių taškų aibę, vadinamas trumpiausiuoju tinklu.
•Bet kuris tinklo mazgas, kuriame trys atšakos susieina 120 laipsnių kampu, vadinamas Šteinerio tašku.
Kaip rasti tris taškus jungiantį trumpiausią tinklą?
•Jei vienas iš trikampio, sudaryto iš duotųjų taškų, kampas didesnis arba lygus 120°, tai trumpiausias tinklas sutampa su minimaliuoju jungiančiuoju medžiu.
•Jei visi trikampio kampai yra mažesni už 120°, tai trumpiausias tinklas ir minimalus jungiantysis medis nesutampa. Trumpiausiąjį tinklą gauname, radę Šteinerio mazgo tašką ir sujungę jį su visomis viršūnėmis.
•Trumpiausias tinklas, jungiantis keletą taškų, yra arba -Minimalus jungiantysis medis (nėra vidinių mazgų), arba -Šteinerio medis (yra vidinių mazgų).
Susiję įrašai: