Wnioski z paprotki

W poprzedniej notce „Pożyteczny chaos” wspomniałem o tym, że stosowanie niesymetrycznej, „oszukującej” kostki do gry może dawać bardzo dobre wyniki w generowaniu fraktali. W programie dołączonym do tamtej notki są dwie gry w chaos „Game III” (G3) i „Game IV” (G4), które mają wygenerować fraktala nazwanego paprotką Barnsley’a.

Ale każdy, kto ściągnął ten program może łatwo się przekonać, że oba fraktale znacznie się różnią jakością prezentacji.


Rys. 1	Rys. 2

Czym się wobec tego różnią? Rys. 1 wykonany jest zgodnie ze strategią „każdemu po równo”, czyli każda transformacja losowana jest z jednakowym prawdopodobieństwem. Natomiast rys. 2 wykonany jest zgodnie ze strategią „sprawiedliwie, nie znaczy równo”. Pierwsza strategia jest opisana i intuicyjnie zrozumiała. Natomiast co trzeba zrobić aby dobrać tak prawdopodobieństwa losowań poszczególnych transformacji aby fraktal generował się efektywnie? Bo jak łatwo się przekonać pomimo wielokrotnego naciskania na klawisz „100000” w G3 ciągle nie udaje się wygenerować tak pięknego fraktala jak za jednym naciśnięciem tego klawisza w G4.

Aby znaleźć rozwiązanie tego problemu będziemy rysowali go stosując do każdej z transformacji inny kolor.

Jak widać z rys. 3 transformacje brązowa, zielona i czerwona dają dość bardzo dobre rezultaty. Natomiast wyraźnie widać, że transformacja niebieska nie generuje w pełni swojej części. A skoro tak, to może zobaczmy jaki jest wkład poszczególnych transformacji w wynikową złożoną transformację. W tym celu policzmy wyznaczniki wszystkich transformacji.

Jak widać, transformacja brązowa ma wyznacznik równy zero. Jest to transformacja prowadzącą do odcinka. Aby dać tej transformacji szansę na realizację damy zastępczo tej transformacji wartość mniejszą od wszystkich pozostałych, na przykład 0.01.

Następnie policzmy sumę tych wyznaczników i policzmy ich wkład w całą transformację. Jest oczywiste, że suma tych wkładów da nam liczbę 1. Czyli? Czyli mamy prawdopodobieństwa wyboru poszczególnych transformacji. Wydaje się, że jest ona optymalna.

Po zastosowaniu wartości z kolumny „Udział w sumie” jako prawdopodobieństw wyboru transformacji już po naciśnięciu jednorazowym klawisza „100000” otrzymujemy piękną paprotkę Barnsley’a.

Nasz algorytm „sprawiedliwie, nie znaczy równo” dał nam piękny rezultat. Ale ktoś mógłby się obruszyć, że transformacja brązowa została „nagrodzona” niesłusznie. Należy jej zabrać te znikome 0.01 i zgodnie z prawdą nic jej nie dać. Ten wariant nazwiemy „nie dla bezproduktywnych”. Po uwzględnieniu tej strategii prawdopodobieństwa wyliczone według wkładów do sumy wyznaczników będą następujące: