Błądzenie Losowe 5g3h4p

Sztuczne życie – Błądzenie losowe

Mieczysław Szyszkowicz

Smashwords Edition

Copyright 2014 by Mieczysław Szyszkowicz

Smashwords Edition, License Notes

This eBook is licensed for your personal enjoyment only. This eBook may not be re-sold or given away to other people. If you would like to share this book with another person, please purchase an additional copy for each recipient. If you’re reading this book and did not purchase it, or it was not purchased for your use only, then please return to Smashwords.com and purchase your own copy. Thank you for respecting the hard work of this author.

Table of Contents Rozdział 1

*Wstęp*

Rozdział 2

* Błądzenie losowe w ośmiu kierunkach *

Rozdział 3

* Błądzenie losowe w trzech wymiarach*

Rozdział 4

* Błądzenie losowe w czterech kierunkach *

Rozdział 5

* Błądzenie losowe w trzech kierunkach *

Rozdział 6

* Kierunki oraz ścieżki *

Rozdział 7

* Błądzenie losowe na ścieżkach *

Rozdział 8

* Błądzenie losowe z trzema kierunkami*

Rozdział 9

* Błądzenia losowe na ścieżce w 3 wymiarach *

Rozdział 10

* Monte Carlo i liczba pi *

Rozdział 1

*Wstęp*

# Wprowadzenie # Książka ta należy do pierwszej pozycji w serii „Sztuczne życie” i jest właśnie o tym sztucznym życiu. Jednak nie aż tak do końca. Raczej jest ona o pewnych przejawach cech życia, które dają się realizować na ekranie komputera. Tutaj jest to głównie ruch niby żywej istoty. Często też daje się zaobserwować rodzaj organizacji czy współpracy pomiędzy takimi sztucznymi obiektami. Punkt jest zastosowany do reprezentacji jednego sztucznego żyjątka. Punkt taki porusza się i znaczy swoją drogę na ekranie komputera. Punkt jest automatem komórkowym i, albo porusza się swobodnie, albo czyta zapis znaków i porusza się na ich podstawie. Tutaj punkt nie czyta żadnych znaków, tylko utrwala swoją aktualną pozycję. Różnego rodzaju procesy są tu użyte do realizowania tego ruchu. Cechy ogólne charakteryzujące te procesy są następujące: ruchy swobodne i pozbawione pamięci, ruchy używające częściowo pamięć, ruchy w dowolnym kierunku, ograniczone ruchy bazujące na zadanych regułach. Brak pamięci to kompletna niezależność od poprzedniego ruchu. Takie właśnie procesy są w tej części opisane. Do błądzenia losowego możemy dodać odrobinę pamięci. Chociażby taki przykład: w następnym kroku swego ruchu punkt nie może pójść w kierunku, który właśnie użyl. Podobnie możemy zadać sekwencję kierunków i ustalić regułę ich wyboru dla punktu w kolejnym kroku. Mamy więc trochę pamięci, jednak dalej są to procesy losowe. Decyzje co do następnego kierunku są tu podejmowane z pewnym prawdopodobieństwem. W pozostałych dwóch pozycjach książkowych z serii „Sztuczne życie” są opisane obiekty, które poruszają się same. Czytają zapis stanów pikseli ekranu i na tej podstawię wykonują ruchy. Jest to taka poruszająca się swobodnie głowica, co czyta i pisze. Obiekty tego typu realizujemy za pomocą programów. Nie trzeba ich zatem fizycznie budować. Wystarczy krótki kod komputerowy, aby stworzyć sztuczne życie. Przynajmniej namiastkę życia. Zamieszczone programy w Javie winne być trzymane w plikach o tych samych nazwach, jakie są podane w pierwszej linii komentarza. Program w Javie jest

realizowany w dwóch krokach; kompilacja, a następnie wykonanie. Zatem komenda> javac program-nazwa.java (powoduje kompilowanie programu) oraz komenda> java program-nazwa (powoduje wykonanie programu).

# Błądzenie losowe # W roku 1827 botanik szkocki Robert Brown badał pod mikroskopem ruchy pyłku kwiatowego zanurzonego w wodzie. W swoich doświadczeniach Brown próbował różnych cząstek wziętych z zasuszonych roślin. Wszystkie one poruszały się w wodzie. Podejrzewał zatem, iż są one żywe, bo się ruszają. Zaczął więc eksperymentować z cząstkami, które na pewno nie były fragmentami czegoś, co kiedykolwiek żyło. Badał więc pył uzyskany po rozkruszeniu kamienia. Podobno stosował nawet pył ze Sfinksa z Egiptu. To stąd zapewne Sfinks może mieć ubytek nosa. Ku jego zdumieniu, wszystkie badane w wodzie cząstki wykonywały ruchy. Ruch ten, obecnie nazywany ruchem Browna, jest spowodowany losowym przemieszczaniem się molekuł samej wody. Zderzają się one z pyłkiem i wprawiają go w ruch. Zachowanie się malutkich cząstek pyłku w wodzie nie ma nic wspólnego z życiem. Przejawiają one jednak jedną z istotnych afirmacji życia. Jest nim ruch. Brown myślał, że cząstki żyją. Ruchy Browna mogą być postrzegane, jako pierwsze eksperymenty ze sztucznym życiem. Ruchy Browna były badane dalej przez Einsteina, Smołuchowskiego, Wienera, Levy’ego, Mandelbrota oraz wielu innych fizyków oraz matematyków. Ruchy te są ciągle obiektem istotnych dociekań naukowych. W matematyce, w rachunku prawdopodobieństwa intensywnie bada się wiele procesów losowych modelowanych właśnie ruchami Browna. Jest to do tej pory żywa i kwitnąca gałąź matematyki. Ekran komputera pozwala wykonywać modele różnych ruchów Browna. Ruchy te są symulowane poprzez błądzenie losowe. Wielorakie podejścia do tego zagadnienia są przedstawione w tej książce. Chociażby taki przykład: w modelu pokazanym poniżej zestaw kierunków jest wybierany cyklicznie w kolejności 1, 2 oraz 3. Natomiast kierunek 3 jest z kolei wybierany losowo wśród kierunków zaznaczonych przerywaną strzałką.

Celem urozmaicenia tematyki dodatkowo na końcu książki przedstawiona jest metoda Monte Carlo otrzymywanie przybliżenia dla liczy pi. Tak, tej właśnie liczby pi=3.141592… .

Rozdział 2

* Błądzenie losowe w ośmiu kierunkach *

Błądzenie losowe punktu jest realizowane na ekranie komputera. Dla zadanej początkowej pozycji punktu, wskazanej na białym ekranie jako czarny piksel, następne położenie tego punktu (mamy tu na myśli aktualnie rozpatrywany punkt) jest wybrane losowo. Wyboru dokonujemy pośród ośmiu możliwych miejsc w najbliższym sąsiedztwie aktualnego punktu. Każda pozycja ma taką samą szansę zostać wylosowaną. Po wyborze nowej pozycji, odpowiadający jej piksel zmienia swój kolor na czarny. Proces ten powtarzamy wiele razy. Przez takie postępowanie zaznaczona jest droga, jaką przebywa w ten sposób punkt. Obserwując monitor komputera dostajemy wrażenie ruchu punktu na płaszczyźnie ekranu. Rozpatrywany tu system nie posiada żadnej pamięci. Nie używamy informacji o poprzednich stanach pikseli. Również nie korzystamy tu z informacji o wcześniej wybranych kierunkach. Decyzja w bieżącym kroku podejmowana jest niezależnie od poprzednich kroków. O nowej pozycji punktu decyduje czysty przypadek. Punkt po prostu błądzi. Im bardziej jest to ruch przypadkowy tym lepiej. Chcemy mieć ruch zupełnie losowy. Dlatego mówimy o błądzeniu losowym. Rysunek dany poniżej obrazuje początek rozważanego tu procesu błądzenia.

Rys. 1. Pozycja wyjściowa do błądzenia losowego. Duże X pokazuje następny wybrany punkt. W każdym kroku tego procesu tworzone są dwie liczby losowe o trzech możliwych wartościach: –1, 0 oraz 1. Jedna liczba określa zmianę w kierunku poziomym, zaś druga w kierunku pionowym. Przyjmijmy odpowiednio oznaczenia: x na ruch w poziomie oraz y na ruch w pionie. Zatem przyrosty dla x oraz y, inaczej delty dx oraz dy, mogą mieć następujące wartości dx={-1,0,1} oraz dy={-1,0,1}. Dla sytuacji pokazanej na powyższym rysunku mamy wylosowane wartości dx=1 i dy=-1. Na ekranie komputera przyrost na osi y jest zrealizowany w przeciwnym kierunku, niż w klasycznym układzie kartezjańskim. Stąd mamy tu dy=-1, a nie dy=1. Jak się lepiej przyjrzeć, to praktycznie istnieje 9 kierunków do wyboru. Jednak jeden z nich jest trywialny, kiedy wypadnie dx=dy=0. Dalej zamieszczony jest obrazek z błądzenia losowego. Również podany jest jego sprawca. Stosunkowo prosty program, który tę grafikę zrealizował.

