Verlet-luettelo (nimetty Loup Verletin mukaan) on molekyylidynamiikan simulaatioissa esiintyvä tietorakenne, jolla ylläpidetään tehokkaasti luetteloa kaikista hiukkasista tietyllä katkoetäisyydellä toisistaan.
tätä menetelmää voidaan helposti soveltaa Monte Carlon simulaatioihin. Lyhyen kantaman vuorovaikutuksissa käytetään tyypillisesti katkaisusädettä, jonka yli hiukkasten vuorovaikutukset katsotaan ”riittävän lähelle” nollaa, jotta ne voidaan turvallisesti sivuuttaa. Jokaiselle hiukkaselle rakennetaan Verlet-lista, joka luettelee kaikki muut potentiaalisen katkaisuetäisyyden sisällä olevat hiukkaset sekä jonkin verran ylimääräistä etäisyyttä, jotta luetteloa voidaan käyttää useisiin peräkkäisiin Monte Carlon ”pyyhkäisyihin” (joukko Monte Carlon askelia tai siirtoja) ennen kuin se päivitetään. Jos haluamme käyttää samaa Verlet-luetteloa n {\displaystyle N} kertaa ennen päivitystä, niin katkaisuetäisyyden Verlet-luetteloon sisällyttämiseksi tulisi olla R C + 2 n d {\displaystyle R_{C}+2nd}
, missä r c {\displaystyle R_{C}}
on katkaisuetäisyys potentiaali, ja D {\displaystyle d}
on yksittäisen hiukkasen suurin Monte Carlo-vaihe (siirto). Täten käytämme kertalukua n 2 {\displaystyle N^{2}}
aikaa Verlet-luetteloiden laskemiseen ( n {\displaystyle N}
on hiukkasten kokonaismäärä), mutta saamme palkinnoksi n {\displaystyle N}
Monte Carlon ”pyyhkäisyt” kertalukua n n 2 {\displaystyle nn^{2}}
sijasta N n {\displaystyle nn}
. Optimoimalla valintamme n {\displaystyle N}
voidaan osoittaa, että Verlet-luetteloiden avulla voidaan muuntaa o(n 2 ) {\displaystyle O (N^{2})}
Monte Carlon pyyhkäisyjen ongelma O (N 5 / 3) {\displaystyle O(N^{5/3})}
ongelma.
käyttämällä soluluetteloita lähimpien naapureiden tunnistamiseksi o(n) {\displaystyle O(n)} vähentää laskennallisia kustannuksia entisestään.