Kauppamatkustajan ongelman approksimointialgoritmin suunnittelu, toteutus ja kokeellinen tutkimus
TUOMISTO, AARO (2007)
2007
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty 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ä
2007-05-09
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-16794
https://urn.fi/urn:nbn:fi:uta-1-16794
Tiivistelmä
Tässä tutkielmassa kuvataan uusien, tutkielmaa varten kehitettyjen, kauppamatkustajan ongelman approksimointialgoritmien rakennetta, toteutusta ja kokeellista tutkimusta. Lisäksi tutkielma luo katsauksen itse ongelman historiaan ja tutkimukseen. Uusia algoritmeja tutkitaan vertaamalla niitä jo olemassa olevaan konveksia verhoa hyödyntävään lisäysalgoritmiin. Testimateriaalina kokeellisessa tutkimuksessa on käytetty internetistä löytyviä pistesarjoja, jotka ovat yleisesti käytössä kauppamatkustajan ongelman tutkimuksessa.
Kokeellisen tutkimuksen tuloksena saatiin selville, että kehitettyjen algoritmien perusidea on toimiva ja että kehitetyt algoritmit ovat vertailukohtaansa nähden huomattavan nopeita. Lisäksi saatiin selville, että uusien algoritmien antama reitti ei ollut kovin paljon pidempi vertailukohtana käytetyn algoritmin antamaan reittiin verrattuna.
Avainsanat ja -sanonnat: kauppamatkustajan ongelma, approksimointialgoritmi, kokeellinen tutkimus.
Kokeellisen tutkimuksen tuloksena saatiin selville, että kehitettyjen algoritmien perusidea on toimiva ja että kehitetyt algoritmit ovat vertailukohtaansa nähden huomattavan nopeita. Lisäksi saatiin selville, että uusien algoritmien antama reitti ei ollut kovin paljon pidempi vertailukohtana käytetyn algoritmin antamaan reittiin verrattuna.
Avainsanat ja -sanonnat: kauppamatkustajan ongelma, approksimointialgoritmi, kokeellinen tutkimus.