Rys. 2. Ślad zostawiony przez punkt błądzący po ekranie. Proces błądzenia losowego został wykonany przez program opracowany w języku Java. Program ten jest zawarty w pliku walk.java. Wystarczy go uruchomić, aby dostać obrazek z błądzenia. Program nie przechowuje (nie zapamiętuje) żadnych wartości, tylko wyświetla na ekranie pozycje położenia punktu. Obraz ekranu możemy schować do pliku i tak mamy obrazek, który utrwalił kolejne kroki.

walk.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class walk extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int m = d.width; int n = d.height; int maxit = 100000; int i = (int)(Math.random() * m); int j = (int)(Math.random() * n); g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(i,j,1,1);

i = (i + (int)(Math.random() * 3.0) - 1 + m) % m; j = (j + (int)(Math.random() * 3.0) - 1 + n) % n; } } } public class walk extends Frame { public static void main (String [] args) {new walk();} walk(){ super(“Chodzenie w 8 kierunkach”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”, new walk()); show(); } }

Rozdział 3

* Błądzenie losowe w trzech wymiarach*

Błądzenie losowe daje się zrealizować w przestrzeni trójwymiarowe (3D)j. Również jest to możliwe dla przestrzeni wielowymiarowej o wyższym (i dowolnym) wymiarze. Problem jednak jest, jak pokazać zachowanie się punktu, którego położenie opisuje kilka liczb. Ekran komputera jest dwuwymiarowy (2D). Używamy na nim tylko dwóch współrzędnych. Dwie liczby określają położenie punktu. Z wymiarem rośnie liczba współrzędnych punktu. Dla uproszczenia sytuacji, zajmiemy się tu trzema wymiarami (3D). Jedną z możliwości jest pokazanie na ekranie plasterków. Plasterek powstaje po ustaleniu wartości jednej z trzech zmiennych; x, y lub z. Powiedzmy, tworzymy plasterki po z, wtedy punkty są pokazane na płaszczyźnie x-y dla przyjętego i ustalonego z; z=0, z=1, z=2, ... , z=maksimum z. Dla każdego plasterka mamy plasterek nad nim oraz plasterek pod nim. Punkty są reprezentowane przez x, y oraz z. Delty mają wartości dx=<-1,0,1>, dy=<-1,0,1> oraz dz=<-1,0,1>. Dla dz=0, punkt zostaje w bieżącym plasterku. Natomiast dla dz=-1, punkt przechodzi do plasterka poniżej, zaś dla dz=1, do plasterka leżącego powyżej bieżącego. W obu przypadkach jeden z 9 punktów może być wybrany. Mamy 9 (dla x) +9 (dla y) +9 (dla z) możliwych pozycji w każdym kroku, przy czym jedna jest trywialna, kiedy punkt po prostu się nie przesunie.

Rys. 1. Schemat działania plasterków dla trzech wartości z. Na poniższym rysunku trzy plasterki są położone obok siebie. Ten plasterek z lewej, jest ulokowanym na samym spodzie. Obrazy na plasterkach są prawie identyczne. Dzieje się to tak dlatego, że zmienna z ma bardzo ograniczone wartości, tylko z = 0, 1, 2. Poruszający się punkt gości zatem często na każdym z trzech plasterków. Skrajne plasterki są zlepione: punkt z dołu jak musi zejść jeszcze niżej, to ląduje na górze oraz odwrotnie. Następuje to wtedy, gdy z wyższego (niższego) plasterka trzeba pójść wyżej (niżej).

Rys. 2. Ślad błądzenia w trzech wymiarach. Program, który realizuje ten rodzaj błądzenia losowego jest przedstawiony poniżej. Można się pokusić opracować jego wersję dla większej ilości wartości na osi z. Wtedy oczywiście trzeba zrobić odpowiednio więcej plasterków.

// walk3d.java // Autor M.Szyszkowicz, MMIV

import java.awt.*; import java.awt.event.*; class walk3d extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int k = 3; // wymiar na osi z int m = d.width / k; int n = d.height; int maxit = 100000; int x = (int)(Math.random() * m); int y = (int)(Math.random() * n); int z = (int)(Math.random() * k); g.setColor(Color.black);

for (int iter=0; iter<maxit; iter++){ g.fillRect(z * m + x,y,1,1); x = (x + (int)(Math.random() * 3.0) - 1 + m) % m; y = (y + (int)(Math.random() * 3.0) - 1 + n) % n; z = (z + (int)(Math.random() * 3.0) - 1 + k) % k; } } } public class walk3d extends Frame { public static void main (String [] args) {new walk3d();} walk3d(){ super(“Chodzenie w 9+9+9 kierunkach w 3W”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”, new walk3d()); show(); } }

