Esitellään virittävä minimaalipuu (MST, Minimal Spanning Tree) ja Eulerin kierros, joita 2-MST hyödyntää, sekä konveksin peitteen laskeminen, joka on oleellinen CHH-heuristiikassa.
3.2.1 Virittävä minimaalipuu
Virittävällä minimaalipuulla (MST) tarkoitetaan sellaista syklitöntä puuta, joka ei si-sällä ainuttakaan isoloitua solmua ja jonka kaarten pituuksien summa on minimi.
Isoloitu solmu tarkoittaa pistettä, jota ei ole yhdistetty mihinkään verkon pisteistä.
TSP-reitin laskennassa voi olla edullista muodostaa välivaiheena MST, joka sisältää kaikki verkon solmut, sillä näin voidaan mahdollisesti saada verkon minimietäisyyksiä mukaan lopulliseen Hamiltonin kierrokseen.
MST on mahdollista laskea esimerkiksi Kruskalin tai Primin algoritmilla (ks. esim.
Skiena & Revilla, 2003, sivu 220). Tutkielman ohjelmointityön taustalla on käytetty jälkimmäistä menetelmää. Sen aikavaativuus riippuu käytettävistä tietorakenteista ja yksinkertaisimmillaan Prim-algoritmin aikavaativuusluokka on O(n2) käytettäessä boolean-taulukkoa (tosi-epätosi-matriisia) pitämään kirjaa yhdistetyistä solmuista (Skiena, 2008, sivu 195). Myös Lawler (1976, sivut 285-286) puhuu aikavaativuudesta O(n2). Todellisuudessa kompleksisuus riippuu siitä, kuinka MST ja Eulerin kierroksen etsintä toteutetaan ja mitkä ovat niiden kompleksisuudet.
Syöte: geometrinen verkko.
Tuloste: puu (Tprim).
(1) Valitaan satunnainen solmu, josta puuta Tprim aletaan muodostaa
(2) Toistetaan seuraavia kahta toimintoa niin kauan
kuin verkossa on olemassa puuhun kuulumattomia sol-muja:
(2.1) Valitaan sellainen minimipituinen kaari, jonka toinen solmu on nykyisessä puussa ja toinen on puuhun yhdistämätön solmu
(2.2) Lisätään valittu kaari ja uusi solmu puuhun Tprim.
Ohessa on Skienan (2008, sivu 193) esitys Prim-algoritmista vapaasti suomennettuna.
Työ on mahdollista tehdä s.e. yksinkertaisella boolean-taulukolla pidetään kirjaa puu-hun yhdistetyistä ja yhdistämättömistä solmuista, mutta Skiena & Revilla (2003, sivu 221) suosittelevat sen sijaan pitämään kirjaa lyhyimmästä kaaresta sitä mukaa, kun puuhun yhdistetään kaaria.
3.2.2 Eulerin kierroksen etsintä
Eulerin kierroksella tarkoitetaan kierrosta, joka sisältää graafin jokaisen kaaren täs-mälleen kerran. Tunnetuimpia algoritmeja tällaisen kierroksen etsintään ovat Fluery- ja Hierholzer-algoritmit, mutta näihin tai muihinkaan syvällisiin menetelmiin ei pa-neuduta tässä tutkielmassa. Tarkasteltaessa virittävää minimaalipuuta, jossa jokainen kaari on tuplattu, voidaan Eulerin kierros löytää kätevästi seuraavalla pseudokoodilla.
Syöte: kaksi kertaa laajempi puu (Tprim2) esim. taulukkorakenteena.
Tuloste: solmut järjestettynä Eulerin kierrokseksi.
(1) Lue ensimmäinen rivi taulukosta ja merkitse osoitin p osoittamaan ensimmäisen rivin Loppu-sarakkeen koordinaatteihin. Poista ensimmäinen rivi eli kaari yhdistämättömien joukosta (koordinaatit jäävät p:hen).
(2) Etsi yhdistämättömien joukosta rivi, jossa Alku- sarakkeella on samat arvot kuin p-osoittimen koordi- naateilla. Vaihda p osoittamaan tämän uuden rivin Loppu-sarakkeen koordinaatteihin. Poista tämäkin rivi yhdistämättömien joukosta (koordinaatit säilyvät
(3) Toista kohtaa (2), kunnes rivejä ei enää ole ja huolehdi myös alun ja lopun yhdistämisistä.
Osoitin p on lopulta käynyt läpi Eulerin kierroksen virittävässä minimaalipuussa. On oleellista tallentaa kaaret s.e. tuplatut kaaret ovat taulukon puolestavälistä eteenpäin ja alkuperäiset kaaret ovat alusta puoliväliin s.e. järjestys pysyy samana (ja alku- ja lop-pukoordinaatit ovat päinvastaiset). Oletettavasti verkossa ei sallita olevan kahta sol-mua, joilla olisi täsmälleen samat koordinaatit. Oheinen taulukko 1 on esimerkki so-pivasta tallennustavasta.
Taulukko 1: Esimerkki tallennetusta MST:stä, jossa kaaret on kahdennettu.
Alku (x, y) Loppu (x, y) (1.0, 1.0) (0.0, 0.5) (0.0, 0.5) (-1.0, 1.0) (0.0, 0.5) (1.0, -1.0) (0.0, 0.5) (-1.0, -1.0) (0.0, 0.5) (1.0, 1.0) (-1.0, 1.0) (0.0, 0.5) (1.0, -1.0) (0.0, 0.5) (-1.0, -1.0) (0.0, 0.5)
Kuva 6: Graafinen esitys esimerkkiverkosta.
Eulerin kierroksen etsintä on lopulta eräs yksinkertaisimmista toimenpiteistä graa-fiteoriassa. Monimutkaista on lähinnä aikakompleksisuuden määrittäminen. Tässä ta-pauksessa voidaan olettaa aikavaativuuden olevan neliöllinen.
3.2.3 Konveksin peitteen laskeminen
Graham (1972) esitteli menetelmän laskea sellainen minimaalinen ja kaikki solmut ympäröivä joukko, jonka peittämä alue sisältää kaikki verkon solmut, eikä mitään jää määritellyn alueen ulkopuolelle. Tämä onnistuu ajassa O (n log n). Luvussa 2.2 esitel-tiin ristitulosta johdettu kaava (4), jolla voidaan tarkistaa, onko kolmas piste myötä- vai vastapäivään vai suoraan kahdesta muusta pisteestä. Kaavaa tarvitaan algoritmin while-silmukassa, kun solmut on aluksi järjestetty esimerkiksi kulmakertoimen mu-kaiseen järjestykseen. Barber & al. (1996) on myös mahdollinen vaihtoehto konveksin peitteen laskennalle ja on nimeltään ”pikapeite”.
Niin kutsutulla kumilenkkiperiaatteella tarkoitetaan tässä tutkielmassa sitä, että sol-mujen joukko ympäröidään konveksilla peitteellä, minkä jälkeen edetään sisäänpäin yhdistellen sisäsolmut siten, että venymä on mahdollisimman pieni. Ongelmiin voi-daan törmätä, mikäli kohdataan yhtä edullisia venymiä samalla kierroksella ja pitäisi tarkastella kaikkien vaihtoehtojen etenemiset. Tällöin joudutaan yksinkertaisesti valit-semaan esimerkiksi ensimmäisenä vastaan tuleva vaihtoehto.
Syöte: geometrinen verkko (ja pino).
Tuloste: verkon solmut sopivasti järjestettynä esim. taulukossa.
(1) Etsi verkosta T solmu j, jolla on (1.1) max x-koordinaatit
(1.2) ja kohdan 1.1 joukosta min y-koordinaatti, aseta osoitin osoittamaan j:hin, poista j joukosta T (set boolean false) (2) Niin kauan kuin T sisältää käsittelemättömiä
solmuja, toista seuraavat askeleet:
(2.1) olkoon j:n ja seuraavan solmun i välinen kulmakerroin kk
(2.2) aseta i oikeaan kohtaan listassaan s.e.
II) kk pienimmästä, III) kk suurimpaan”
(3) Kun solmut nyt ovat läpikäyntijärjestyksessään, työnnä 2 ensimmäistä solmua pinoon s ja toista seuraavia aske-leita, kunnes solmut on käyty läpi:
(3.1) ota 2 päällimmäistä solmua s:stä ja seuraava solmu n
(3.2) Laske kaavassa (4) esitetty myötä- vai vastapäivä (3.2.1) jos kolmen linja on vastapäivään tai
suorassa, hyväksy n
(3.2.2) else jos kolmen linja onkin myötäpäivään, hyväksy n, mutta hylkää välissä olevat solmut seuraavasti:
ota takaperin n:n lisäksi 2 viimeisintä solmua ja hylkää aina keskimmäinen, kunnes n ja nämä 2 ovat ok
jatka kohdasta 3.1
Seuraavassa on esitetty, kuinka kaavaa (4) sovelletaan ohjelmakoodiin. Edellisen pseudokoodin kohta 3.2 hyödyntää alla olevaa koodia.
Syöte: kolmen solmun koordinaatit.
Tuloste: 1=vastapäivään, -1=myötäpäivään, 0=suoraan.
(1) Olkoon muuttuja a =
((x2 - x1)(y3 - y1)) - ((y2 - y1)(x3 - x1)) (2) Onko a < 0? (2.1) Jos on, palauta -1
(2.2) Jos ei, (2.2.1) onko a > 0
Jos on, palauta 1 (2.2.2) onko a = 0?
Jos on, palauta 0
Useimmissa toteutuksissa, kuten TSP Solver -ohjelmassa, ainoastaan konveksin peit-teen kulmat kuuluvat tulokseen ja mikäli solmuja esiintyy samassa suorassa kulmasol-mujen välillä, ne jätetään huomiotta.