Tietorakenteiden harjoitustyö – kesä 2010

Aiheen määrittely

Valitsin aiheeksi A*-reitinhaun, jonka toimintaperiaate on kuvattu ^[1][2]. Algoritmi saa syötteenä kaksiulotteisen kartan, jota se tulkitsee verkkona. Kartta koostuu ruuduista, jotka tulkitaan verkon solmuiksi. Yhdestä ruudusta pääsee ainoastaan ympäröiviin vierusruutuihin, eli solmulla on korkeintaan 8 vierussolmua. Jotkut solmut ovat "seiniä", joiden kautta ei pääse etenemään mihinkään. Algoritmin tavoitteena on löytää lyhin reitti kahden solmun välillä.

Missä Dijkstran algoritmi etenee kaikkiin suuntiin tasaveroisesti, A*-algoritmi pyrkii ohjautumaan systemaattisesti maalia kohti niin, ettei aivan selvästi vääriä vaihtoehtoja turhaan tutkita.

Implementoin harjoitustyön seuraavin ominaisuuksin ja oletuksin:

Pysty- ja vaakasuoraan liikkuminen on kustannukseltaan yksi.
Vinottain liikkumisen kustannus on ~sqrt(2)
Vaikeakulkuinen maasto: joidenkin solmujen kautta kulkeminen on kalliimpaa kuin toisten

Ohjelman syöte ja tulostus

Ohjelmalle annetaan syötteenä bittikarttakuva, johon on värikoodattu lähtösolmu, maalisolmu, seinät ja vaikeakulkuiset maastot. Jokainen pikseli tulkitaan solmuksi. Kuvan tilanteessa, missä maali- ja lähtösolmuksi on merkitty useampi pikseli, valitaan se jonka kuvankäsittelijä ensimmäiseksi kohtaa, eli se joka on kaikista ylimpänä ja vasemmalla. Muut saman värin pikselit tulkitaan yhden painoisiksi lattioiksi.

kuva esimerkki syötteestä

A*-haun päätyttyä ohjelma tulostaa ruudulle kopion annetusta kuvasta, johon on merkitty lyhin reitti. Tulostettavassa kuvassa näkyy myös tummennettuna kaikki ne solmut/pikselit, jotka jouduttiin lisäämään kekoon algoritmin suorituksen aikana.

Algoritmit ja tietorakenteet

A*-hakualgoritmi

Kevään 2010 tietorakenteet-kurssin luentomonisteen^[1] ja Wikipedian artikkelin^[2] mukaan.

Heuristiikkafunktio

Jos heuristiikkafunktion antama etäisyysarvio on suurempi kuin todellinen etäisyys maalisolmuun, ei A*-haku välttämättä löydä lyhintä polkua.^[1] Toisaalta liioittelemalla voidaan parantaa algoritmin suorituskykyä. Manhattan-etäisyys ei sovellu tähän tapaukseen hyvin, sillä verkossa on mahdollista siirtyä myös diagonaalisesti. Heuristiikkafunktion pohjaksi valitsen ainakin näin aluksi Euklidisen etäisyyden, jolloin arvioissa ei ole ainakaan liioittelemisen vaaraa.

Minimikeko

Kevään 2010 tietorakenteet-kurssin luentomonisteen mukaan^[1]

Verkko

Ei ainakaan vierusmatriisiesitys, sillä solmuja tulee olemaan paljon, mutta jokaisella solmulla on korkeintaan 8 vierussolmua. Näillä näkymin jonkinlainen variaatio vieruslistaesityksestä.

A*-hakualgoritmin haluttu aika- ja tilavaativuus

Aikavaativuus: O((|E|+|V|)log|V|)
Tilavaativuus: O(|V|)

Käyttöohjeet

Ohjelman ajaminen

Ohjelmakoodi käännetään ajamalla komento javac -d bin -sourcepath src src/Main.java projektin juurihakemistossa, jolloin käännetyt moduulit ilmestyvät bin-hakemistoon.
Ohjelma käynnistetään komennolla java Main hakemistossa, jossa käännetyt ohjelmamoduulit sijaitsevat.
Ohjelman alussa avautuu tiedostonvalintaikkuna, jossa tulee valita sopivaa kuvamuotoa oleva tiedosto tietokoneelta. Valittu tiedosto tulkitaan ongelmaksi, johon A*-reitinhakualgoritmi etsii ratkaisun.

(* Ohjelman voi käynnistää myös antamalla luettavan kuvatiedoston polun komentoriviparametrina, esim. java Main C:/tira/maze.bmp, jolloin tiedostonvalintaikkunaa ei tule esille ollenkaan. )
Ohjelma tulostaa ruudulle ratkaisun, jos sellainen löytyi. Ikkunan yläosassa on painike, josta voi tallentaa ratkaisun bittikarttakuvaksi (.bmp) kovalevylle. Lisäksi verkon luomiseen sekä A*-algoritmin suoritukseen käytetty aika tulostetaan sille komentoriville/terminaaliin, josta ohjelma käynnistettiin.

Jos ratkaisua ei löytynyt (tai kuvassa ei ole maali- tai lähtösolmua), niin ohjelma ilmoittaa asiasta komentorivillä/terminaalissa, eikä ylläolevaa ikkunaa ponnahda ollenkaan näkyviin.

Syötteen muoto

Ohjelma hyväksyy syötteeksi kuvatiedoston. Sallitut kuvatiedostomuodot ovat BMP, GIF ja PNG. Kuvien värit tulkitaan tiukasti alla olevan taulukon mukaisesti. Jokaisessa kuvasyötteessä on oltava vähintään lähtö- ja maalisolmut määriteltyinä.

Red	Green	Blue	Väri	Merkitys
0	0	255	Sininen	Lähtösolmu
0	255	0	Vihreä	Maalisolmu
0	0	0	Musta	Lävitsepääsemätön seinä
255	255	255	Valkoinen	Normaali solmu/lattia. Kustannus on 1.
0-255	0-254	0-254	Muut	Solmu/lattia. Kustannus lasketaan seuraavasti: $\sqrt{256-blue}+\sqrt{256-green}$ . Käytännössä kannattaa käyttää punaisen eri sävyjä (tummempi = kalliimpi), jolloin kartta on ihmiselle helpommin tulkittavissa.

Toteutuksen kuvaus algoritmien ja tietorakenteiden osalta

Toiminta

Ohjelman kolme ydinkomponenttia ovat: A*-reitinhakualgoritmi AStarPathFinder, minimikeko MinimumHeap sekä verkon esitys Graph. Homma lähtee tietorakenteiden osalta käyntiin siitä, kun kuvankäsittelijä on lukenut kuvan ja luo luettujen pikseleiden pohjalta itse verkon. Rakennuksen yhteydessä, verkko luo jokaista solmua kohti Node-olion, joka sisältää mm. sijainnin verkossa, painon, sekä muuta A*-haulle ja minimikeolle arvokasta informaatiota.

Kun verkko on rakennettu on aika siirtyä suorittamaan A*-hakua. Kuvankäsittelijän selvittämät lähtö- ja maalisolmut, sekä verkko annetaan parametreinä A*-algoritmille. Heti ensi töikseen algoritmi alustaa minimikeon ja asettaa lähtösolmulle etäisyydet. Erilaisia polku- ja kustannustaulukoita^[1] ei tarvita, samat tiedot löytyvät jo Node-olioista valmiiksi alustettuina. Lopuksi algoritmi alkaa etsimään lyhintä polkua kahden solmun välillä.

Kun algoritmi vihdoin löytää (tai ei löydä käytyään läpi kaikki saavutettavissa olevat solmut) polun, tieto välitetään ylöspäin pääluokalle Main, joka polun olemassaollessa välittää sen edelleen piirtäjäluokalle.

Valitut ratkaisut

Verkko (`Graph.java`)

Verkko esitetään Node-tyyppisenä kaksiulotteisena taulukkona, joka on enkapsuloitu Graph-luokan sisään. Taulukkoa operoidaan koordinaatistona, jossa yhden solmun vierussolmut (i,j) löytyvät sen vieressä olevista alkioista eli: (i-1,j), (i+1,j), (i,j-1), (i,j+1), (i-1,j-1), (i-1,j+1), (i+1,j-1) ja (i+1,j+1).

Seiniä varten ei luoda Node-olioita, vaan arvoksi jätetään null. Näin ollen seinät eivät ole oikeastaan solmuja, vaan osoitus siitä, että solmua ei tietyssä alkiossa/ koordinaatissa ole.

Verkko on tilavaativuudeltaan O(|V|), koska minkäänlaista esim. vierussolmulistaa ei ylläpidetä. Verkon luonti on aikavaativuudeltaan O(|V|). Vierussolmut jollekin solmulle evaluoidaan vasta, kun A*-algoritmi pyytää verkolta sen solmun naapurit. Koska vierussolmuja on aina korkeintaan kahdeksan, on operaation aika- ja tilavaativuus ainoastaan O(1). Käytännössä operaatio on kuitenkin aika kallis. Kokonaissuorituksen kannalta onkin järkevämpää selvittää solmun naapurit vasta sitten, kun solmu tulee reitinhakualgoritmin käsittelyyn. Tällöin naapureita ei turhaan selvitetä sellaisille solmuille, jotka eivät koskaan tule käsiteltäväksi. Koska jokainen verkon solmu tulee reitinhaussa käsitellyksi korkeintaan kerran, ei selvitettyjä vierussolmuja tarvitse talletaa tehokkuusmielessä välimuistiin.

Minimikeko (`MinimumHeap.java`)

Toteutettu binäärikekona. Keon koko on vakio, eli se ei kasva automaattisesti. Verkon luonnin jälkeen tiedetään jo keon maksimaalinen koko, ja keon kasvattaminen on turhan kallis operaatio O(n). Keko koostuu kahdesta taulukosta, joita käsitellään puina. Ensimmäinen taulukko ilmaisee prioriteettia, ja toinen vastaavaa dataa eli Node-oliota. Minimikekoon on myös toteutettu metodi, jolla voi laskea jonkun alkion avainarvoa, eli nostaa sen prioriteettia keossa.

Kekoon lisäämisen, pienimmän alkion poistamisen, ja avainarvon laskemisen aikavaativuudet ovat O(log n). Muut (ulospäin näkyvät) operaatiot ovat aikavaativuudeltaan vakioita. Tilavaativuudeltaan kaikki operaatiot ovat pääsääntöisesti vakioita. Poikkeuksen tekee heapify()-metodia hyödyntävä kekoon lisääminen, joka on tilavaativuudeltaan O(log n) rekursion takia.

Solmu (`Node.java`)

Esittää yhtä solmua. Toteutukseltaan yksinkertainen "getter/setter"-luokka, joka sisältää tietoa liittyen solmuun verkossa, reitinhakualgoritmissa ja minimikeossa. Tiedon luonteen vuoksi yksi solmu voi kuulua samaan aikaan vain yhteen verkkoon ja kekoon. Samoin jos reitinhaun haluaa suorittaa uudestaan samoille solmuille, tulee niiden etäisyysarviot resetoida oletusarvoihin manuaalisesti.

A*-reitinhakualgoritmi (`AStarPathFinder.java`)

Toteutettu pitkälti Kevään 2010 tietorakenteet-kurssin luentomonisten^[1] mukaan. Polku- ja etäisyysarviotiedot säilytetään taulukoiden sijasta solmuolioissa. Solmun naapureiden selvittäminen, etäisyysarvion laskeminen ja kekoon lisäys tehdään vasta viime tingassa, eli kun solmu tulee A*:in käsiteltäväksi. Tällöin ei turhaan prosessoida sellaisia solmuja, jotka eivät koskaan tulee A*:n käsiteltäväksi. Seurauksena kokonaissuoritusaika paranee.

Heuristiikkafunktiona toimii Eukliidinen etäisyys eli $\sqrt{(dx)^2 + (dy)^2}$ , missä dx ja dy on maalisolmun ja jonkun muun solmun x ja y kordinaattien erotus. Koska etäisyysarvio on aina vähemmän tai yhtä kuin todellinen etäisyys, antaa A*-algoritmi aina oikean vastauksen, eikä esim. toiseksi lyhintä polkua. Heuristiikkafunktion aika- ja tilavaativuus on vakio.