Rozdział 4

* Błądzenie losowe w czterech kierunkach *

Wprowadzamy odrobinę ograniczenia na błądzenie losowe. Odbywać się ono teraz będzie tylko po z góry zadanej konfiguracji kierunków. Obecnie błądzenie losowe jest realizowane poprzez losowy wybór między dostępnymi kierunkami. Kierunek daje się opisać deltami. Wartości delt są wybierane losowo. Dla przykładu, w kierunku poziomym x mamy dx=<-1,0,1>. Oznacza to, że możemy pójść w lewo (-1), zostać (0) lub zrobić jeden krok w prawo (1). Do określenia kierunku na płaszczyźnie potrzebujemy dwie delty; dx oraz dy. Do kreowania tylko czterech, wybranych kierunków, powiedzmy NESW (litery na kierunki świata), realizowany algorytm powinien zastosować ograniczenie na wartości (dx, dy). W tym wypadku dopuszczalnymi zestawami są tylko pary liczb: N(0,-1), E(1,0), S(0,1), W(-1,0). Innym podejściem jest zapamiętanie wszystkich możliwych kierunków dla przyjętego modelu. W takiej sytuacji generator liczb losowych jest użyty do określenia indeksu. Wybrany indeks podaje numer kierunku na wcześniej zrobionej liście z ich wykazem. Na tej podstawie wybiera się aktualny kierunek. Zatem użyty generator winien dawać liczby 1, 2, 3, 4, jeśli mówimy tylko o czterech kierunkach.

Rys. 1. Zestaw dwóch istotnie różnych układów kierunków. Kierunki są te same. Istnieje istotna różnica między konfiguracją kierunków ustawionych w krzyż, a tymi zestawionymi w kwadrat. Mamy takie ułożenie kierunków, jak to widać na ilustracji powyżej. Konfiguracja kwadratu ma kierunki uporządkowane. Po kierunku do góry (N) ze wskaźnikiem 1, następuje kierunek w prawo (E) z indeksem 2, potem kierunek w dół (S) z indeksem 3. W końcu jest kierunek w lewo (W) identyfikowany przez 4. Mamy zadany obieg i to nawet zgodny z ruchem wskazówek zegara. W krzyżu nie ma zadanego takiego porządku. Każdy kierunek w nim zawarty, może być wybrany w dowolnej kolejności. Błądzenie losowe oparte na kwadracie ma już odrobinę pamięci. Rozważmy jeden z takich przypadków, kiedy tylko sąsiednie kierunki są dostępne. Tak więc po ruchu w pionie do góry może tylko nastąpić ruch znów w pionie do góry (ten sam jak poprzednio), w lewo lub w prawo. W tym wypadku ruch w pionie w dół nie jest dostępny. Kierunek ten jest za daleko od pionowego do góry. W tym sensie, że najpierw trzeba przejść przez kierunek pośredni. Kierunek ten będzie dostępny po jednym z ruchów w bok.

Rys. 2. Ślad błądzenia losowego po systemie kierunków ułożonych w kwadrat. Zamieszczony dalej program ma wbudowaną strukturę kierunków ułożoną w kwadrat. Droga jest zamknięta. Suma wartości dla przyrostów w kierunku poziomym (x) oraz w kierunku pionowym (y) jest zero. Program wybiera jeden z czterech kierunków. Łatwo jest zmodyfikować program tak, aby wybrał tylko kierunek aktualny lub jeden z dwóch sąsiednich. Dodajemy zatem ograniczenia, a przez to rodzaj prostej pamięci do systemu.

// walk4.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class walk4 extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int m = d.width; int n = d.height; int [] dx = {0,1,0,-1}; int [] dy = {-1,0,1,0}; int maxit = 100000; int i = (int)(Math.random() * m); int j = (int)(Math.random() * n);

int dir, maxdir = 4; g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(i,j,1,1); dir = (int) (Math.random ()* maxdir); i = (i + dx[dir] + m) % m; j = (j + dy[dir] + n) % n; } } } public class walk4 extends Frame { public static void main (String [] args) {new walk4();} walk4(){ super(“Chodzenie w 4 kierunkach”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”,new walk4()); show(); } }

Rozdział 5

* Błądzenie losowe w trzech kierunkach *

