Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Koneoppimisen soveltaminen graafihakualgoritmien ohjaamisessa

Luukka, Joel (2017)

 
Avaa tiedosto
1513599675.pdf (2.850Mt)
Lataukset: 



Luukka, Joel
2017

Tietojenkäsittelytieteiden tutkinto-ohjelma - Degree Programme in Computer Sciences
Luonnontieteiden tiedekunta - Faculty of Natural 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ä
2017-12-11
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201712182945
Tiivistelmä
Graafirakenteita käytetään monissa eri sovelluksissa kuvaamaan niiden toimintaympäristöjen lainalaisuuksia. Graafien laajan sovelluskentän vuoksi graafihakualgoritmit ovat keskeisessä roolissa sovellusten toteutuksessa. Graafihakuongelmaan on kehitetty erittäin hyvin toimivia algoritmeja, mutta tietoaineistojen kasvaminen ja sovelluskohteiden monimutkaistuminen asettavat yhä korkeampia tehokkuusvaatimuksia graafihakualgoritmeille.

Graafihakumenetelmät ovat karkeasti jaettavissa kahteen joukkoon: heikkoihin hakumenetelmiin, jotka ovat suoritettavissa missä tahansa graafissa, ja heuristisiin hakumenetelmiin, jotka käyttävät sovellus-, hakutehtävä- ja graafikohtaista tietoa tehostaakseen hakua. Heikot hakumenetelmät ovat toimintavarmoja, mutta suorittavat paljon ylimääräisiä toimenpiteitä haun aikana, mikä tuottaa tehottomuutta. Heuristiset hakumenetelmät pystyvät välttämään osan ylimääräisistä vaiheista, mutta heuristisia hakuja on mahdollista räätälöidä vain rajattuun määrään sovelluskohteita.

Tässä tutkielmassa esittelen uuden koneoppimista käyttävän graafihakumenetelmän, jonka oppimistehtävänä on tuottaa malli, joka ohjaa hakua heurististen hakumenetelmien tapaan. Menetelmän oppiva osa perustuu vahvistusoppimiseen, jonka avulla voidaan purkaa tehokkaiden hakumenetelmien asettamia vaatimuksia graafien kuvaukseen ja laajentaa siten näiden hakumenetelmien sovelluskenttää.

Oppivan haun toimintaa mitattiin kahdessa kokeessa. Ensimmäisessä kokeessa oppivaa hakua verrattiin tehokkaaseen heuristiseen hakumenetelmään sille soveltuvissa hakutehtävissä. Toisessa kokeessa oppivan haun toimintaa tutkittiin heuristisille hauille sopimattomassa hakutehtävässä, jossa oppivan haun vertailukohtana käytettiin yksinkertaista leveyshakua.

Kokeiden tulosten perusteella oppivaa hakua voidaan pitää hyvänä keinona toteuttaa tehokkaampia hakumenetelmiä sovelluskohteissa, joissa heuristista hakua ei ole mahdollista käyttää. Tutkielmassa esitetty oppiva haku vaatii kuitenkin suuren muistimäärän sisäisen mallinsa ylläpitämiseen, mikä on otettava huomioon oppivan haun soveltamisessa ja jatkokehityksessä.
Kokoelmat
  • Opinnäytteet - ylempi korkeakoulututkinto [36421]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste