Gravitaatiosimulaatiot
Authors
Date
2019Copyright
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Tässä tutkielmassa tarkastellaan gravitaatiosimulaatioita, simulaatioiden tehokkuutta ja algoritmeja, joilla simulaatioita voidaan nopeuttaa. Gravitaatiosimulaatioiden suurin ongelma on laskennallinen vaativuus. Suoraan N kappaleen välisiä vuorovaikutuksia laskemalla laskennallinen vaativuus on luokkaa O(N^2). On selvää, että tämä on ongelma suurilla kappalemäärillä. Erilaiset algoritmit, kuten Barnes-Hut puualgoritmi, voivat vähentää aikavaativuutta tuntuvasti. Parhaimmillaan voidaan saavuttaa nopealla moninapamenetelmällä aikavaativuus O(N). Simulaatioita voidaan lisäksi nopeuttaa hyödyntämällä rinnakkaislaskentaa. Tähän soveltuu esimerkiksi Barnes–Hut-algoritmi hyvin. In this paper we will look at gravitational simulations, effectiveness of simulations and algorithms that can be used to accelerate simulations. The biggest problem gravitational simulations have is algorithmic complexity. Calculating interactions directly has the algorithmic complexity of O(N^2). It is clear that this becomes a real problem with large numbers of particles in simulation. Different algorithms such as the Barnes-Hut tree algorithm can reduce algorithmic complexity a lot. At best algorithmic complexity of O(N) can be achieved with Fast Multipole Method. In addition, to achieve speed it is very important to make use of parallel computing. Barnes–Hut-algorithm is well suited for parallel computing.
Metadata
Show full item recordCollections
- Kandidaatintutkielmat [4764]
Related items
Showing items with similar title or keywords.
-
Reitinhakualgoritmien käyttö videopeleissä
Keränen, Emil (2018)Reitinhaku on sekä videopeleissä että tekoälyn ja robotiikan puolella hyvin tuttu ongelma. Sen tutkimiseen on käytetty viime vuosina paljon resursseja lisääntyneen tekoälykiinnostuksen vuoksi. Tässä tutkielmassa keskitytään ... -
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 ... -
Klusterointialgoritmien vertailu
Nättilä, Severi (2021)Tutkielmassa tutustutaan ryhmittelyn perusteisiin, todennäköisyysmallipohjaisen sekä ei-parametrisen datan klusterointiin ja menetelmiin. Klusterointimenetelmistä käydään läpi: EM-algoritmi, k-means, k-medoids, k-modes ja ... -
Simuloidun jäähdytyksen suppenemislause
Luoto, Antti (2013)Tämä pro gradu -tutkielma käsittelee simuloitu jäähdytys -nimisen kombinatorisen optimointimenetelmän teoriaa ja käytäntöä. Esimerkiksi kuvankäsittelyssä sovelletun algoritmin ideana on löytää annetulla joukolla määritellyn ...