Błądzenie losowe
Janusz Sobieraj - 28 LO

Błądzenie losowe bez powtórzeń

[Twoja przeglądarka nie obsługuje apletów Javy]
Będzie nas interesowało błądzenie losowe przy 4 kierunkach ruchu "bez powtórzeń" (patrz rys. obok).
Rygorystycznie założymy, że:
1° nie można wylosować miejsca, na którym było     się w dowolnym z poprzednich ruchów.
2° Będziemy wędrowali dotąd, "dopóki jest to     możliwe".
3° Mamy obowiązek wrócić do punktu startowego
W rozwiązaniu można zastosować listę jednokierunkową (stos)z zapisem elementu "na początku" i odczytem "od początku".

Taka struktura pozwoli na
1° sprawdzanie czy byliśmy już w danym punkcie
2° zrealizować powrót zdejmując ze stosu kolejne     notatki

Postulat wędrówki "dopóki jest to możliwe" można zrealizować przy pomocy listy typu zbiór i metody należy klasy lista (zobacz rozdział Trochę teorii).

Algorytm ogólny może wyglądać tak →(patrz ramka) .
Język i szczegóły techniczne to już rzecz gustu i upodobania. Na pewno ćwiczenie ciekawe i dające sporo satysfakcji, mimo że wygląda na łatwe.
Wnioski:

  1. Średnia ilość kroków stabilizuje się na liczbie (59,62)
    zobacz →zielony wykres
  2. Uzyskana droga nie jest oczywiście optymalna np najdłuższa
  3. Średnia odległość od punktu startowego stabilizuje się na liczbie, która jest pierwiastkiem ze średniej il.kroków ( u nas (√59 , √62) ) co w praktyce daje ≈8 →wykres niebieski
while(jest droga) 
{ 
  wyzeruj zbior; 
  while(jest droga lub możliwe inne kier.) 
  { 
    while(brak w zbiorze) 
      { 
        kierunek=losowa(4); 
      } 
    zapisz_w_zbiorze(los); 
    kierunek==0: jeśli(wolna(x,y+1)) y++; 
    kierunek==1: jeśli(wolna(x,y-1)) y--; 
    kierunek==2: jeśli(wolna(x+1,y)) x++; 
    kierunek==3: jeśli(wolna(x-1,y)) x--; 
    } 
  zapamietaj(x,y); 
  idz_do(x,y); 
}