Gra w chaos

algorytm komputerowy

Gra w chaosalgorytm komputerowego generowania obrazów pewnych fraktali. Generuje on przybliżony obraz atraktora lub punktu stałego dowolnego systemu funkcji iterowanych.

Liść paproci wygenerowany za pomocą gry w chaos

AlgorytmEdytuj

Zaczynając od pewnego punktu   kolejne iteracje są dane przy pomocy wzoru   gdzie   jest jedną z funkcji iterowanych wybieraną niezależnie i losowo dla każdej iteracji. Iteracje zbiegają się do punktu stałego systemu funkcji iterowanych. Jeżeli wartość początkowa   należy do atraktora systemu funkcji iterowanych, wówczas wszystkie punkty   również należą do tego atraktora i z prawdopodobieństwem 1 tworzą w nim zbiór gęsty. Prawdziwy jest znacznie ogólniejszy rezultat.

Twierdzenie o grze w chaos (zob.[1]): Niech   będzie przestrzenią metryczną zupełną, zaś   iterowanym układem funkcyjnym (IFS) złożonym z przekształceń zwężających   Niech   będzie orbitą startującą w dowolnym punkcie   Wówczas atraktor   układu   (który istnieje w myśl twierdzenia Hutchinsona) odtwarzany jest przez zbiór punktów skupienia   orbity  

  • (wersja probabilistyczna)   z prawdopodobieństwem 1, jeśli tylko ciąg   sterujący wyborem funkcji w n-tym kroku iteracji, jest losowany z użyciem schematu Bernoulliego na zbiorze  
  • (wersja zderandomizowana)   jeśli tylko ciąg   jest dyzjunktywny nad alfabetem   tzn. dowolny łańcuch skończony nad   pojawia się w  

W przypadku układów kontrakcji wariant probabilistyczny twierdzenia o grze w chaos (używający schematu Bernoulliego) wynika z wariantu dyzjunktywnego. Dzieje się tak, gdyż schemat Bernoulliego generuje ciągi dyzjunktywne prawie na pewno.

Przykład dla trójkąta SierpińskiegoEdytuj

 
Trójkąt Sierpińskiego

Na początku stawia się na płaszczyźnie 3 dowolne punkty (powinny być niewspółliniowe, gdyż inaczej fraktal zdegeneruje się do odcinka), po czym wybiera sobie kolejny punkt płaszczyzny, zwany punktem gry (game point). Następnie wybiera się dowolny z trzech punktów obranych na samym początku (można je oznaczyć 1, 2 i 3, po czym korzystając z generatora liczb losowych, wybierać je) i stawia punkt w połowie odległości między czwartym punktem a tym wybranym. Powtarza się ten krok, za każdym razem oznaczając punkt leżący dokładnie w połowie odległości między ostatnio postawionym a jednym z trzech pierwszych.

Efektem algorytmu – zakładając, że punkty były losowane z mniej więcej takim samym prawdopodobieństwem – jest pewien wariant trójkąta Sierpińskiego. Jego wierzchołkami są trzy punkty wybrane na samym początku gry.

Zobacz teżEdytuj

PrzypisyEdytuj

  1. Michael Barnsley, Andrew Vince, Developments in fractal geometry, „Bulletin of Mathematical Sciences”, 3 (2), 2013, s. 299–348, DOI10.1007/s13373-013-0041-3, ISSN 1664-3607 [dostęp 2020-03-25] (ang.).