A*-algoritmin aikavaativuus on O((|E|+|V|)log|V|) ja tilavaativuus pahimmassa tapauksessa O(|V|). Tilavaativuuden määrää algoritmissa oleva keko, jonka koko valitaan sen mukaan, kuinka monta Node-oliota luotiin verkkoa luodessa. Ts. seinille (null) ei varata keosta tilaa.

Testit

Projektia on testattu yksikkötestein ja manuaalisesti bittikarttakuvin. Bittikarttakuvat löytyvät hakemistosta bitmaps. Testit löytyvät hakemistosta test.

Testit käännetään ajamalla seuraava komento projektin juurihakemistossa:

javac -cp bin/junit-4.8.2.jar -d bin -sourcepath test:src test/AllTests.java

Kaikki testit ajetaan suorittamalla seuraava komento bin-hakemistossa:

java -cp junit-4.8.2.jar:. AllTests

Yksittäisen testin, esim. verkkotestin voi ajaa seuraavasti:

java -cp junit-4.8.2.jar:. org.junit.runner.JUnitCore GraphTests

Projekti ja työtunnit

Lähdekoodit ja linkki versionhallintaan löytyy Google Codesta.

Päivämäärä	Tuntimäärä	Kuvaus
21.5.2010	5h	Aiheeseen tutustuminen ja määrittelyn kirjoittaminen.
22.5.2010	6h	Versionhallinnan pystyttäminen, yksinkertaisen verkon toteuttaminen, sekä A*-haku algoritmin nopea toteutus.
23.5.2010	12h	A-haku algoritmin nopea toteutus korjattu toimivaksi. Kuvien lukeminen. Reitin tulostaminen kuvana ruudulle. Suorituskyvyn optimoiminen ja koodin parantaminen. Testitapaus verkkoluokalle. Perehtymistä ja kirjoittelua Ahaku algoritmin oikeellisuudesta ja heuristiikkafunktiosta.
24.5.2010	3h	Minimikeon ja sen testikeissin toteutus, sekä integraatio A*-hakuun
25.5.2010	2h	Kekoon lisättyjen solmujen tummentaminen, A*-haulle pari testitapausta
26.5.2010	1h	Main-luokan siistimistä
27.5.2010	1h	Korvasin vahingossa jäännen ArrayListin taulukolla, ja pari muuta pientä bugifiksiä.
28.5.2010	3h	Vaikeakulukuisen maaston implementointi, tiedoston valinta ikkuna, ja lopputuloksen tallennus tiedostoon
29.5.2010	3h	Ohjelmakoodin bugien fiksaaminen, vaikeakulkuisen maaston värikoodien muuttaminen ja käyttöohjeiden kirjoittaminen.
30.5.2010	2.5h	Koodin refkatorointia: kuvaavampia nimiä, suurien metodien jakaminen useampaan pienempään, optional: tiedoston määritys komentoriviparametrilla
31.5.2010	0.5h	JavaDoccia Main-luokalle ja vierussolmujen haku hieman luettavammaksi
1.6.2010	2h	JavaDoccia tietorakenne- ja algoritmiluokkiin
2.6.2010	2.5h	Verkkoluokalle pari uutta testiä, sekä JavaDoccien selkeyttäminen
7.6.2010	4h	Dokumentaation päivittäminen, testeille selkeämmät nimet, sekä toteutusosion kirjoittelua.
8.6.2010	0.5h	Toteutusosion kirjoittaminen loppuun.
18.6.2010	5h	Kriittisen bugin etsiminen ja korjaaminen, sekä lisää outputtia mm. käytyjen solmujen lkm ja löydetyn polun koko
19.6.2010	2h	Keon korjaaminen ja väritulkinnan siirtäminen omaan luokkaansa.
20.6.2010	2h	Tiedostonvalintaikkunan korjaus, ja dokumentaation sekä lähdekoodin läpikäyminen
21.6.2010	2h	Projektin paketointi, ohjeet testien kääntämiselle ja ajamiselle.
Total	= 59h