Kauppamatkustajan ongelman ratkaisualgoritmien vertailu

(1)

Kauppamatkustajan ongelman ratkaisualgoritmien vertailu

Tuomas Hyvönen

Pro gradu –tutkielma

Tietojenkäsittelytieteen laitos

Tietojenkäsittelytiede

(2)

i

ITÄ-SUOMEN YLIOPISTO, Luonnontieteiden ja metsätieteiden tiedekunta, Kuopio Tietojenkäsittelytieteen laitos

Tietojenkäsittelytiede

Tuomas Hyvönen: Kauppamatkustajan ongelman ratkaisualgoritmien vertailu Pro gradu –tutkielma, 41 s., 1 liite (3 s.)

Pro gradu –tutkielman ohjaaja: FT Matti Nykänen toukokuu 2018

Tiivistelmä:

Kauppamatkustajan ongelma (TSP, Traveling Salesman Problem) on tutkituimpia kombinatorisen optimoinnin ongelmia tietojenkäsittelytieteessä. Sen juuret ulottuvat jopa 1800-luvulle aikaan ennen automaattisen tietojenkäsittelytieteen syntyä, sillä esimerkiksi William Rowan Hamiltonin ja Thomas Penyngton Kirkmanin tiedetään kä- sitelleen sitä osana verkko- eli graafiteorian alan tutkimuksia. Koska ongelman opti- miratkaisujen tavoittamiseen tunnetaan toistaiseksi ainoastaan eksponentiaalisen ajan vieviä algoritmeja, sitä on syytä lähestyä heuristiikoilla ja approksimointialgoritmeilla.

Tutkielma esittelee kolme algoritmia TSP-ongelman ratkaisemiseen heuristisesti, toisin sanoen pyrkien parhaan mahdollisen ratkaisun tavoittelun sijaan ratkaisemaan ongelma suhteellisen tarkasti ja kohtuullisessa ajassa. Ensimmäinen ja laajasti tunnettu lähimmän naapurin heuristiikka (NNH, Nearest Neighbor Heuristic) on ensimmäisim- piä tunnettuja ratkaisumenetelmiä ja niin kutsuttu ahne algoritmi. Toinen ja myös laajasti tunnettu kaksois-virittävän minimaalipuun algoritmi (2-MST, Double Minimal Spanning Tree) takaa korkeintaan 2 kertaa optimaalista ratkaisua kehnomman kauppamatkustajan reitin hyödyntäen virittävää minimaalipuuta sekä niin kutsuttua Eulerin kierrosta. Kolmas algoritmi (CHH, Convex Hull Heuristic) perustuu niin kutsuttuun kumilenkkiperiaatteeseen hyödyntäen konveksia peitettä, johon toisinaan yhdistetään nimet Stewart ja Bodin.

Kokeellisen tutkimuksen taustalla on omatekoinen sovellus TSP Solver, joka on ohjel- moitu Java-kielellä NetBeans 8 -ohjelmistokehitysvälineellä. FT Pekka Kilpeläisen ResourceTracker sekä omat tilastolliset analyysit toimivat apuna kaikkien kolmen algoritmin vertailuissa. Tarkasteltavana ovat tsplib-muodossa olevat geometriset verkot, joita on julkisesti saatavilla muun muassa Waterloon yliopiston verkkosivuilla.

Avainsanat: Kauppamatkustajan ongelma, geometrinen verkko, heuristiikat, tsplib ACM-luokat (ACM Computing Classification System, 1998 version):

F.2.2 Ei-numeeriset algoritmit ja ongelmat G.2.2 Graafiteoria

(3)

UNIVERSITY OF EASTERN FINLAND, Faculty of Science and Forestry, Kuopio School of Computing

Computer Science

Tuomas Hyvönen: A comparison between Traveling Salesman algorithms Master’s Thesis, 41 pp., 1 appendix (3 p.)

Supervisor of the Master’s Thesis: PhD Matti Nykänen May 2018

Abstract:

The Traveling Salesman Problem (TSP) has been one of the most studied combinato- rial optimization problems in computer science. Its roots lead back to 1800s before the automated computer science existed, for example William Rowan Hamilton and Thomas Penyngton Kirkman are known to have studied the problem as a part of their graph theory researches. The computing of optimum TSP solution is currently known to have exponential time-consuming algorithms only and thus it is necessary to ap- proach the problem with heuristics and approximate algorithms.

The thesis presents three algorithms in order to solve the TSP heuristically, in other words, instead of aiming for the best possible solution to solve the problem, relatively low time and relatively high accuracy are concentrated on. The first and widely known Nearest Neighbor Heuristic (NNH) is one of the first solving methods and it is a so- called greedy algorithm. The second and also widely known Double Minimal Span- ning Tree algorithm (2-MST) guarantees a maximum of 2 times the optimum solution by using the minimal spanning tree, as well as the so-called Euler cycle. The third algorithm (CHH, Convex Hull Heuristic) is based on the so-called elastic band idea and uses a convex hull that is sometimes combined with the names Stewart and Bodin.

An experimental study in the background is a self-made application TSP Solver, which is implemented with Java and NetBeans 8 software development tool. PhD Pekka Kil- peläinen’s ResourceTracker, as well as the author’s own statistical analyzes are used in the comparisons of the three algorithms. Tsplib file format and geometric graphs from the University of Waterloo website are also discussed.

Keywords: Traveling Salesman Problem, Geometric graph, Heuristics, tsplib

CR Categories (ACM Computing Classification System, 1998 version):

F.2.2 Nonnumerical Algorithms and Problems G.2.2 Graph Theory

(4)

iii

Esipuhe

Kirjoittajana tahdon erityisesti kiittää kärsivällistä ja tieteelle uskollista ohjaajaani ja tutkielman tarkastajaani Matti Nykästä sekä kandidaatintutkielman ohjaajaa Pekka Kilpeläistä, kuten myös tämän tutkielman toista tarkastajaa Simo Juvastetta. Kiitän myös vanhempiani, siskoani, kahta veljeäni ja isovanhempiani tuesta sekä kannustuk- sesta. Opiskelija-asumisen tukemisesta kiitokset Marjalle ja Pentille. Tutkielma on omistettu teille kaikille ja toivon sen herättävän lukijassaan mitä syvällisintä mielen- kiintoa matematiikkaa, ohjelmointia, tekniikkaa, luonnontiedettä ja ongelmanratkon- taa kohtaan.

Kuopiossa 23.5.2018 Tuomas Hyvönen

(5)

Lyhenne- ja käsiteluettelo

1-puu Puutietorakenne, jossa on yksi kierros.

2-MST “Double Minimal Spanning Tree”, virittävää minimaalipuuta hyödyn- tävä 1,0-approksimointialgoritmi, tutkielmassa tarkasteltava toinen algoritmi.

BFS ”Brute Force Search” eli laskentamenetelmä, jolla etsitään jokainen mahdollinen tulos ja valitaan niiden joukosta paras mahdollinen.

CHH “Convex Hull Heuristic”, konveksin peitteen heuristiikka, tutkielmassa tarkasteltava kolmas algoritmi.

euklidinen etäisyys

Kahden pisteen (𝑥₁, 𝑦₁) ja (𝑥₂, 𝑦₂) etäisyys, joka lasketaan kaavalla

√(𝑥₂− 𝑥₁)²+ (𝑦₂− 𝑦₁)². Eulerin kierros

Yhtenäinen kierros, jossa esiintyy jokainen verkon kaari täsmälleen kerran.

GitHub Maailman suurin lähdekoodi-verkkopalvelu, jonka kautta voi julkaista sovellusten lähdekoodeja, kuten .java-tiedostoja.

Hamiltonin kierros

Yhtenäinen kierros, jossa esiintyy jokainen verkon solmu täsmälleen kerran. Kauppamatkustajan ongelmassa on kyse pienipainoisimman täl- laisen kierroksen löytämisestä.

heuristinen algoritmi, heuristiikka

Algoritmi, joka pyrkii optimaalisen ratkaisun sijaan suhteellisen hyvään nopeuteen ja tarkkuuteen.

isoloitu solmu

Solmu, josta ei ole yhteyksiä mihinkään verkon solmuun.

isomorfinen verkko, isomorfinen esitys

Matemaattisesti sama graafi toisella tavalla esitettynä s.e. kytkennät ei- vät muutu.

karteesinen koordinaatisto

Eräs tapa hahmottaa pisteiden sijainnit avaruudellisesti. Karteesisessa koordinaatistossa on x-akseli vaaka-akselina ja y-akseli pystyakselina.

On olemassa myös mm. napa-, sylinteri- ja pallokoordinaatistot.

(6)

v kolmioepäyhtälö

Kolmion mikä tahansa sivu on aina korkeintaan yhtä pitkä kuin kahden muun sivujen a ja b pituuksien summa ja vähintään sen pituinen kuin kahden muun sivujen a ja b pituuksien erotuksen itseisarvo.

| |a| – |b| | ≤ |a + b| ≤ |a| + |b| .

konveksi ”Kupera”, jos yksikään pisteiden välinen jana eli kaari ei kuulu määri- tellyn alueen ulkopuolelle, kyseinen alue on konveksi.

kumilenkkiperiaate

Kun konveksi peite on muodostettu, verkkoon toistaiseksi kuulumatto- mat sisäpisteet tulisi yhdistää s.e. venymä on mahdollisimman pieni.

MST ”Minimum Spanning Tree”, virittävä minimaalipuu eli puutietorakenne, joka kytkee kaikki verkon solmut yhteen s.e. jokaisesta solmusta lähtee vähintään yksi yhteys ja verkko on yhtenäinen ja kierrokseton kaarten pituuksien summan ollessa minimi.

NNH ”Nearest Neighbo(u)r Heuristic”, lähimmän naapurin heuristiikka, tutkielmassa tarkasteltava ensimmäinen algoritmi.

NP ”Non-deterministic polynomial” -luokka; sisältää ongelmat, joille voidaan tarkastaa tehokkaasti epädeterministisellä Turingin koneella, onko ratkaisu oikein.

NP-hard NP-vaikeiden tai NP-kovien ongelmien luokka; sisältää ongelmat, joille ei tunneta muita kuin eksponentiaalisen ajan vieviä ratkaisualgoritmeja.

Ongelma on NP-kova jos ja vain jos se on ainakin yhtä vaikea kuin mikä hyvänsä NP-ongelma.

NPC ”NP complete” eli ”NP-täydellinen”-luokka, toisin sanoen NP-luokan ongelmat, joille ei tunneta ainuttakaan polynomisen ajan vievää ratkaisua. Ongelma on NP-täydellinen jos ja vain jos se on yhtä aikaa luo- kissa NP ja NP-hard.

ortogonaalipiste

Piste, joka osuu suoralle 90 asteen kulmassa suoran ulkopuolelta määri- tellystä pisteestä.

P ”Polynomial”-luokka eli ongelmat, jotka voidaan ratkaista tehokkaasti polynomisessa ajassa deterministisellä Turingin koneella.

PC ”Personal Computer”, työkäyttöön tarkoitettu tietokone.

(7)

pisteen etäisyys suorasta

Pisteen (X0, Y0) etäisyys suorasta ax + by + c lasketaan kaavalla

|𝑎𝑋₀+𝑏𝑌₀+𝑐|

√𝑎²+𝑏² ^.

RAM ”Random Access Memory”, tietokoneen keskusmuisti eli työmuisti tai hajasaantimuisti.

ristitulo Kahden vektorin A ja B välinen ristitulo lasketaan kaavalla 𝐴 × 𝐵 = |

𝑖 𝑗 𝑘

𝐴₁ 𝐴₂ 𝐴₃ 𝐵₁ 𝐵₂ 𝐵₃

| = (𝐴₂𝐵₃− 𝐴₃𝐵₂)𝑖 + (𝐴₃𝐵₁− 𝐴₁𝐵₃)𝑗 + (𝐴₁𝐵₂− 𝐴₂𝐵₁)𝑘 .

TSP ”Traveling Salesman Problem” eli kauppamatkustajan ongelma yleisesti. Voidaan jakaa useihin alalajeihin, kuten symmetrinen ja asymmetrinen TSP.

tsplib Tiedostomuoto (tiedostopääte ”.tsp”) verkkojen tallentamista varten.

TSP Solver ”Traveling Salesman Problem Solver” eli tutkielman ohella laadittu Java-sovellus, jolla mittaukset on tehty tutkielmaa varten.

UML ”Unified Modeling Language”, jolla esitetään ohjelmiston mallintami- seen tarkoitettuja kaavioita.

VLSI ”Very-Large-Scale Integration” eli transistoreja sisältävän mikrosirun valmistustekniikka. Esimerkiksi mikroprosessori kuuluu VLSI-tekniik- kaan.

WiFi ”Wireless Fidelity”, langaton verkkoyhteys tietoliikennetekniikassa.

XML ”Extensible Markup Language”, eräs rakenteellisten dokumenttien kä- sittelykieli ja tiedostotyyppi.

(8)

vii

Sisällysluettelo

1 Johdanto ... 1

2 Ongelman kuvaus ... 3

2.1 Ongelman historiaa ja taustaa ... 3

2.2 Määrittelyt matemaattisesti ... 4

2.2.1 Matemaattiset verkot ... 6

2.2.2 Hamiltonin kierros ... 7

2.2.3 Erilaisia TSP-versioita ... 7

2.3 NP-täydellisyys ja kombinatorinen optimointi ... 8

3 Algoritmit ... 10

3.1 Pääalgoritmit ... 10

3.1.1 Lähin naapuri ... 10

3.1.2 Kaksois-MST Prim-algoritmia hyödyntäen ... 11

3.1.3 Heuristiikka konveksilla peitteellä ... 12

3.2 Sivualgoritmit ... 16

3.2.1 Virittävä minimaalipuu ... 16

3.2.2 Eulerin kierroksen etsintä ... 17

3.2.3 Konveksin peitteen laskeminen ... 19

3.3 Christofides-heuristiikka ... 21

4 Materiaalit ja menetelmät ... 22

4.1 Verkonkäsittelyohjelman kuvaus ... 22

4.1.1 Toiminnot ja UML-kaavioita ... 22

4.1.2 Tsplib ... 28

4.1.3 Valmiit esimerkit ... 28

4.2 Mittarit ... 29

4.2.1 Mittareiden kuvailu yleisesti ... 30

4.2.2 ResourceTracker (Pekka Kilpeläinen) ... 30

5 Tulokset ... 31

5.1 Tulosten luotettavuuden arviointi ... 31

5.2 Tilastot ... 31

5.3 Johtopäätökset ... 34

6 Pohdinta ... 35

7 Yhteenveto ... 37

Lähteet ... 39

Liitteet (1) ... 42

Liite 1: Excel-taulukko suorituksista (3 sivua) ………....42

(9)

1 Johdanto

Arjessa kohdataan useita pieniä ja suuria verkkoteorian alan matemaattisia ongelmia, vaikka asiaan ei välttämättä kiinnitetä erityistä huomiota. Liikenteessä kuljetaan monimutkaisia tieverkostoja pitkin, useissa kotitalouksissa on langaton WiFi-verkko ja älypuhelimessa saattaa näppäinlukkona olla yksinkertaisen viivakuvion piirtäminen kosketusnäytölle. Logistiikassa, tietoliikennetekniikassa ja tietoturvallisuuskysymyk- sissä on pohdittu ja pohditaan edelleen kombinatorisen optimoinnin kysymyksiä. Täl- laisilla kysymyksillä on oma merkityksensä myös Hamiltonin kierroksen etsinnässä (ks. termin täsmällinen selitys luku 2.2.2). Niin järjenvastaiselta kuin asia tuntuukin, minimipituisen Hamiltonin kierroksen löytämiselle ei tunneta ainuttakaan tehokasta, niin kutsuttua polynomiaikaista algoritmia eli laskentaohjetta. Mikäli siis verkon suhteen tavoitteena on sellaisen parhaan mahdollisen kierroksen löytäminen, joka vierai- lee jokaisessa pisteessä kerran, on vastausta odotettava syötteestä riippuen jopa enem- män kuin maailmankaikkeudella oletetaan olevan ikää. Johdantoluvun jälkeisessä toisessa luvussa keskitytään tarkemmin kauppamatkustajan ongelman (TSP) kuvailuun historiallisessa, matemaattisessa ja Turingin konetta koskevassa mielessä.

Koska BFS-menetelmällä (Brute Force Search) eli jokaista mahdollista tulosta tarkas- telemalla aika ei riitä optimaalisen TSP-ratkaisun odotteluun nykyiselläkään teknolo- gialla jo muutenkin kiireisessä yhteiskunnassa, asiantuntijat ovat suunnitelleet ja to- teuttaneet heuristiikkoja ja approksimointialgoritmeja suhteellisen hyvän ratkaisun ta- voittamiseksi kohtuullisessa ajassa. Kaksi erittäin tunnettua menetelmää, lähimmän naapurin algoritmi ja kaksois-virittävän minimaalipuun algoritmi (Reinelt, 1994, sivut 73-75 & 89-91), esitellään tutkielman luvuissa 3.1.1 ja 3.1.2. Luku 3.1.3 esittelee konveksin peitteen heuristiikan, jossa kokeillaan omaa lähestymistapaa TSP-reitin laske- miseksi Grahamin skannausalgoritmia hyödyntäen. Luku 3.2 selventää kyseisen skan- nauksen sekä kaksi muuta oleellista apualgoritmia: virittävän minimaalipuun ja Eule- rin kierroksen muodostukset. Christofides-heuristiikka (Reinelt, 1994, sivu 92) on jä- tetty pois tutkielman aihepiiristä. Kyseinen menetelmä rajattiin pois lähinnä sen toteutushaastavuuden vuoksi ja koska se ei palvele algoritmiasettelua ”naiivi algoritmi, si- sältä ulos -algoritmi ja ulkoa sisään -algoritmi”. Christofides-heuristiikasta kerrotaan

(10)

Luvussa 4 perehdytään kokeellisen tutkimuksen materiaaleihin ja menetelmiin, joiden avulla kaikkien kolmen heuristisen algoritmin ajojen pohjalta on muodostettu tilastoja ja johtopäätöksiä asianmukaisilla mittareilla. Tsplib-tiedostoja lukeva verkonkäsitte- lyohjelma TSP Solver ja mittareista erityisesti ResourceTracker ovat tarkastelun koh- teena. Näistä molemmat on toteutettu Java-kielellä, joten lukijallakin on mahdollisuu- det toistaa ajoja itse niin halutessaan riippumatta PC:n käyttöjärjestelmästä. Lähde- kooditiedostoja on viisi ja ne ovat julkisia GitHub-palvelussa.

Viidennessä luvussa arvioidaan tulosten luotettavuutta, esitetään tilastoja algoritmien suorituksista erikokoisilla syötteillä ja muodostetaan johtopäätökset niin matemaattisten faktojen kuin teknisten suoritusten pohjalta. Pohdinnassa puolestaan arvioidaan, mitä olisi mahdollisesti voitu parantaa ja millaisia jatkotoimenpiteitä tutkielman työlle on mahdollista tehdä. Mahdollisuuksia on paljon ja asian on tarkoitus innoittaa luki- jaakin kokeilemaan uusia ideoita. Lisäksi pohdintaosiossa vastataan tutkimuskysy- mykseen, joka on ”kuinka kolme valittua algoritmia poikkeavat toisistaan tarkkuuden ja ajallisen tehokkuuden suhteen?” Algoritmit on pyritty valitsemaan siten, että ne edustavat kolmea eri lähestymistapaa (valitse aina lähin / etene sisältä ulospäin / etene ulkoa sisäänpäin) ja ovat riittävän yksinkertaisia ymmärtää. Lisäksi tutkielma toimii eräänlaisena johdannollisena suomenkielisenä oppaana henkilölle, joka tahtoo sisäis- tää kauppamatkustajan ongelman perusteet ja kokeilla rohkeasti erilaisia lähestymis- tapoja ongelman ratkaisemiseksi.

(11)

2 Ongelman kuvaus

Kuvitellaan, että jo peruskouluajoilta tutussa niin kutsutussa 2-ulotteisessa karteesi- sessa koordinaatistossa on mielivaltainen äärellinen määrä pisteitä. Geometrinen 2- ulotteinen TSP on yleisen TSP-ongelman erikoistapaus, jossa pisteet on sijoitettu ky- seisenlaiseen koordinaatistoon ja kaikista pisteistä on olemassa yhteys kaikkiin muihin pisteisiin. Sanotaan siis, että verkko on täydellinen. Kun tarkoituksena on etsiä mahdollisimman lyhyt reitti, joka aloittaa mielivaltaisesta pisteestä ja kulkee jokaisen pisteen kautta täsmälleen kerran palaten lopuksi takaisin lähtöpisteeseen, puhutaan kauppamatkustajan ongelmasta. Kauppamatkustaja suunnittelee itselleen reitin, joka käy kerran jokaisen asiakkaan luona, ja lopuksi palataan takaisin pääkonttorille, josta läh- dettiinkin. Toisin sanoen etsitään niin kutsuttua minimipituista Hamiltonin kierrosta.

Tässä luvussa selvennetään Hamiltonin kierroksen käsite, matemaattisten verkkojen tyyppejä ja kauppamatkustajan ongelman historiaa lyhyesti sekä sen erilaisia versioita.

Lopuksi luvussa 2.3 selitetään, miksi ongelmasta ollaan kiinnostuneita tietojenkäsitte- lytieteessä laskennallisten ongelmien luokittelun kannalta.

Tässä tutkielmassa kauppamatkustajan ongelmaan viitataan yleisesti lyhenteellä TSP, jotta turhilta pitkien sanojen toistamisilta vältyttäisiin.

2.1 Ongelman historiaa ja taustaa

TSP-ongelman perusidea tunnettiin jo ennen automaattisen tietojenkäsittelytieteen syntyä. Irlantilainen matemaatikko William Hamilton ja britannialainen matemaatikko Thomas Kirkman aloittivat 1800-luvulla graafiteorian alan ongelmien tutkinnat, jotka liittyivät läheisesti TSP-ongelmaan (Shekhar & Xiong, 2008, sivu 1174). Tuomisto (2007, sivut 8-10) on myös käsitellyt termin syntymistä ja ongelman tutkimusta lyhyesti ja ytimekkäästi. TSP-ongelman syntyhistoria on melko epäselvä ja tarkkaa vuosi- lukua tai ongelman ensimmäisiä määrittelijöitäkään ei tunneta. Tuomisto viittaa Hoff- maniin ja Wolfiin, joiden mukaan matemaatikot saattoivat käyttää termiä ensimmäisen kerran vuonna 1931 tai 1932, joskin on syytä huomata viite vuonna 1832 ilmestynee- seen nimeltä mainitsemattomaan saksankieliseen kirjaan. Hassler Whitney puolestaan

(12)

kauppamatkustajan reitin 49 eri yhdysvaltalaisen kaupungin välille ilman nykyaikaisia tietokoneita, mitä pidettiin merkittävänä saavutuksena. Applegate & al. (2007, sivu 51) ovat listanneet merkittäviä edistysaskeleita TSP-ongelman ratkonnassa aina vuo- teen 1987, jolloin voitiin ratkoa optimaalinen vastaus jo 2392 pisteen verkolle. Water- loon yliopisto pitää kirjaa 100000 solmun Mona Lisa -verkon TSP-reitin ennätyksestä ja 17.3.2009 Yuichi Nagata löysi geneettisellä algoritmilla 5757191 pituusyksikön mittaisen reitin, jonka optimaalisuudesta ei toistaiseksi ole varmaa tietoa (University of Waterloo, 2017b).

TSP-ongelmaa voidaan soveltaa mm. robotiikassa (Skiena, 2008, sivu 533 tai Reinelt, 1994, sivu 35). Kun tietokoneen piirilevyihin tehdään juotoksia robottikädellä, etsitään käytännössä minimipituista Hamiltonin kierrosta juotoskohtien joukosta. Mahdollista on myös ratkoa ongelma erilaisissa avaruuksissa, kuten esimerkiksi pallon pinnalla, jollainen tapaus nousee esille suunniteltaessa lentokonereittejä. Kolmantena erinomai- sena soveltamisesimerkkinä mainittakoon (röntgen)kristallografia (Reinelt, 1994, sivu 36). Siinä tarkoitus on tutkia esimerkiksi molekyylien avaruudellista rakennetta kol- miulotteisesti, miksei vaikkapa DNA:n eli deoksiribonukleiinihapon kaksoiskierrettä.

2.2 Määrittelyt matemaattisesti

Määritellään matemaattinen verkko ja Hamiltonin kierros sekä esitellään muutamia tunnettuja TSP-variaatioita. Yleistietona esiteltäköön kuitenkin ensimmäiseksi euklidinen etäisyys ja kolmioepäyhtälö sekä muita hyödyllisiä kaavoja, joilla tulee olemaan merkittävä rooli etenkin kolmannessa algoritmissa, jota tämä tutkielma käsittelee luvussa 3.1.3.

Euklidinen etäisyys (Reinelt, 1994, sivu 42; Spiegel & al., 2009, sivu 22) on kahden pisteen (𝑥₁, 𝑦₁) ja (𝑥₂, 𝑦₂) välinen etäisyys, joka lasketaan kaavalla (1).

Kaava (1): Euklidinen etäisyys √(𝑥₂− 𝑥₁)²+ (𝑦₂− 𝑦₁)²

Tällä on oleellinen merkitys TSP-reitin pituuden laskennassa ohjelmoitaessa kahta eri Java-metodia, joista ensimmäinen antaa täsmällisen tuloksen ja toinen jättää neliöjuu- ren pois, mikä on pituusvertailujen kannalta hyödyksi.

(13)

Kolmioepäyhtälöllä (kaava (2); Spiegel & al., 2009, sivu 205) tarkoitetaan, että kolmion sivu on aina korkeintaan yhtä pitkä kuin kahden muun sivujen a ja b pituuksien summa ja vähintään sen pituinen kuin kahden muun sivujen a ja b pituuksien erotuksen itseisarvo. Muuttujat a ja b ovat reaalilukuja. Luku 3.1.3 esittää, kuinka epäyhtälöllä perustellaan TSP-reitin risteyksettömyyttä.

Kaava (2): Kolmioepäyhtälö | |a| – |b| | ≤ |a + b| ≤ |a| + |b|

Määriteltäessä suoran ax + by + c = 0 yleistä muotoa vain kahden pisteen (𝑥₁, 𝑦₁) ja (𝑥₂, 𝑦₂) avulla voidaan todeta, että a = y1 – y2 , b = x2 – x1 ja c = (x1 – x2)y1 + (y2 – y1)x1 (Stackoverflow.com, 2012).

Spiegel & al. (2009) on esittänyt myös vektorien välisen ristitulon ja kaavan, jolla voidaan laskea pisteen etäisyys suorasta s.e. piste on (𝑋₀, 𝑌₀).

Kaava (3): Pisteen etäisyys suorasta ^|𝑎𝑋⁰^+𝑏𝑌⁰^+𝑐|

√𝑎²+𝑏²

Kahden vektorin välisestä ristitulosta on johdettavissa seuraava kaava (4), jolla lasketaan 2-kertainen kolmion pinta-ala (Spiegel & al., 2009, sivu 23).

Kaava (4): Kaksinkertainen kolmion pinta-ala ja sen johtaminen

|

𝑎_𝑥 𝑎_𝑦 1 𝑏_𝑥 𝑏_𝑦 1 𝑐_𝑥 𝑐_𝑦 1

| = 𝑏_𝑦𝑎_𝑥− 𝑐_𝑦𝑎_𝑥− 𝑏_𝑥𝑎_𝑦+ 𝑐_𝑥𝑎_𝑦+ 𝑏_𝑥𝑐_𝑦− 𝑐_𝑥𝑏_𝑦

= (𝑏𝑥− 𝑎𝑥)(𝑐_𝑦− 𝑎𝑦) − (𝑏𝑦− 𝑎𝑦)(𝑐𝑥− 𝑎𝑥)

Kolmannen heuristiikan ohjelmoinnissa voidaan myös huomata, että on hyödyllistä tarkastella, mihin kohtaan suoralle osuisi uusi piste 90 asteen kulmassa.

(14)

Kuva 1: Suora on muodostettu pisteiden (x1, y1) ja (x2, y2) kautta ja pisteestä (x3, y3) suoralle määritellään 90 asteen kulmassa ortogonaalipiste (x4, y4), joka ei välttämättä ole kahden ensimmäisen pisteen välissä.

Suora määritellään sen päällä sijaitsevien pisteiden (x1, y1) ja (x2, y2) avulla. Pisteestä (x3, y3) lähtee kohtisuora piste tälle suoralle ja se on (x4, y4). Tämä suoralla oleva kohtisuora piste voidaan laskea seuraavasti (Stackoverflow.com, 2009): määritellään apu- muuttuja k s.e.

k = ((y2-y1)(x3-x1) - (x2-x1)(y3-y1)) / ((y2-y1)² + (x2-x1)²) tällöin x4 = x3 - k(y2-y1) ja

y4 = y3 + k(x2-x1).

Edellä esitellyn 2-kertaisen kolmion pinta-alan kaavalla (4) sekä joko-tai-operaation (xor) avulla voidaan lisäksi tarkastella, onko 4. piste 1. ja 2. pisteen välissä. Mikäli yhteydet 341 ja 342 ovat molemmat vastapäivään tai molemmat myötäpäi- vään ja päällekkäisiä pisteitä ei ole, tällöin 4. piste ei sijaitse 1. ja 2. pisteen välissä suoralla.

2.2.1 Matemaattiset verkot

Verkko (graph) G eli graafi on solmujen (vertex) V eli pisteiden ja kaarten (edge) E eli viivojen muodostama pari G = {V, E}. Verkko voi olla suunnattu tai suuntaamaton riippuen siitä, esiintyykö siinä niin sanotusti ”yksisuuntaisia katuja” eli kaaria, joissa on kulkuyhteys vain toiseen solmuun. Verkko voi olla myös symmetrinen tai asymmetrinen riippuen siitä, onko kaikkien kaarten paino eli pituus sama kumpaankin suun- taan kullakin yhdistetyllä solmuparilla.

(15)

Tässä tutkielmassa keskitytään erityisesti geometrisiin eli euklidisiin verkkoihin. Täl- laiset verkot ovat aina suuntaamattomia ja symmetrisiä. Ne on aina mahdollista kuvata karteesisessa koordinaatistossa siten, että kullakin solmulla on oma vaaka- ja pysty- koordinaatti. Geometriset verkot ovat automaattisesti täydellisiä verkkoja eli kaikista solmuista on olemassa yhteys kaikkiin muihin solmuihin. Verkoista on mahdollista tehdä erilaisia isomorfisia esityksiä siirtelemällä solmuja s.e. kytkennät eivät muutu.

Kaava (5): Hamiltonin kierrosten lukumäärä geometrisessa verkossa ^{(𝑛−1 ) !}

2 Suuntaamattomissa graafeissa, kuten myös geometrisissa graafeissa, kaikkien mahdollisten Hamiltonin kierrosten lukumäärä on kaavan (5) tulos, missä muuttuja n on luon- nollinen luku ja verkon solmujen lukumäärä (Gutin & Punnen (Ed.), 2007, sivu 2).

Siispä esimerkiksi 5 solmun graafissa on kaikkiaan 12 ja 10 solmun graafissa on kaikkiaan 181440 erilaista Hamiltonin kierrosta.

2.2.2 Hamiltonin kierros

TSP-ongelmassa on kyse minimipainoisen Hamiltonin kierroksen etsimisestä. Tällai- sella kierroksella tarkoitetaan reittiä, joka sisältää jokaisen solmun täsmälleen kerran.

Termi on saanut nimensä kuuluisan matemaatikon, William Rowan Hamiltonin, mukaan. Hamiltonin kierroksen olemassaolon selvittäminen graafissa ylipäätään on han- kalaa ja se kuuluu samaan, niin kutsuttuun NP-täydelliseen luokkaan TSP-ongelman kanssa (Skiena, 2008, sivu 538).

Eulerin kierros (nimetty Leonhard Euler:n mukaan) eroaa Hamiltonin kierroksesta s.e.

Eulerin kierroksessa on verkon jokainen kaari tasan kerran, kun Hamiltonin kierroksessa jokainen solmu esiintyi tasan kerran. Eulerin kierrosta tullaan kuitenkin myö- hemmin hyödyntämään minimipainoisen Hamiltonin kierroksen etsinnässä toisessa algoritmissa, joka esitellään luvussa 3.1.2.

2.2.3 Erilaisia TSP-versioita

TSP-ongelmasta on olemassa useita muitakin variaatioita kuin geometrinen TSP. Seu- raavassa luetellaan niistä muutamia.

(16)

Tarkasteltaessa kirjallisuutta yleisesti TSP eritellään usein karkeasti joko symmetri- seen tai asymmetriseen versioon riippuen siitä, onko käsiteltävä graafi suunnattu vai suuntaamaton. Suunnatun graafin TSP on asymmetrinen eli ATSP (Asymmetric Tra- veling Salesman Problem), kun taas suuntaamattoman graafin TSP on symmetrinen eli STSP (Symmetric Traveling Salesman Problem). Geometrinen TSP voidaan ajatella ikään kuin STSP-ongelman alalajina.

Traveling Salesman Walk (Lam & Newman, 2008, sivu 39) on astetta anteeksianta- vampi TSP-variaatio, sillä siinä on lupa käydä samassa solmussa useammin kuin kerran. Toinen esimerkki astetta helpommasta variaatiosta on geometrinen maksimi-TSP, jossa etsitään poikkeuksellisesti mahdollisimman pitkää Hamiltonin kierrosta. Bar- vinok & al. (2003, sivu 1) osoittivat, että mille tahansa monitahokkaalle normille (”po- lyhedral norm”) on mahdollista löytää maksimipituinen TSP-reitti polynomisessa ajassa.

Useamman kauppamatkustajan ongelmassa (The Multisalesman Problem, ks. Reinelt, 1994, sivu 33) erikoisuutena on, että kauppamatkustajia on enemmän kuin yksi, johon yleisesti on totuttu. Hoff & Løkketangen (2006) puolestaan käsittelevät variaatiota ni- meltä TSPPD (Traveling Salesman Problem with Pickup and Delivery), jossa solmuille on määritelty prioriteetit. Toisin sanoen joissain solmuissa on käytävä ennen kuin on lupa päästä toisiin solmuihin. Kun yhdistellään multi-TSP:n ja TSPPD:n kal- taisia ongelmia toisiinsa, voidaan saada aikaan hyvin monimutkaisia ja haastavia pul- mia, joita voidaan kuitenkin selvästi havaita reaalimaailmassa.

2.3 NP-täydellisyys ja kombinatorinen optimointi

Kombinatorisessa optimoinnissa pyritään löytämään parasta mahdollista eli optimaalista ratkaisua kaikkien mahdollisten kombinaatioiden joukosta. TSP on klassinen esimerkki tästä. Kuten aiemmin on todettu, n-solmuisessa verkossa on kaavan (5) osoit- taman lukumäärän verran erilaisia Hamiltonin kierroksia ja näistä pyritään löytämään lyhin mahdollinen reitti (tai lyhimmät mahdolliset reitit, mikäli on olemassa useita op- timaalisia ratkaisuja). Kombinatorisessa optimoinnissa voidaan tunnistaa erilaisia luo- kituksia erilaisille ongelmille. Seuraavassa näistä oleellisimmat (Papadimitriou &

Steiglitz, 1982, sivu 353):

(17)

 Luokan P (Polynomial) ongelmat ovat laskennallisia ongelmia, jotka voidaan ratkaista polynomisessa ajassa deterministisellä Turingin koneella.

 Luokan NP (Non-deterministic Polynomial) ongelmat ovat laskennallisia ongelmia, jotka voidaan ratkaista polynomisessa ajassa myös epädeterministi- sellä Turingin koneella.

 NP-vaikeat tai NP-kovat (NP-hard) ongelmat ovat ongelmia, ”joihin voidaan polynomiajassa redusoida kaikki NP-ongelmat, mutta NP-kovien ongelmien ei tarvitse itse kuulua NP:hen” (Järvenpää & Talvitie, 2014, sivu 5). Laskennal- linen ongelma on NP-kova jos ja vain jos se on ainakin yhtä vaikea kuin mikä hyvänsä NP-ongelma.

 Laskennallinen ongelma on NP-täydellinen (NP-complete) jos ja vain jos se on NP-vaikea ja kuuluu luokkaan NP. TSP kuuluu tähän luokkaan, kuten myös sen geometrinen eli euklidinen versio.

Kuva 2: Eulerin diagrammi tapauksille, joissa luokat P ja NP ovat identtiset ja epäidenttiset.

https://en.wikipedia.org/wiki/P_versus_NP_problem#/media/File:P_np_np-complete_np-hard.svg (muokattu, vierailtu 5.6.2017)

Vuonna 2000 Clay Mathematics Institute sisällytti P vs NP -ongelman yhdeksi seitse- mästä Millennium-ongelmasta, josta kustakin on luvattu miljoonan dollarin palkkio.

Stephen Cook on selostanut ongelman virallisesti 12-sivuisessa artikkelissaan The P vs NP Problem. Peruskysymys kuuluu ”jos ongelman ratkaisun voi tarkistaa tehokkaasti eli polynomisessa ajassa, voiko ongelman myös ratkaista tehokkaasti eli polynomi-

(18)

3 Algoritmit

Esitellään kolme algoritmia, joita sovelletaan TSP-reitin laskentaan geometrisessa verkossa. Lisäksi esitellään algoritmien käyttämät apualgoritmit. Kaikkia kolmea pääal- goritmia tullaan vertailemaan ohjelmalla, joka kuvaillaan tarkemmin luvussa 4.1. Ver- tailuissa käytetään mittareita, jotka kuvaillaan tarkemmin luvussa 4.2, ja tulokset esi- tetään viidennessä luvussa.

3.1 Pääalgoritmit

Esitellään lähin naapuri -heuristiikka (NNH), kaksois-virittävän minimaalipuun algoritmi (2-MST) sekä konveksin peitteen heuristiikka (CHH). NNH valitsee aina lähim- män solmun, 2-MST muodostaa virittävän minimaalipuun tuplatuilla kaarilla oikoen lopulta ylimääräiset reitit pois ja CHH hyödyntää niin kutsuttua kumilenkkiperiaatetta yhdistellen sisäpisteet yksitellen mukaan reittiin konveksin peitteen muodostuksen jäl- keen.

3.1.1 Lähin naapuri

Lähimmän naapurin algoritmi eli Nearest Neighbor Heuristic (NNH) on niin kutsuttu ahne heuristiikka, joka valitsee jokaisella kierroksella parhaan mahdollisen vaihtoeh- don, tässä tapauksessa solmun, joka on kaikkein lähimpänä viimeksi yhdistettyä solmua. Mahdollista on myös toteuttaa algoritmi siten, että tarkastellaan jokaisella yhdis- tämiskierroksella sekä nykyistä alkusolmua että nykyistä päätesolmua, ja näistä kahdesta lasketaan minimietäisyyttä seuraavaksi lähimpään solmuun (Reinelt, 1994, sivu 74). Tämän tutkielman toteutuksessa ei kuitenkaan keskitytä kahteen päähän, vaan algoritmi on toteutettu perinteisenä ”yhden pään” toteutuksena ilman aputietorakenteita.

Syynä tähän ratkaisuun on yksinkertaisuuden tavoittelu.

NNH on ensimmäisiä ratkaisumenetelmiä TSP-ongelman historiassa, eikä se aina takaa parhainta mahdollista kokonaistulosta. On itse asiassa todennäköistä, että laajassa verkossa algoritmilla löydetään kehno tulos, joka sisältää risteyksiä. Geometrisissa graafeissa optimaalinen tulos ei voi koskaan sisältää risteyksiä johtuen kolmioepäyh- tälöstä, tähän palataan luvussa 3.1.3.

(19)

Syöte: geometrinen verkko.

Tuloste: verkon solmut sopivasti järjestettynä esim. taulukossa.

(1) Valitaan satunnainen solmu j ja osoitin l asetetaan osoittamaan sen sijaintikohtaan. Lisäksi j poistetaan yhdistämättömien solmujen T joukosta.

(2) Niin kauan kuin T sisältää solmuja, toistetaan:

(2.1) Olkoon uusi j, joka kuuluu joukkoon T, muuttujaa l lähinnä oleva yhdistämätön solmu (2.2) Yhdistetään l ja j toisiinsa ja poistetaan j joukosta T, lopuksi asetetaan l osoittamaan muuttujan j sijaintikohtaan.

(3) Yhdistetään l siihen solmuun, joka ensimmäisenä poistettiin joukosta T kohdassa (1).

Yllä heuristiikka on esitetty pseudokoodilla niin kuin Reinelt (1994, sivu 74) on sen kuvaillut. Koodia on vapaasti suomennettu s.e. turhat yksityiskohdat on jätetty pois.

Algoritmin aikavaativuus on neliöllinen eli syötteen kasvaessa aika-askeleet ovat 2- potenssista luokkaa (Ω(n²) ks. Reinelt, 1994, sivu 74).

Nilsson (2003, sivu 1) on esittänyt, että heuristiikan tarkkuus on usein korkeintaan 25% huonompi kuin niin kutsuttu Held & Karp alaraja. Held & Karp (1970) käyttävät lähestymistapana 1-puuta, joka on yhden kierroksen jo sisältävä MST (ks. luku 3.2.1), selvittääkseen rajaa optimaalisen TSP-reitin pituudelle. Ideana on, että verkkoa muo- kataan useaan kertaan ja kullekin muokatulle verkolle lasketaan minimipainoinen 1- puu. Minimipainoiset 1-puut ovat aina alarajoja optimiratkaisulle ja kun näistä alara- joista otetaan maksimiarvo, päästään yhä lähemmäs optimiratkaisun alarajan selvittä- mistä.

3.1.2 Kaksois-MST Prim-algoritmia hyödyntäen

Kaksois-MST eli Double Minimum Spanning Tree (2-MST) on niin kutsuttu 1,0-approksimointialgoritmi (todistus: Papadimitriou & Steiglitz, 1982, sivu 414), joka ni- mestäänkin päätellen hyödyntää virittävää minimaalipuuta TSP-reitin laskennassa.

(20)

pituuden ollessa positiivinen reaaliluku x on 2-MST-heuristiikan antama tulos pahimmillaan 2x. Menetelmästä on olemassa kehittyneempi versio, jota kutsutaan Christofi- des-algoritmiksi. Tämä puolestaan on 0,5-approksimointialgoritmi, jonka antama tulos on pahimmillaan 1,5-kertainen (Papadimitriou & Steiglitz, 1982, sivut 416-417).

Tutkielman 2-MST-toteutuksessa on vaiheessa (1) hyödynnetty niin kutsuttua Primin algoritmia, mutta muutkin lähestymistavat ovat mahdollisia, kuten esimerkiksi Krus- kalin algoritmi.

(1) Etsitään virittävä minimaalipuu T

(2) Luodaan multigraafi G eli verkko, jossa kahden solmun välillä voi olla useita samoja kaaria, kopioi- malla jokainen T:n kaari kerran

(3) Etsitään Eulerin kierros graafista G, jossa kaarten lukumäärä on kaksinkertaistunut, ja muodostetaan oikoreitit s.e. samassa solmussa ei vierailla kahdesti.

Ohessa on esitetty Papadimitriou & Steiglitz (1982, sivu 414) -teoksessa kuvattu heuristiikka vapaasti suomennettuna. Heuristiikan aikavaativuusluokka vaihtelee, sillä se riippuu erityisesti MST:n ja Eulerin kierroksen etsinnän tehokkuuksista. Nilsson (2003, sivu 2) määrittelee aikavaativuudeksi O (n²log 2 (n)) osana Christofides-heuris- tiikkaa, eikä kirjallisuudessa tavallisesti tarjota tätä suurempaa ylärajaa.

3.1.3 Heuristiikka konveksilla peitteellä

Konveksin peitteen heuristiikka (CHH, Convex Hull Heuristic) on menetelmä, jolla etsitään parhaimmissa toteutuksissa risteyksetön Hamiltonin kierros. Sen oleellinen apurakenne on konveksi peite, joka kuvaillaan luvussa 3.2.3. ja on mahdollista toteuttaa Graham-algoritmilla.

Syötteet: geometrinen verkko, pino konveksin peitteen muodostamista varten.

(21)

(1) Muodostetaan konveksi peite ja merkitään sitä koskettavat solmut kehäpisteiksi, muut solmut ovat sisäpisteitä

(2) Niin kauan kuin sisäpisteitä on olemassa, toistetaan seuraavat vaiheet:

(2.1) Etsitään peitettä lähinnä oleva solmu ja lasketaan sen etäisyydet kaikkiin

kehäpisteisiin

(2.2) Lasketaan kolmioiden painot kaavalla c+b-a, missä a on mahdollisesti poistuva sivu ja c ja b ovat sisäpistettä koskettavia sivuja.

(2.3) Lohkaistaan kevein kolmio pois s.e. a poistuu, c ja b lisätään reitin pituuteen (2.4) Merkitään yhdistetty sisäpiste

kehäpisteeksi

Pseudokoodia on yksinkertaistettu ja luvussa 4.1.1 esitellään algoritmin toimintaa tarkemmin. Koska CHH valitsee jokaisella kierroksella parhaan mahdollisen vaihtoeh- don, sen voi luokitella ahneeksi heuristiikaksi. Kuvassa 3 on esitetty tarkemmin, mihin kohdan 2.2 kaavan c+b–a muuttujat viittaavat.

Kuva 3: Hetkellisesti edullisin valinta tehdään valitsemalla se kolmio, jolle c+b–a = min.

(22)

Kuva 4: Kolmioepäyhtälöllä (kaava (2)) voidaan perustella optimaalisen reitin risteyksettömyys (Van Rooij & al., 2003, sivut 217-218). Kirjain d tarkoittaa etäisyyttä (distance).

Nilsson (2003, sivu 2) luokittelee algoritmin lisäysheuristiikaksi, jonka aikavaativuus on O (n²log 2 (n)). Tutkielman toteutuksella voidaan silmämääräisesti perustella kuutiollinen aikavaativuus O(n³), sillä tiedostossa ”TSP_Solver_UEF_241908.java” (Hy- vönen, 2017) on seuraavat silmukat CHH:n suhteen:

for(nykyisten sisäpisteiden lukumäärä){ // joka kierroksella 1 sisäpiste mukaan reittiin for(verkon solmujen lukumäärä){

for(verkon solmujen lukumäärä){

etsi vertailtava sisä-kehä-minimietäisyys }

}

for(nykyisten kehäpisteiden lukumäärä){ // kahdesti päivitä indeksejä

}

for(nykyisten sisäpisteiden lukumäärä){

for(nykyisten kehäpisteiden lukumäärä){

etsi tarkemmin sisäpistettä 90° kulmissa }

}

for(verkon solmujen lukumäärä){

kehäpistemerkintä kuntoon }

for(nykyisten kehäpisteiden lukumäärä){

kolmiolaskelmat c + b – a }

(23)

// lopuksi silmukat, joilla solmu lisätään reittiin for(korkeintaan verkon solmujen lukumäärä){

for(korkeintaan verkon solmujen lukumäärä){ // kahdesti lisäystoimenpide

} }

for(korkeintaan verkon solmujen lukumäärä){

lisäystoimenpide }

}

Koska sisäkkäisiä silmukoita on aina korkeintaan kolme ja kaikkia suoritetaan korkeintaan sen verran kuin verkossa on solmuja, eikä silmukkamuuttujissa tapahdu kompleksisuuteen vaikuttavia muutoksia, on perusteltua väittää aikavaativuuden ylä- rajan olevan korkeintaan kuutiollinen sillä edellytyksellä, että alussa myös konveksin peitteen muodostus on korkeintaan kuutiollinen.

Kaava (6): Kolmiotarkastelujen lukumäärä, missä k < n

∑ 𝑖

𝑛−1

𝑖=𝑘

Kuva 5: Viisi erilaista tapausta 8 solmun verkosta, niiden konveksit peitteet sekä kolmiotarkastelujen yhteismäärä. Esimerkiksi 25 = 3+4+5+6+7.

Kaavassa (6) ja kuvassa 5 on havainnollistettu, kuinka solmujen sijainnit vaikuttavat

(24)

tässä tapauksessa 8-solmuisessa verkossa. Kaavassa k on kehäpisteiden lukumäärä ja n on kaikkien pisteiden yhteismäärä. Molemmat muuttujat kuuluvat luonnollisiin lu- kuihin, kuten myös i. Kehäpisteiden ja sisäpisteiden lukumäärät ovat oleellisia muttei- vät ainoita tekijöitä, jotka vaikuttavat algoritmin ajalliseen tehokkuuteen.

3.2 Sivualgoritmit

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(n²) 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(n²). Todellisuudessa kompleksisuus riippuu siitä, kuinka MST ja Eulerin kierroksen etsintä toteutetaan ja mitkä ovat niiden kompleksisuudet.

Tuloste: puu (Tprim).

(1) Valitaan satunnainen solmu, josta puuta Tprim aletaan muodostaa

(2) Toistetaan seuraavia kahta toimintoa niin kauan

(25)

kuin verkossa on olemassa puuhun kuulumattomia solmuja:

