| dc.date.accessioned |
2013-05-29T18:07:46Z |
und |
| dc.date.accessioned |
2017-10-24T12:24:36Z |
|
| dc.date.available |
2013-05-29T18:07:46Z |
und |
| dc.date.available |
2017-10-24T12:24:36Z |
|
| dc.date.issued |
2013-05-29T18:07:46Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/2740 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/2740 |
|
| dc.title |
Heuristinen etsintä ja tietorakenteet kauppamatkustajan ongelmassa |
fi |
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
| ethesis.department |
Institutionen för datavetenskap |
sv |
| ethesis.department |
Department of Computer Science |
en |
| ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Tanskanen, Tapio |
|
| dct.issued |
2013 |
|
| dct.language.ISO639-2 |
fin |
|
| dct.abstract |
Paikallinen etsintä on yksi tapa ratkaista optimointiongelmia likimääräisesti. Tässä tutkielmassa tarkastellaan kauppamatkustajan ongelman likimääräiseen ratkaisemiseen tarkoitettuja paikallisen etsinnän heuristiikkoja, sekä reitin esitykseen tarvittavia tietorakenteita. Reitti voidaan esittää listana, jonka on tuettava osajonojen eli segmenttien kääntämisiä. Listan esitykseen käytettävän tietorakenteen merkitys korostuu suurissa ongelmissa, sillä segmenttien kääntelyyn kuluva aika voi dominoida algoritmin muuta suoritusaikaa.
Tietorakenteen suunnittelu on tasapainoilua tietorakenteeseen kohdistuvien kyselyiden ja muokkausoperaatioiden välillä. Jommatkummat on mahdollista suorittaa hyvin nopeasti, eli vakioajassa, mutta molempia ei voida suorittaa vakioajassa yhdessä ja samassa tietorakenteessa. Kyselyiden nopeuttaminen hidastaa muokkausoperaatioiden suoritusta ja päinvastoin. Binääripuu on varsin luonnollinen listan esitystapa, jossa kyselyt ja segmentin kääntäminen voidaan suorittaa logaritmisessa ajassa. Se ei kuitenkaan ole käytännössä kilpailukykyinen parhaiden vaihtoehtoisten tietorakenteiden kanssa.
Segmenttipuu on aputietorakenne, joka ryvästää kyselyitä ja muokkausoperaatioita erillisiksi ryppäiksi. Helsgaunin etsintästrategialla on samankaltainen ryvästävä vaikutus. Kyselyiden ja muokkausoperaatioiden ryvästys mahdollistaa sen, että binääripuussa muokkausoperaatioiden välissä tapahtuvien kyselyiden hakupolkujen keskimääräisiä syvyyksiä voidaan aikaleiman avulla pienentää. Globaalin informaation laiska päivitys binääripuun sisäsolmuihin mahdollistaa sen, että kyselyissä tarvittavia globaaleja tietoja ei tarvitse kerätä puun juureen asti selaamalla. Selaus voidaan keskeyttää heti ensimmäiseen solmuun, jonka globaalit tiedot ovat aikaleiman perusteella ajan tasalla. Periaatetta on testattu binääripuun kaltaisella tietorakenteella, lohkopuulla, Helsgaunin LKH-2 -algoritmin yhteydessä noin 2000–86000 kaupungin kokoisilla ongelmilla. Suoritettujen testien perusteella lohkopuu vaikuttaisi olevan kilpailukykyinen tietorakenne sitä suuremmissa ongelmissa. |
fi |
| dct.language |
fi |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/fin |
|
| ethesis.language |
Finnish |
en |
| ethesis.language |
suomi |
fi |
| ethesis.language |
finska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| ethesis.degreeprogram |
Algorithms and Machine Learning |
en |
| dct.identifier.urn |
URN:NBN:fi-fe2017112251116 |
|
| dc.type.dcmitype |
Text |
|