Błądzenie losowe na płaszczyźnie jest możliwe do wykonania w trzech kierunkach. Tylko niektóre zestawy kierunków nadają się do tego celu. Dla pewnych kompletów kierunków, punkt przesuwa się głównie w poziomie lub pionie, tzn. rysuje on linię zygzakowatą w kierunku osi x bądź y. Dla przykładu, na rysunku w podanym niżej zestawie, ten zestaw z lewej strony nie jest najlepszy. Dwa kierunki skośnie idące w dół dominują ruch błądzącego punktu i powodują jego posuwanie się zdecydowanie w kierunku osi y. Układ trzech kierunków po prawej stronie jest bardziej wyważony. Pozwala to wykonać z nimi błądzenie na płaszczyźnie. Poruszający się punkt nie ma teraz tendencji przemieszczania się tylko w jedną stronę.

Rys. 1. Dwa różne zestawy kierunków. Przy zestawie z lewej strony - punkt zdecydowanie idzie w dół. Dla zestawu z prawej strony - punkt w miarę jednakowo porusza się we wszystkie strony. Poprzez symetrię mamy cztery takie kombinacje trzech kierunków, które pozwalają błądzić po płaszczyźnie. Dobrym ćwiczeniem jest je określić oraz opracować z nimi program. Inne podejście do realizacji błądzenia, to wyważenie dominujących kierunków poprzez dobranie długości kroku, tj. użycie wartości delt 2, 3 lub większych w kierunkach zdominowanych. Na rysunku powyżej kierunek do góry (N) jest przeważony przez dwa kierunki idące skosem w dół. Zatem ten kierunek może być faworyzowany przez większe przyrosty, powiedzmy zamiast 1 użyjemy 2 lub 3. Ogólnie, staramy się realizować takie błądzenia, aby każdy punkt obszaru (ekranu) mógł być odwiedzony przez wędrujący punkt. Chcemy to zapewnić przynajmniej teoretycznie. Zatem unikamy tu procesów, kiedy punkt porusza się tendencyjne w jedna stronę, a przez to nie ma żadnych szans, aby on powrócił kiedykolwiek w okolice swojego startu.

Rys. 2. Obrazek błądzenia losowego punktu utworzony przez program. Program w Javie walk3.java radzi sobie z ruchem na płaszczyźnie używając tylko trzech kierunków. Zastosowano zestaw trzech kierunków, który daje wyważony ruch. Użyty jest zestaw z prawej strony na Rys. 1. W którym miejscu i jak jest to zdane w programie? Czy taki punkt ma jakieś szanse powrócić w swoje rodzinne strony, czyli do miejsca skąd wyszedł?

// walk3.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class walk3 extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int m = d.width; int n = d.height; int [] dx = {0,-1,1}; int [] dy = {1,-1,0}; int maxit = 100000; int i = (int)(Math.random() * m); int j = (int)(Math.random() * n); int dir, maxdir = 3;

g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(i,j,1,1); dir = (int) (Math.random ()* maxdir); i = (i + dx[dir] + m) % m; j = (j + dy[dir] + n) % n; } } } public class walk3 extends Frame { public static void main (String [] args) {new walk3();} walk3(){ super(“Chodzenie w trzech kierunkach”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); walk3 p3 = new walk3(); add(p3); show(); } }

Rozdział 6

* Kierunki oraz ścieżki *

Błądzenie losowe używa kierunków. W każdym kroku w sposób losowy jest wybierany jeden z dostępnych kierunków. Punkt przemieszcza się z aktualnej pozycji na nową, określoną przez losowo wybrany kierunek. Kierunki mogą występować w ściśle określonym porządku. W takim wypadku mamy do czynienia ze ścieżką. Dla zbioru n kierunków mamy n! (n silnia) możliwych ścieżek złożonych z tych komponentów. Inaczej postawiony ten problem to: na ile sposobów można ustawić n strzałek (wektorów)? Zatem dla n=3, istnieje dokładnie 6 (3!) ścieżek ułożonych z trzech kierunków. Kierunki można też określić, jako odcinki lub wektory. Zatem z takich wektorów (kierunków) układamy sobie ścieżki. Rozpatrujemy przykład, aby zilustrować jak budujemy ścieżki. Tutaj mamy trzy z góry zadane kierunki. Są one takie, jak jest to widoczne na obrazku.

Rys. 1. Układ trzech kierunków. W tym przypadku możemy zatem zbudować 3! = 6 ścieżek. Wszystkie w prosty sposób można opisać. Która z nich ma następujący opis: dx=<1,1,0>; dy= <1,1,-1>? Która zaś dx=<0,1,-1>; dy=<-1,1,1>? Opis jest przydatny do umieszczenia go w kodzie programu. Zadanie znalezienia opisu jest stosunkowo łatwe. Dla treningu warto opisać wszystkie poniższe ścieżki. Jak widać i z teorii, jest ich dokładnie 6.

Rys. 2. Zestaw wszystkich możliwych ścieżek utworzonych na bazie kierunków pokazany na Rys. 1. Układy są ciekawe i jednocześnie symetryczne. Zapewne jest to rodzaj niespodzianki. Z tak prostego układu wychodzi aż tyle bardziej złożonych systemów. Teraz zadane są trzy inne kierunki. Wydają się one być bardzo podobne do rozpatrywanych powyżej (Rys. 1). Jednak jak się przekonamy dają one zupełnie inne ścieżki. Nawet na pierwszy rzut oka jest ich jakby ciut za mało, od tego ile to przewiduje teoria.

Rys. 3. Zestaw trzech kierunków. Podobnie jak poprzednio mamy 6 ścieżek możliwych do zbudowania na tym zestawie. Widzimy tylko dwie różne ścieżki. Niektóre z nich po prostu pokrywają się ze sobą. Znów podobne pytanie jak powyżej. Która ścieżka jest opisana następującymi deltami: dx=<0,1,-1>; dy=<1,-1,0>?

Rys. 4. Dwa (a raczej sześć) zestawy ścieżek. Ścieżek winno być sześć - w przypadku użycia trzech kierunków. W każdym tu prezentowanym zestawie trzy ścieżki się pokrywają. Wydaje się, że dla zamkniętych ścieżek mamy właśnie ich pokrycia. Jak już było wspomniane, inną metodą reprezentacji możliwych kierunków, jest przyjęcie indeksu. Użyty wskaźnik pozwala po prostu nazwać dany kierunek. Rysunek poniżej pokazuje jedną z możliwych konwencji. Nadaliśmy nazwy wyszczególnionym kierunkom, tak zwyczajnie po prostu je numerując. Każdy z ośmiu kierunków może być wybrany. Wyboru zwykle dokonujemy losowo. Kierunki zatem dają się kodować liczbami. To z kolei pozwala opisać ścieżkę.

Rys. 5. Ponumerowane osiem kierunków.

Zbudujemy przykładowo dwie ścieżki z tych samych czterech kierunków. Ścieżki są złożone z tych samych elementów. Ściślej elementy (kierunki) są te same ale występują w różnej kolejności. Powstałe ścieżki jednak nie są identyczne. To już widzieliśmy nawet dla trzech kierunków.

Rys. 6. Ścieżka ułożona z czterech kierunków i opisana liczbą 0246. Ścieżka którą tworzy powyższy kwadrat, jest reprezentowana przez liczbę 0246. W ogólnym podejściu możemy przyjąć, iż najmniejsza możliwa liczba zapisu jest użyta jako kod danej ścieżki. Zatem do opisania tego kwadratu wybrana jest liczba zaczynająca się od zera. Jak zaraz zobaczymy istotna jest sekwencja kierunków.

Rys. 7. Ścieżka ułożona w kwadrat, jak poprzednia na Rys. 6, jednak z przeciwnym obiegiem. Użyte są te same kierunki, ale są one ułożone w innej kolejności. Ścieżka ta opisuje się liczbą 0642. Teraz ta ścieżka też układa się w kwadrat, tak jak poprzednio, jednak z inną kolejnością dostępnych czterech kierunków. Nasuwa się tu pojęcie kierunku obiegu na ścieżce. Otrzymana ścieżka ma kod liczbowy 0642, zupełnie inny niż kwadrat 0246. Cyfry w kodach liczbowych można cyklicznie przestawiać. Nigdy nie dostaniemy tych samych liczb dla ścieżek z Rys. 6 oraz 7.

Rozdział 7

* Błądzenie losowe na ścieżkach *

Błądzenie losowe daje się zrealizować na zadanej ścieżce. Kierunki ze ścieżki są wybierane losowo, jednak z pewnym ograniczeniem. Ścieżka, jak to już wiemy, to zestaw kierunków występujących w określonym porządku. Dla bieżącego kierunku, wybieramy kierunek występujący przed nim lub za nim w ścieżce. Los decyduje, który kierunek jest użyty do określenia nowej pozycji punktu. Na rysunku zamieszczonym poniżej, aktualny kierunek jest wykropkowany. W następnym kroku tylko jeden z kierunków diagonalnych będzie losowany; kierunek występujący zaraz za lub przed kierunkiem wykropkowanym. Coś jak wykonanie kroku w przód lub w tył. Tutaj ten krok może być w dowolną stronę. Zależy to od sekwencji kierunków. Zdefiniowaliśmy ogólne pojęcie skrętu: zamiast powiedzmy skrętu w lewo czy w prawo, operujemy określeniem kierunek następny lub poprzedni. To mogą być zupełnie dowolne kierunki i podajemy je względem aktualnego w zestawie na ścieżce.

Rys. 1. Ścieżka skomponowana z czterech kierunków. W tym przypadku mamy częściowe użycie pamięci w kreowanym systemie. W procesie pamięta się aktualny kierunek, i tylko aktualny. Jego poprzednik lub następnik jest wybierany losowo (jeden z dwóch) w następnym kroku. Oczywiście, również pamiętana jest ścieżka z ustalonymi z góry kierunkami. W tym systemie, w każdym kroku omija się kierunek ze ścieżki leżący dalej niż o jeden. Dokładniej, to właśnie wybiera się kierunki odległe dokładnie o 1 krok „w lewo” lub „w prawo”.

Rys. 2. Ślad pozostawiony przez błądzący punkt po zadanej z góry ścieżce. Poniżej podany jest program, który realizuje proces tworzenia Rys. 2. W procesie wybiera się losowo jeden z dwóch najbliższych sąsiednich kierunków do aktualnie użytego.

// path4.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class path4 extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int m = d.width; int n = d.height; //int [] dx = {0,1,0,-1}; //int [] dy = {-1,0,1,0}; //int [] dx = {1,1,-1}; //int [] dy = {-1,1,0}; int [] dx = {0,1,0,-1}; int [] dy = {-1,1,-1,1}; int maxit = 100000;

int i = (int)(Math.random() * m); int j = (int)(Math.random() * n); int dir = 0, maxdir = 4; g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(i,j,1,1); dir = (dir + (int) (Math.random () * 3.0) – 1 + maxdir) % maxdir; i = (i + dx[dir] + m) % m; j = (j + dy[dir] + n) % n; } } } public class path4 extends Frame { public static void main (String [] args) {new path4();} path4(){ super(“Chodzenie po sciezce w 4 kierunkach”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”, new path4()); show(); } }

Rozdział 8

* Błądzenie losowe z trzema kierunkami*

Ścieżkę tworzą trzy kierunki ułożone w trójkąt. Widać to na poniższym obrazku. Ścieżka jest zakodowana przez wartości delt; dx=<0,1,-1> oraz dy=<-1,0,1>. Trzy kierunki są określone jako pary przyrostów dla x oraz y, (x,y); (0,-1), (1,0) i (-1,1). W rozpatrywanym procesie ten sam kierunek nie może być wybrany dwa razy pod rząd. Zatem mamy tu wymieszanie czynnika losowego z deterministycznym. W danym etapie losowo wybiera się tylko jeden z dwóch kierunków. Same kierunki oraz ich kolejność występowania są ustalone. Aktualny kierunek nie jest ponownie losowany. Ma on szansę dopiero w następnej turze. Wtedy będzie on sąsiadem dla aktualnego. Dajemy mu więc szansę tylko po innym, za drugim razem.

Rys. 1. Ścieżka złożona z trzech kierunków. Ciekawym doświadczeniem będzie zbadanie błądzenia losowego na podobnej ścieżce, gdzie przyrosty w deltach mają różne wartości. Jedna z takich możliwości jest pokazana poniżej na obrazku. Jak widać mamy tutaj przyrosty o 1, 2 oraz o 3 jednostki. Sama ścieżka nie tworzy figury zamkniętej.

Rys. 2. Ścieżka złożona z trzech kierunków. Przyrost długości (delty) są różne dla każdego kierunku

Rys. 3. Ślad z błądzenia losowego po ścieżce podanej na Rys. 1. Kolejny program w Javie. Temu właśnie przypadła zrealizować chodzenie po trójkącie. Dobrą gimnastyką będzie zmodyfikować kod, aby program ten zmieniał długości kroków na ścieżce, tak jak mu ona każe.

// path3.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class path3 extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int m = d.width; int n = d.height; int [] dx = {0,1,-1}; int [] dy = {-1,0,1}; int k,maxit = 100000; int i = (int)(Math.random() * m); int j = (int)(Math.random() * n); int dir = 0, maxdir =3;

g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(i,j,1,1); k = (Math.random()>0.5)?1:-1; dir = (dir + k + maxdir) % maxdir; i = (i + dx[dir] + m) % m; j = (j + dy[dir] + n) % n; } } } public class path3 extends Frame { public static void main (String [] args) {new path3();} path3(){ super(“Chodzenie na ścieżce z trzema kierunkami”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”,new path3()); show(); } }

