Lyhyimpien reittien etsiminen muuttuvassa graafissa
Tekijät
Päivämäärä
2020Pääsyrajoitukset
Tekijä ei ole antanut lupaa avoimeen julkaisuun, joten aineisto on luettavissa vain Jyväskylän yliopiston kirjaston arkistotyösemalta. Ks. https://kirjasto.jyu.fi/fi/tyoskentelytilat/laitteet-ja-tilat..
Tekijänoikeudet
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Tämän tutkimuksen tarkoitus on selvittää, miten kannattaa käytännössä etsiä lyhyimpiä reittejä suuntaamattomassa graafissa, joka muuttuu vähitellen etsintöjen väleissä. Tutkielman konteksti on luoda todentuntuisia, suunnittelemattomalta vaikuttavia katuverkkoja graafin mallintamaan ympäristöön. Katuverkko helpottaa olennaisesti kulkua paikoista toisiin ja se muodostuu vähitellen, joten graafin muuttuminen on tarkemmin ainoastaan kaarten pituuksien pienenemistä. Käsiteltäviä algoritmeja lyhyimmän reitin etsimiseen ovat Dijkstra, sen laajennokset ja ainakin teoriassa kilpailukykyinen niin kutsuttu PR-algoritmi. This thesis surveys how to practically implement repetitive shortest path seeking in an undirected graph which changes incrementally between the seekings. The context of the thesis is to create apparently truthful and unplanned city street networks in an environment modeled by the graph. More closely, since streets ease the paths following them, change of the graph is only shortening of its edges. The algorithms surveyed are Dijkstra's algorithm, its extensions and the so-called PR algorithm which is at least theoretically competitive.
Asiasanat
Metadata
Näytä kaikki kuvailutiedotKokoelmat
- Kandidaatintutkielmat [4988]
Samankaltainen aineisto
Näytetään aineistoja, joilla on samankaltainen nimeke tai asiasanat.
-
Reitinhakualgoritmien vertailu videopeliympäristöissä
Pollari, Joonas (2020)Reitinhaku on prosessi, jossa etsitään reittiä maaliin erilaisissa ympäristöissä. Tässsä tutkielmassa vertaillaan keskenään erilaisia reitinhakualgoritmeja, ja arvioidaan niiden käytettävyyttä videopeliympäristöissä. ... -
Agenttien liikkuminen peleissä
Parviainen, Jussi (2019)Tutkielma käsittelee agenttien liikkumista tietokonepeleissä. Tyypillinen liikkumisen toteuttaminen tapahtuu hyödyntäen reittipisteitä sekä A*-algoritmia, mutta menettelystä syntyy ongelmia erityisesti usean agentin ... -
Suurten graafien visualisointi
Muhonen, Joonas (2020)Graafit ovat yleisesti tietotekniikassa esiintyvä tietorakenne joita voidaan käyttää visualisoimaan useita reaalimaailman ilmiöitä kuten tietoverkkoja ja riippuvuussuhteitaohjelmiston moduulien välillä. Graafin koon kasvaessa ... -
Improving identification algorithms in causal inference
Tikka, Santtu (University of Jyväskylä, 2018)Causal models provide a formal approach to the study of causality. One of the most useful features of causal modeling is that it enables one to make causal claims about a phenomenon using observational data alone under ... -
The spanning tree based approach for solving the shortest path problem in social graphs
Eremeev, Andrei (2016)This thesis is devoted to the shortest path problem in social graphs. Social graphs represent individuals and social relationships between them. As for social networking sites, their users are represented as vertices of ...
Ellei toisin mainittu, julkisesti saatavilla olevia JYX-metatietoja (poislukien tiivistelmät) saa vapaasti uudelleenkäyttää CC0-lisenssillä.