Barysentrisen heuristiikan ja mukautuvuusanalyysiin perustuvan algoritmin vertailu matriisien järjestämisessä
ANDERSEN, SIRKKA (2013)
ANDERSEN, SIRKKA
2013
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2013-07-29
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201311111579
https://urn.fi/URN:NBN:fi:uta-201311111579
Tiivistelmä
Tutkielmassa käsitellään matriisien järjestelyyn käytettävien algoritmien ominaisuuksia ja historiaa sekä matriisien ja graafien yhteisiä sovellus- ja ongelmaalueita. Matriisien järjestelyalgoritmeista tutustutaan tarkemmin mukautuvuusanalyysiin ja miinustekniikkaan perustuvan järjestelyalgoritmin toimintaan, minkä lisäksi tutustutaan kaksijakoisen graafin risteymien minimointiin perinteisesti käytettyyn barysentriseen heuristiikkaan ja käsitellään risteymien minimointiongelma matriisin järjestelyongelmana. Kumpaankin tekniikkaan perustuvat järjestelyt toteuttiin ohjelmallisesti ja testattiin erityyppisillä ja -kokoisilla matriiseilla. Työssä toteutettiin myös uusi barysentriseen järjestelyyn ja miinustekniikkaan perustuva järjestely, jota sovellettiin muiden tekniikoiden ohella risteymien minimointiongelmaan. Uusi järjestelytekniikka toimi erityisen lupaavasti synteettisesti generoidulla kaistamaisella aineistolla. Testiajojen perusteella myös mukautuvuusanalyysiin ja miinustekniikkaan perustuva algoritmi toimi lupaavasti risteymien minimointiin liittyvien hahmojen muodostamisessa ja risteymien minimointitehtävässä.
Tuloksien perusteella miinustekniikka ja mukautuvuusanalyysi voivat olla varteenotettavia vaihtoehtoja erityisesti sellaisilla graafeilla, joiden järjestelyyn barysentrinen järjestely tai muut perinteiset heuristiikat eivät sovi.
Tuloksien perusteella miinustekniikka ja mukautuvuusanalyysi voivat olla varteenotettavia vaihtoehtoja erityisesti sellaisilla graafeilla, joiden järjestelyyn barysentrinen järjestely tai muut perinteiset heuristiikat eivät sovi.