(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 puuhun 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

(26)

(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 solmua, 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ä tapauksessa voidaan olettaa aikavaativuuden olevan neliöllinen.

(27)

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 voidaan törmätä, mikäli kohdataan yhtä edullisia venymiä samalla kierroksella ja pitäisi tarkastella kaikkien vaihtoehtojen etenemiset. Tällöin joudutaan yksinkertaisesti valitsemaan esimerkiksi ensimmäisenä vastaan tuleva vaihtoehto.

Syöte: geometrinen verkko (ja pino).

(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.

(28)

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

(29)

Useimmissa toteutuksissa, kuten TSP Solver -ohjelmassa, ainoastaan konveksin peitteen kulmat kuuluvat tulokseen ja mikäli solmuja esiintyy samassa suorassa kulmasol- mujen välillä, ne jätetään huomiotta.

3.3 Christofides-heuristiikka

Papadimitriou ja Steiglitz (1982, sivu 416) ovat kuvailleet Christofideen heuristiikan, joka ei sisälly tutkielmassa tarkasteltaviin algoritmeihin. Heuristiikka jätettiin pois lä- hinnä sen toteutushaastavuuden vuoksi ja koska tarkoitus oli valita algoritmit siten, että ensimmäinen on naiivi lähestymistapa, toinen etenee sisältä ulospäin ja kolmas ulkoa sisäänpäin. Haastavuutta lisäsi erityisesti paritusvaihe (seuraavan pseudokoodin kohdassa (2)). Christofideen heuristiikka on kuitenkin tutkielman käsittelyssä havain- nollistamassa, kuinka 2-MST-algoritmia voidaan parantaa.

(1) Etsitään verkosta virittävä minimaalipuu T, jolle on olemassa etäisyysmatriisi.

(2) Etsitään joukosta T ne solmut, joilla on pariton asteluku. Etsitään myös paritus M, jossa ainoastaan nämä solmut ovat mukana. Olkoon G multigraafi, jossa on alku- peräinen puu T ja paritetut yhteydet M.

(3) Etsitään Eulerin kierros multigraafista G ja muodostetaan oikoreitit s.e. samassa solmussa ei vierailla kahdesti.

Heuristiikka on tunnettu siitä, että se antaa korkeintaan 50% optimista poikkeavan ratkaisun. Jos optimiratkaisu on esimerkiksi 5 pituusyksikköä, niin huonoin mahdollinen tapaus on 7,5 pituusyksikköä. Hyvin toteutettuna heuristiikan aikavaativuus on kuutiollinen O(n³) (Nilsson, 2003, sivu 2).

(30)

4 Materiaalit ja menetelmät

Esitellään TSP Solver -ohjelma sekä siihen liittyviä mallinnuksia ja dokumentaatioita.

Lisäksi perehdytään tsplib-tiedostoformaattiin, esimerkkiverkkoihin ja mittareihin, joista oleellinen on FT Pekka Kilpeläisen (2018) ResourceTracker.

4.1 Verkonkäsittelyohjelman kuvaus

TSP Solver -ohjelma on tarkoitettu euklidisten, 2-ulotteisten verkkojen käsittelemi- seen tsplib-muodossa ja sisältää toteutukset kolmesta algoritmista. Sovellusta käyte- tään PC:llä ja Javan asentaminen on välttämätöntä sovelluksen käyttämiseksi. Ohjel- mointityön tulos on näkyvillä Github-palvelussa (Hyvönen, 2017).

4.1.1 Toiminnot ja UML-kaavioita

Sovellukseen on rakennettu seuraavat toiminnot: ”New”, ”Open”, ”Save”, ”Exit”,

”Nearest Neighbor Algorithm”, ”2-MST Algorithm with Prim”, ”Convex Hull Algo- rithm” ja “About”, joista viimeisin näyttää tietoja sovelluksesta (F1-näppäin). Käyttäjä voi vapaasti muokata avointa tiedostoa Editor-kentässä ja sen alapuolella olevassa val- koisessa tekstikentässä esitetään algoritmien ajojen tulokset. Jos tarkasteltavalla rivillä on luku, Enterin painaminen luo seuraavalle riville automaattisesti uuden solmun ID- numeron ja siirtää kursorin loppuun (rivin ”EOF” poistaminen ei vaikuta ohjelman toimintaan). Uusi viisisolmuinen tiedosto luodaan näppäinkomennolla ctrl+n, tiedoston avausikkuna komennolla ctrl+o ja tiedoston tallennusikkuna komennolla ctrl+s.

Oletusverkko on viisisolmuinen s.e. kolmella heuristiikalla on mahdollista saada kolme eri pituustulosta verkolle. Esc ja välittömästi Enter on kätevin tapa lopettaa sovellus nopeasti muutoksia tallentamatta. Itse algoritmien suoritusajot tapahtuvat no- peimmin pikanäppäimillä F5 (NNH), F6 (2-MST) ja F7 (CHH). Jos tiedoston käsitte- lyssä havaitaan virheitä, sovellus ilmoittaa asiasta englanniksi. Jos ikkuna jäätyy use- aksi minuutiksi, kyseessä on liian laajaksi tehty verkko ja ohjelman sulkemisen voi pakottaa käyttöjärjestelmän käskyllä.

(31)

Kuva 7: Kuvakaappaus sovelluksesta, kun CHH on ajettu läpi onnistuneesti.

Ohjelma koostuu neljästä luokasta ja yhdestä form-tiedostosta, joka muotoilee käyttö- liittymän. Seuraavan sivun luokkakaavio (kuva 8) esittää kunkin luokan metodit ja muuttujat. ”User_interface” sisältää käyttöliittymän toteutukseen tarvittavat metodit ja muuttujat. ”TSP_Solver_UEF_241908” on pääluokka, josta sovellus käynnistetään main-metodin kautta. Se sisältää myös kutsut kaikkiin kolmeen algoritmiin sekä syöt- teen tarkistuksen ennen ajoa. Luokka ”Sub_algorithms” pitää sisällään lähinnä Eukli- disen etäisyyden laskennat sekä luvussa 3.2 esitellyt sivualgoritmit. Viimeinen luokka

”DoubleStack” sisältää pinoon tarvittavat komponentit.

(32)

Kuva 8: TSP Solver -sovelluksen luokkakaavio.

Seuraavat vuokaaviot (kuvat 9, 10 ja 11) mallintavat kukin oman algoritminsa toimintaa. Yksityiskohtia on selitetty luonnollisella kielellä silloin, kun sen on katsottu olevan selkeämpää kuin ohjelmointiläheinen syntaksi.

(33)

Kuva 9: NNH-heuristiikka.

NNH aloittaa satunnaisesta alkusolmusta ja niin kauan kuin yhdistämättömiä solmuja on olemassa, yhdistetään lähin mahdollinen solmu mukaan TSP-reittiin. Menetelmä on yksinkertaisimpia ratkaisutapoja ahneiden heuristiikkojen joukossa.

(34)

Kuva 10: 2-MST-heuristiikka.

Heuristiikka nimeltä 2-MST aloittaa satunnaisesta solmusta MST:n luomisen. Kun MST on valmis, muodostetaan Eulerin kierros puun ympäri. Lopuksi poistetaan tup- lattujen kaarten joukosta ne ylimääräiset kaaret, jotka aiheuttavat samassa solmussa vierailun kahdesti. Christofides-algoritmiin nähden voidaan huomata se ero, että Christofides muodostaa parituksen MST:n solmuille, joilla on pariton asteluku, ja jat- kaa sitten Eulerin kierroksen etsinnästä.

(35)

Kuva 11: CHH-heuristiikka.

CHH on algoritmeista monimutkaisin ja sen yksityiskohtia on kaaviossa selitetty luonnollisella kielellä enemmän kuin kahdessa edellisessä kaaviossa. Heuristiikka muodostaa ensin konveksin peitteen Grahamin skannaus -algoritmilla (Graham, 1972), joka käyttää pinotietorakennetta ja ristituloa. Tämän jälkeen etsitään lähimpiä sisäpis- teitä aiemmin luvussa 2.2 esitettyjen kaavojen avulla ja yhdistetään sisäpisteet mukaan TSP-reittiin yksi kerrallaan. Yhdistäminen tapahtuu lohkaisemalla kevein kolmio pois aiemmin esitetyn kuvan 3 tavalla. Kun sisäpistettä koskettavien kolmioiden painot on laskettu, sisäpistettä koskettavat keveimmän kolmion kaaret yhdistetään reittiin ja kolmion kolmas eli uloin kaari jätetään pois. Näin tapahtuu joka kierros ja kun sisäpisteet loppuvat, on TSP-reitti valmis.

(36)

4.1.2 Tsplib

Tsplib-tiedostoformaatti (Reinelt, 1994, sivu 211) on mahdollista toteuttaa ainakin kolmessa muodossa: tekstitiedostona, sarjallistettuna binääritiedostona ja XML-tie- dostona. Ensimmäisellä rivillä kuvataan nimi attribuutilla NAME. Muita oleellisia att- ribuutteja ovat COMMENT, TYPE, DIMENSION, EDGE_WEIGHT_TYPE ja NODE_COORD_SECTION. Kirjainyhdistelmä EOF puolestaan viittaa tiedoston lu- kemisen päättymiseen, mutta TSP Solver toimii ilman tätäkin. Seuraavassa on tarkemmin kuvailtu attribuuttien tarkoitukset.

NAME : examplegraph1 Verkon nimi.

COMMENT : A 6-node graph. Mahdolliset kommentit.

TYPE : TSP Verkon käyttötarkoitus.

DIMENSION : 6 Verkon laajuus solmuina.

EDGE_WEIGHT_TYPE : EUC_2D Kaarten tyyppi.

NODE_COORD_SECTION Ilmoitus solmuluettelon alkamisesta.

1 0.0 0.5 Lista solmujen koordinaateista, 2 -1.0 1.0 kokonaisluku yksilöi solmun, 3 -1.0 -1.0 luku sekä x- ja y-koordinaatit 4 1.0 -1.0 erotetaan välimerkillä

5 1.0 1.0 ja desimaaliluvussa 6 2.5 0.5 on piste pilkun sijasta.

EOF “End of File”, tiedosto päättyy.

Esimerkki .tsp-tiedostosta. Oikeanpuoleiset suomeksi kirjoitetut tekstit ovat ohjeita, jotka eivät sisälly itse tiedostoon. Tutkielman TSP Solver ei hyväksy negatiivisia lukuja.

Verkon käyttötarkoitus voisi olla myös esimerkiksi CPP (Chinese Postman Problem) tai Tour eli ratkaisu ja kaarten tyyppi esimerkiksi CEIL_2D, jolloin solmujen koordinaatit pyöristettäisiin ylöspäin lähimpään kokonaislukuun. Sovellusten ohjelmoijat vastaavat lopulta itse siitä, kuinka tiedostoa luetaan, eikä tutkielman TSP Solver vedä vertoja esimerkiksi kuuluisalle Concorde-sovellukselle (University of Waterloo, 2017a).

4.1.3 Valmiit esimerkit

TSP on laajasti tutkittu ongelma ja siihen liittyen on julkistettu useita valmiita esi- merkkejä optimaalisten ratkaisujen kera. Waterloon yliopiston verkkosivuilla (Univer- sity of Waterloo, 2017c) on useita esimerkkiverkkoja tsplib-muodossa. Sivustolla on

(37)

eri valtioiden kaupunkien muodostamia verkkoja, laajoja taideteosverkkoja jopa 200 000 solmuun asti sekä Very-Large-Scale-Integration-piiriesimerkkejä.

Kuva 12: Kymmenen tutkittavan verkon rakenteet järjestyksessä pienimmästä suurimpaan. Kuvat on ladattu Waterloon yliopiston verkkosivuilta ja ne on muokattu samaan kuvaan sopivaksi.

http://www.math.uwaterloo.ca/tsp/world/countries.html (31.1.2018) http://www.math.uwaterloo.ca/tsp/vlsi/index.html (31.1.2018) http://www.math.uwaterloo.ca/tsp/vlsi/page2.html (31.1.2018)

Tutkielmassa käsitellään 10 erilaista verkkoa, joista 4 ovat valtioiden kaupunkien si- jaintikarttoja ja 6 puolestaan VLSI-piirejä. Verkot ovat solmujen lukumäärän mukai- sesti koiltaan 38’, 194’, 237, 380, 423, 662, 734’, 813, 929’ ja 1083 solmua. Näistä yläpilkulla (’) merkityt kaupunkiverkot ovat rakenteeltaan hajaantuneita s.e. solmut eivät esiinny järjestelmällisesti pystyrykelminä niin kuin piirilevyjen juotoskohdat.

Juuri nämä 10 verkkoa on valittu tutkittaviksi, koska ne edustavat sopivaa, kasvavaa järjestystä suunnilleen väliltä 30–1090. Tämän kokoiset verkot eivät aiheuta liian pit- kiä odotusaikoja ajettaessa algoritmeja käytännössä.

4.2 Mittarit

Kuvaillaan mittarit, joita algoritmien vertailuissa käytetään. Kokeellisessa osiossa kes-

(38)

on olemassa useita eri vertailukohteita, kuten esimerkiksi optimaalinen ratkaisu, niin kutsuttu Held-Karp-alaraja sekä ajojen aikana paras mitattu tulos. Koska optimiratkai- sut ovat saatavilla Waterloon yliopiston verkkosivuilta, käytetään vertailukohteena op- timi-TSP-reittejä.

4.2.1 Mittareiden kuvailu yleisesti

Tutkielman kolmesta algoritmista on tarkoitus kuvata teoreettisesti aikavaativuus, tarkkuus, toteutusvaikeus ja apualgoritmit. Käytännössä testataan ajan ja muistin käyt- töjä sekä poikkeavuuksia optimituloksesta. Suoritusaikaa mitataan millisekunteina ja muistin käyttöä megatavuina. Käyttöjärjestelmänä toimi yliopiston tietojenkäsittely- tieteen laitoksen PC, jossa oli asennettuna 64-bittinen Windows 10 Education -käyttö- järjestelmä. Laitteessa oli 16 gigatavua RAM-keskusmuistia ja x64-pohjainen 4- ydinprosessori malliltaan Intel(R) Core(TM) i7-6700 CPU @ max speed 3.41 GHz.

Testaushetkellä laitteessa oli asennettuna Javan versio 8, päivitys 121 (build 1.8.0_121-b13). Jokaiselle 10 verkolle tehtiin 3 testiajoa tutkielman kolmella algoritmilla.

4.2.2 ResourceTracker (Pekka Kilpeläinen)

Tutkittaessa ohjelman ajan ja etenkin muistin käyttöä on apuna käytetty FT Pekka Kil- peläisen ResourceTracker-ohjelmaa (Kilpeläinen, 2018). Sen lähdekoodissa oleva ko- mento System.nanoTime() on hyödyllinen, kun on otettava talteen suorituksen alka- mis- ja päättymisajat. Muistin käyttö huipussaan (engl. peak memory usage) ilmais- taan tavuina. Tavallinen käyttäjä ei näe ajan ja muistin mittauksia, sillä tulokset tulos- tetaan System.out.println-toiminnolla.

(39)

5 Tulokset

Tutkielmaa edeltäneen kokeellisen työn oleellisena tavoitteena oli saada TSP Solver -ohjelman avulla tieteellisessä mielessä luotettavia tuloksia. Nämä tulokset esitetään tässä luvussa. Aluksi arvioidaan sitä, missä määrin sovelluksen antamiin tulosteisiin voi luottaa. Seuraavaksi esitetään tilastoja suorituksista. Lopuksi tehdään koonti ai- neiston pohjalta nousseista johtopäätöksistä.

5.1 Tulosten luotettavuuden arviointi

Seuraavissa kahdessa aliluvussa kuvatut tilastot ja johtopäätökset ovat luotettavia sillä edellytyksellä, että ohjelmistovirheitä ei ole ja luvun 4 mittarit ovat täsmälliset. Suori- tusajot ovat julkisesti kenen tahansa toistettavissa Java-ympäristössä, eikä ristiriitai- suuksia ilmene. Lisäksi tarkasteltavat verkot (10 kappaletta) ovat olleet riittävän laajoja sekä satunnaistettuja johtopäätösten tekemiseksi. Esimerkiksi yli 10000 solmun verkkojen käsittely tuottaisi liian pitkiä odotusaikoja etenkin CHH-heuristiikalla.

5.2 Tilastot

Ajoja suoritettiin kaikkiaan 30 ja taulukon 2 osoittamalla tavalla.

Taulukko 2: Kolmenkymmenen ajon suoritusnumerot kullakin verkolla. Yläpilkulla (’) merkittyjen verkkojen solmut ovat kaupunkeja ja muiden verkkojen solmut ovat puolestaan VLSI-juotoskohtia.

Verk- ko

dj38’ qa194’ xqg237 bcl380 pbn423 xql662 uy734’ dkg813 zi929’ xit1083

Ajo 1 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Ajo 2 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.

Ajo 3 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.

(40)

Kuva 13: Algoritmien suoritusaikojen tilastollinen vertailu. CHH-algoritmin alapiikki kohdassa 27 joh- tunee käyttöjärjestelmän hetkellisestä hidastelusta kohdan 26 aikana.

Vaikka 2-MST- ja CHH-heuristiikoiden aikavaativuudet yleisesti ottaen ovat O(n²log 2 (n)), tutkielman toteutuksessa molempien aikavaativuus on O(n³). Tästä joh- tunee niiden samankaltainen käyttäytyminen kuvassa 13. Prim-algoritmi 2-MST- heuristiikassa sisältää kolme sisäkkäistä for-silmukkaa (Hyvönen, 2017, tiedosto Sub_algorithms.java) ja CHH-heuristiikan rakenne on selitetty luvussa 3.1.3.

Kuva 14: Algoritmien muistin käytön tilastollinen vertailu.

Muistia mitattiin NetBeans-sovelluskehitysvälineen käydessä taustalla. Yksikkö Mt eli megatavu tarkoittaa aidon SI-järjestelmän tapaan miljoonaa tavua.

(41)

Kuva 15: Algoritmien tarkkuuksien eli optimiratkaisuista poikkeavuuden tilastollinen vertailu.

(42)

CHH-algoritmin tarkkuuden suhteen voidaan huomata, että sama tulos on löydetty kol- mesti kullekin kymmenelle verkolle, sillä algoritmi on deterministinen eli se päätyy samalla syötteellä aina samaan lopputulokseen. NNH ja 2-MST sen sijaan valitsevat aina satunnaisen aloitussolmun, josta reittiä aletaan laskea, ja täten ne voivat päätyä samalla verkolla eri tuloksiin.

5.3 Johtopäätökset

Seuraavat johtopäätökset voidaan laatia tilastollisten kokeilujen pohjalta:

1) NNH on algoritmeista ajallisesti kaikkein tehokkain ja CHH tehottomin.

2) NNH on algoritmeista vähiten muistia kuluttava ja CHH kuluttaa eniten muistia.

3) Algoritmien tarkkuudet riippuvat käsiteltävien verkkojen rakenteesta eli solmujen sijoittelusta. Vaikka NNH on useissa tapauksissa tarkin, CHH löytää edullisempia TSP-reittejä sellaisista verkoista, joissa solmujen asettelu on satunnaisenomaista ja eri- tyisiä pystyryhmitelmiä esiintyy niukasti.

