Monte Carlo -algoritmi
Wikipedia
 |
Tämä artikkeli sisältää päällekkäistä tietoa artikkelin Monte Carlo -simulaatio kanssa, ja ne pitäisi yhdistää. |
Monte Carlo -algoritmia käytetään monien matemaattisten ongelmien ratkaisemiseen. Se tuottaa tuloksen, joka ei ole tarkka. Sitä käytettäessä virheen todennäköisyys voidaan kuitenkin asettaa halutulle tasolle, ja tarkkuuden kasvaessa kasvaa myös suoritusaika.
[muokkaa] Idea
Monte Carlo -algoritmia käytettäessa tehdään sarja satunnaisia arvauksia, jokainen näistä arvauksista eliminoi joukon mahdollisia ratkaisuja. Mitä kauemmin algoritmi pyörii, sitä varmemmin lopputulos on oikein, lisäksi tulos tarkentuu koko ajan.
Monte Carlon algoritmin ajatuksen voi kuvata seuraavalla vertauksella; On olemassa vaja, jonka seinään on liitetty tikkataulu. Tarkoituksenasi on saada sokea mies heittämään tikka tauluun. Monte Carlo -algoritmi ratkaisee tilanteen tavalla, jossa sokealle miehelle annetaan nopeasti sarjatulella tikkoja sinkoava ase, laitetaan tämä seisomaan siten, että hän osoittaa maalin suuntaan, ja samalla kun mies painaa liipasinta, liikutetaan tämän kättä edestakaisin. Mitä enemmän sokean miehen aseeseen syötetään tikkoja, sitä varmemmin osutaan tauluun -tai sitä parempi suurimman heiton tuloskin saadaan.
[muokkaa] Käyttö
Yksi yleisimmistä Monte Carlo -algoritmin käyttötavoista on nopea tarkistus sille, onko kokonaisluku N alkuluku.
Monte Carlon -algoritmia käyttäessä valitaan satunnaisesti kokonaislukuja väliltä 2 ja ½N, ja jos arvottu luku jakaa N:n niin että lopputulos on kokonaisluku, ei N ole alkuluku. Monte Carlon algoritmi antaa "melko varman" vastauksen ongelmaan erittäin nopeasti verrattuna muihin menetelmiin.
