Skip to content

Latest commit

 

History

History
118 lines (92 loc) · 8.18 KB

toteutus.md

File metadata and controls

118 lines (92 loc) · 8.18 KB

Toteutusdokumentti

Ohjelman rakenne ja kuvaus

Algos-paketti

Paketti sisältää algoritmi X:n rajapinnan määrittelyn ja varsinaiset implementaatiot. Kummatkin algoritmit seuraavat samaa Algoritmi X:n perusajatusta, joka on pseudokoodina seuraava:

Jos annetussa matriisissa ei ole kolumneja, on löydetty ratkaisu.
Muuten: valitse sarakkeista c, jossa on vähiten alkioita.
Jokaista sarakkeen c riviä r kohtaan:
  Sisällytä r ratkaisuun
  Jokaiselle rivin r kolumnille j
    Jokaiselle kolumnin j riville t
      poista rivi t matriisista
  Käynnistä haku rekursiivisesti riisutulle matriisille
  Palauta poistetut rivit käänteisessä järjestyksessä

DLX -algoritmi perustuu Dancing links -tekniikkaan, jossa poistetaan ja palautetaan "in-place" kaksisuuntaisesti ja ympäri matriisin linkitettyjä solmuja ("double linked circular linked lists"). Solmut ovat siis muistissa algoritmin suorituksen ajan, jolloin poistettujen solmujen palauttaminen on tehokasta. Toteutus perustuu Donald Knuthin artikkeliin vuodelta 2000.

DictX -algoritmi perustuu hajautukseen, jossa kunkin kolumnin solmut on tallennettu dict / ja set-tietorakenteisiin. Näin sopivan kolumnin ja rivin löytäminen on nopeaa. Toteutus perustuu Ali Assafin blogiin (vuosi tuntematon).

Data creators -paketti

Paketti sisältää eri ongelmatyyppien ratkaisemiseen tarvittavat datan generoijat.

Pentomino-moduuli toimii seuraavasti:

  • Ensin generoidaan sopiva universumi: yksi alkio jokaista pentominoa kohtaan, tunnisteena pentominon nimi ja yksi alkio jokaista mahdollista paikkaan kohtaan, tunnistetaana paikan koordinaatti (x,y). Universumiin tulee siis 12 + 60 = 72 alkiota.
  • Seuraavaksi generoidaan joukko joukkoja universumin elementtejä. Jokaista pentominoa ja pentominojen kääntöjä kohtaan tehdään yksi kuuden alkion joukko: joukko sisältää pentominon nimen sekä viisi koordinaattia, jotka peittyvät pentominon asettamisen myötä.
  • Lopputuloksena syntyy matriisi, josta on mahdollista löytää täsmäpeite. Täsmäpeitteeseen kuuluu jokainen kahdestatoista pentominosta ja jokainen kuudestakymmenestä peitetystä koordinaatista.

Sudoku-moduuli toimii seuraavasti:

  • Ensin generoidaan sopiva universumi: neljä alkiota jokaista mahdollista laitettua numeroa kohtaan. Alkiot ovat laitetun numeron varaama koordinaatti (x,y), numeron varaama rivi, numeron varaama sarake sekä numeron varaama ruutu.
  • Seuraavaksi generoidaan joukko joukkoja universumin elementeistä. Tässä käydään läpi annettu sudokulauta ja jokaista ruutua kohtaan generoidaan joko yksi tai yhdeksän joukkoa. Jos ruudussa on valmiiksi jokin numero, generoidaan vain yksi joukko sisältäen alkiot yllämainitulla tavalla. Muussa tapauksessa generoidaan yhdeksän joukkoa: yksi jokaista mahdollista numeroa varten.
  • Lopputuloksena syntyy matriisi, josta on mahdollista löytää täsmäpeite. Täsmäpeitteeseen kuuluu 81 riviä, joista jokainen kuvaa jonkin numeron sijoittamista johonkin koordinaattiin siten, että sudokun säännöt on huomioitu.

Datastructures-paketti

Paketti sisältää ohjelman tarvitsemat itse tehdyt tietorakenteet:

  • Matriisien rajapinta.
  • Dancing links -toteutuksessa tarvitut linkitettyjen listojen erityyppiset solmut sekä matriisitoteutus, jonka metodeilla solmut liitetään yhteen
  • Hajautustaulu-pohjainen matriisitoteutus,
  • Pentominojen esitys sekä kahdentoista pentominon yhteenkoonti

Services-paketti

  • Solver-moduuli toimii rajapinta käyttöliittymään ja mm. käynnistää datan generoinnin, algoritmit jne. sekä palauttaa löydetyt ratkaisut

Translator-paketti

  • Paketin ainoa moduuli sisältää toiminnallisuuden algoritmin löytämien ratkaisujen kääntämiseen ymmärrettävämpään muotoon eli valmiiksi pentomino-laudoiksi, sudoku-laudoiksi tai ratkaisuun valittujen osajoukkojen listaksi

