Polyominojen pakkaaminen tasossa

Abstract

Polyominot ovat kaksiulotteisia kappaleita, jotka muodostuvat yhdestä tai useammasta, särmistään toisiinsa liitetyistä, samankokoisista neliöstä. Tason täyttäminen valitulla polyominojoukolla on NP-täydellinen ongelma. Tässä tutkielmassa esitetään uusi tarkistussummiin perustuvan menetelmä, joilla polyominojen pakkaamista tasolle pyritään tehostamaan aiempiin vastaaviin pakkausmenetelmiin verrattuna. Kutsun kehittämääni menetelmää moduloidun bittikentän menetelmäksi. Moduloidun bittikentän menetelmässä täytettävälle alueelle sekä polyominoille etsitään sopiva jakaja. Jakajan perusteella täytettävälle alueelle ja polyominoille lasketaan tarkistussummat. Sopivalla jakajan valinnalla tarkistussummat saadaan kuvaamaan samanaikaisesti sekä polyominon muotoa että sijaintia täytettävällä alueella. Kaikki mahdolliset ratkaisuvaihtoehdot alueen täyttämiseksi voidaan löytää alueen ja kappaleiden yhteenlaskettuja tarkistussummia vertailemalla. Moduloidun bittikentän menetelmällä alkuperäinen vaikea tehtävä jakautuu useammaksi pienemmäksi tehtäväksi, joiden ratkaiseminen voi usein olla huomattavasti alkuperäistä tehtävää helpompaa. Tutkielmassa esitetään myös muutokset, jotka mahdollistavat hajota ja hallitse -menetelmän käytön moduloidun bittikentän menetelmän yhteydessä. Hajota ja hallitse -menetelmään soveltamiseksi tarkistussummat muunnetaan sopivaan binääriseen kantalukuesitykseen. Sopivalla binäärisellä kantaluvulla kappaleille voidaan muodostaa tarkistussummat aiempaa pienemmällä jakajalla säilyttäen tieto kappaleen muodosta ja sijainnista. Huomattavan nopeusedun ansiosta moduloidun bittikentän menetelmä mahdollistaa huomattavasti suurempien alueiden pakkaamisen kuin vastaavat bittikenttiin perustuvat menetelmät. Hajota ja hallitse -menetelmän ansiosta moduloidun bittikentän algoritmi on myös erittäin tehokkaasti rinnakkaistettavissa.