Prírodou inšpirované algoritmy

Sandpile model

Sandpile simulácia (simulácia pieskovej hromady) pozostáva z grafu, určitého množstva piesku rozmiestneného v grafe a množiny pravidiel určujúcich správanie sa piesku pri jeho pridávaní (sypaní).

Graf

Tradičný sandpile model pozostáva z množiny bodov rozmiestnených v mriežke. Každý bod zdieľa svoju hranu s bodmi na východ, západ, sever a juh od neho. Teda body v rohoch majú dvoch susedov, body na okraji troch a všetky ostatné majú štyroch susedov. Každému bodu je pridelené číslo odpovedajúce počtu zrniek piesku v danej bunke.

Niektoré variácie tohto modelu:

• pridanie hrán v mriežke v dôsledku šírenia piesku
• zvýšenie počtu hrán bodov -> 8 susedov
• 3D modely

Časové ohraničenia

Čas v simulácii je diskrétny. Stav mriežky sa mení simultánne so zmenou obsahu každej bunky v súlade s transformačným pravidlom. Trasformačné pravidlo sa aplikuje, pokiaľ žiadna z buniek už nemôže zmeniť svoj stav.

Transformačné pravidlo

Pravidlo na zmenu stavu grafu závisí od množstva piesku v každom bode a na hodnote prah. Ak je množstvo piesku v bunke rovné alebo väčšie ako hodnota prah, dôjde k premiestneniu 1 zrnka ku každému zo susedov. Tento presun zrniek sa nazýva toppling. V tomto základnom modeli je prah=4. Bunky s menej ako štyroma susedmi piesok strácajú, znižuje sa tak množstvo piesku v systéme. Hovoríme, že systém je v stabilnom štádiu, ak žiaden bod nemá dostatok piesku k vykonaniu topplingu.

Interakcia susedov

Keďže je transformačné pravidlo aplikované na všetky bunky simultánne, dochádza u priľahlých buniek, ktoré vykonávajú toppling, ku interakcii. Keď dve priľahlé bunky vykonávajú toppling, vymieňajú si medzi sebou zrnká piesku. Teda množstvo piesku u týchto dvoch buniek sa nezníži o hodnotu prah, ale o hodnotu prah-1. Môže dôjsť k stavu, keď bunka vykonávajúca toppling prijme zrnká od všetkých jej susedov a tým pádom sa množstvo zrniek v tejto bunke nezníži.

Príklady simulácie

V tejto simulácii je hodnota prah=3. Jednotlivé farby odpovedajú nasledujúcemu počtu zrniek piesku:

• 0 - žltá farba
• 1 - modrá farba
• 2 - zelená farba
• 3 - červená farba

Piesok je pridávaný iba do stredu hromady.

Piesok je pridávaný náhodne.