4) Vaikka 2-MST onkin approksimointialgoritmi ja kuluttaa aikaa sekä muistia kohtuudella, sen antaman tuloksen tarkkuus on harvoin paras verrattuna kahden muun algoritmin tuloksiin.

(43)

6 Pohdinta

Alkuperäinen tutkimuskysymys oli ”kuinka kolme valittua algoritmia poikkeavat toi- sistaan tarkkuuden ja ajallisen tehokkuuden suhteen?” On tutkittu, kuinka myös sol- mujen sijoittelut vaikuttavat algoritmien toimintaan ja kuinka risteyksien välttäminen verkossa takaa usein tuloksia, jotka ovat lähempänä optimaalista ratkaisua. Väitteet ovat matemaattisesti perusteltavissa.

Tulosten pohjalta voidaan todeta, että NNH on ajallisesti tehokkain, kuluttaa vähiten muistia ja on useissa tapauksissa tarkin, kun verkossa esiintyy linjamaisia piirteitä solmujen sijoittelussa. CHH puolestaan on ajallisesti tehottomin ja vie eniten muistia, mutta sen antamat reitit ovat usein tarkimpia verkoissa, joissa solmujen sijoittelu on satunnaisempaa. Algoritmeista 2-MST kuluttaa aikaa ja muistia kohtuudella. Vaikka 2-MST ei tavallisesti takaa tarkkaa reittiä, sillä on olemassa takuu korkeintaan 2-ker- taisesta TSP-reitistä optimiin verrattuna.

Mielenkiintoista olisi ollut sisällyttää tutkielmaan useampiakin algoritmeja, kuten Christofides-heuristiikka ja Lin-Kernighan-heuristiikka (Nilsson, 2003, sivut 2 ja 4).

Tutkielman päätavoitteiden kannalta ei kuitenkaan ollut järkevää tarkastella enempää kuin kolmea algoritmia. Jatkokehitysideaksi kävisi myös erilaisten aputietorakentei- den kokeilu. Prim-algoritmissa esimerkiksi olisi mahdollista hyödyntää niin kutsuttua Fibonacci-kekoa, joka teoriassa olisi hyödyksi suurilla syötteillä (Skiena, 2008, sivu 487).

Tutkielma ja sen taustatyönä rakennettu TSP Solver antavat vahvan pohjan TSP-ongelmaan tutustumiselle kenelle tahansa. Koska lähdekoodit ovat julkisia, käyttäjä voi omin päin tehdä monenlaisia jatkokehityksiä sovellukseen ja sen algoritmeihin.

Vaikka Millennium-ongelman ratkaisun edistäminen onkin tässä hyvin epätodennä- köistä, kokeilija voisi käytännössä luoda Java-kielellä esimerkiksi Android-sovelluksen omaan tarkoitukseensa. Oleellisinta on löytää mahdollisimman lyhyitä reittejä verkoista, mihin on nyt helposti saatavilla kolme eri menetelmää erittäin yleisellä ohjel- mointikielellä.