UI

UI on toteutettu pienen python-serverin ja react-appin avulla. Kaikki ohjelman ominaisuudet eivät ole käytettävissä UI:n kautta, vain pentominojen ja sudokun ratkaiseminen.

Saavutetut aika- ja tilavaativuudet

Datan generointi ja saatujen tulosten kääntäminen valmiiksi pentomino- sekä sudoku-laudoiksi sujuu melko lailla vakioajassa: esimerkiksi tyhjän 9x9 -sudokun täsmäpeitematriisiin tarvittavan datan generoiminen kestää n. sekunnin kymmennesosan. Analyysissä keskitytäänkin siksi vain Algoritmi X:n implementaatioihin.

Algoritmi X

Analyysi perustuu enimmäkseen David Eppsteinin blogiin vuodelta 2008.

Ohjelman pääalgoritmi toimii rekursiolla, ja jokaisella rekursiotasolla kutsut ovat toteutettujen tietorakenteiden ansiosta vakioaikaisia, joten saamme aikavaativuuden ylärajan seuraavasti: Olkoon F on joukko, jonka alkiot ovat joukkoja ja F:n alkioista voidaan rakentaa täsmällinen peite. Valitaan jokin x ja määritellään, että C on kaikkien niiden F:n alkioiden S_i joukko, joissa x \in S_i. Nyt algoritmi suorittaa |C| rekursiokutsua, joista jokaisella F:n koko on enimmillään n - |C|. Tästä saadaan ylärajaksi O(3^(n/3).

Algoritmi toimii käytännössä käyttämällä raakaa voimaa kaikkien mahdollisten ratkaisujen etsintään. Tehokkaan siitä tekee kuitenkin toteutus, jossa 1) sopivat kolumnit haetaan ajassa O(n) käymättä kaikki n kolumnin m riviä läpi ja 2) yksittäiset solmut voidaan palauttaa paikalleen ajassa O(1), eikä niitä tarvitse käydä säilöä mihinkään tietorakenteeseen haun poistaessa ne.

Tilavaativuuden yläraja on O(n), sillä linkitetyistä listoista koostettuun matriisiin tallennetaan ainostaan annettujen joukkojen elementtien kuvaus. Jokaista erillistä elementtiä kohtaan luodaan yksi kolumnisolmua ja jokaista elementtiä kohtaan luodaan yksi datasolmu. Esimerkiksi joukon ((1,2,4), (2,3,4)) kuvaamiseksi tarvitaan kuusi datasolmua sekä neljä kolumnisolmua.

Suorituskyky ja O-analyysivertailu

Kaikkien suurin vaikutin ohjelman tehokkuuteen on mahdollisten ratkaisujen määrässä: yksittäisen ratkaisun löytäminen on isoillakin (n = 10^6) syötteille melko lailla yhtä nopeaa kuin pienillä syötteillä - helposti alle sekunnin. Kaikkien ratkaisuiden löytäminen sen sijaan muuttaa algoritmin suorituskestoa merkittävästi.

Testejä ajaessa huomasin, että periaatteellisesti samasta aikavaativuudesta huolimatta DictX suoriutuu selvästi hitaammin. Suurin osa huonommasta suorituskyvystä liittynee seuraaviin seikkoihin:

  • DictX poistaa ja palauttaa alkioita set- ja dictionary -tietorakenteista, DLX palauttaa vain viitteet toisiin solmuihin muistissa
  • DictX säilöö joka kierroksella poistetut rivit listaan, jotta ne voidaan palauttaa
  • DictX joutuu vertailemaan palautettavia ja poistettavia rivejä alkuperäiseen joukkojen kokoelmaan, DLX:n ei tarvitse tehdä vertailua.

Kaiken kaikkiaan kuitenkin Algoritmi X ja erityisesti DLX-pohjainen toteutus tuo erityisesti täsmäpeitteeksi käännettäviin ongelmiin merkittävää tehoa. On vaikea päästä alle sekunnin suorituskykyyn sudokujen tai pentomino-lautojen ratkaisuihin vain läpikäymällä mahdollisia numeroiden tai pentominojen asetteluita.

Työn mahdolliset puutteet ja parannusehdotukset

  • Hajautustaulupohjaista ratkaisua olisi todennäköisesti mahdollista optimoida vielä käyttämällä listoja aidon O(1) -pääsyn takaamiseksi hajautuksen keskimääräisen O(1) -pääsyn sijaan
  • Ohjelmaa olisi hyvä laajentaa mahdollisten syötteiden myötä
  • Python on kielenä selvästi hitaammasta päästä, joten hajautustauluja sekä linkitettyjä listoja seuraava toteutus jollain low-level -kielellä voisi tuoda kiinnostavia puolia esille

Lähteet