Rozdział 9

* Błądzenia losowe na ścieżce w 3 wymiarach *

Niewątpliwie najprostszą ścieżką w trzech wymiarach (3W = 3D), jest trójkąt w przestrzeni. Jeden z jego rodzajów widać poniżej na rysunku. Ścieżka ta została użyta do realizacji błądzenia losowego. Do określenia ścieżki potrzebujemy podać wartości dla trzech delt; dla x, y oraz dla z. Następujący, uporządkowany ciąg opisuje tę ścieżkę: dx=<1,-1,0>, dy=<-1,0,1> oraz dz=<0,1,-1>. W tym wypadku trzy kierunki w przestrzeni mają postać: (1,-1,0), (-1,0,1) oraz (0,1,-1). Oczywiście daje się zbudować inne trójkąty w 3W.

Rys.1. Przykłady dwóch ścieżek w 3W. Dobrym ćwiczeniem jest zakodować ścieżkę pokazaną po prawej stronie rysunku. Następnie opracować program, który realizuje błądzenie losowe na tak właśnie zadanej ścieżce.

Rys. 2. Ślad z błądzenia losowego po ścieżce złożonej z trzech kierunków w 3W. Jak zazwyczaj w tej książce dalej przedstawiony jest program w języku Java. Program ten realizuje błądzenie losowe w 3W na trójkątnej ścieżce.

// path3d.java // Autor M.Szyszkowicz, MMIV import java.awt.*; import java.awt.event.*; class path3d extends Canvas{ public void paint(Graphics g){ Dimension d = getSize(); int k = 3; int m = d.width / k; int n = d.height; int [] dx = {1,-1,0}; int [] dy = {-1,0,1}; int [] dz = {0,1,-1}; int w,maxit = 100000; int x = (int)(Math.random() * m); int y = (int)(Math.random() * m);

int z = (int)(Math.random() * k); int dir = 0, maxdir =3; g.setColor(Color.black); for (int iter=0; iter<maxit; iter++){ g.fillRect(z * m+ x,y,1,1); w =(int) (Math.random () * 3.0) - 1; dir = (dir + w + maxdir) % maxdir; x = (x + dx[dir] + m) % m; y = (y + dy[dir] + n) % n; z = (z + dz[dir] + k) % k; } } } public class path3d extends Frame { public static void main (String [] args) {new path3d();} path3d(){ super(“Chodzenie po sciezce w 3W”); addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent event) {System.exit(0);}}); setSize(640,480); add(“Center”, new path3d()); show(); } }

Rozdział 10

* Monte Carlo i liczba pi *

Dana jest sekwencja X1, X2, X3,… . liczb losowych z wartościami jednostajnie dystrybuowanymi pomiędzy liczbami 0 a 1. Innymi słowy generujemy ułamki. Pytanie jest, ile takich liczb losowych trzeba dodać, aby wynik sumowania nie przekroczył z góry zadanej wartości T, tj. X1+X2+X3+…+XN<=T. a. Dla T=1, tu uwaga następuje duża niespodzianka, rozwiązaniem tego problemu jest liczba e=2.7182..., która ma nieskończone rozwinięcie dziesiętne. Średnio trzeba więc dodać N=e składników. Liczba e jest podstawą logarytmu naturalnego. b. Wyznaczyłem liczbę Spi=1.235249264743367..., która ma tę własność, że dla T=Spi, wynikiem jest liczba pi (N = pi). Liczba Spi jest pewnie liczbą niewymierną oraz przestępną. Tylko tak to zgadujemy. Kto to potrafi kiedykolwiek udowodnić? Wartość Spi pozwala określić liczbę pi poprzez symulację. Jest to inny rodzaj metody Monte Carlo na znajdowanie wartości liczby pi. c. Dla T=e, mamy rozwiązanie eS=6.10400234136375... . d. Dla T=pi, mamy rozwiązanie piS=6.94950388752955... . e. Dla T=Ssqrt(2)=0.34657359027973…, rozwiązaniem jest sqrt(2). f. Dla T=SSpi0.211272783514569, rozwiązaniem jest Spi.

Poniżej podany jest program w języku Java o nazwie Spi, który liczy przybliżenie liczby pi na bazie wartości liczby Spi.

//Spi.java - M.Szyszkowicz,

public class Spi{ public static void main(String[] args){ double s,Spi=1.23524926474336; int k,m,tm=0,iter=1024; for(k=0;k
KONIEC

KONIEC