Przeszukiwanie lokalne...

Czasami, podczas rozwiązywania różnych problemów zależy nam na szybkości otrzymania rozwiązania (niekoniecznie najlepszego). W takim wypadku np. algorytmy genetyczne są bardzo 'nie na miejscu', a to ze względu na fakt, że nigdy nie wiemy kiedy zatrzymać takowy algorytm. Czasami też ograniczeniem na stosowane metody jest ilość dostępnej pamięci, wtedy też algorytmy genetyczne są niefajne (cała populacja zajmuje dość pokaźną liczbę bajtów...). W takich wypadkach dobrze jest zaprzągnąć do roboty algorytmy zwane 'przeszukiwaniem lokalnym'. Nie operują one na populacjach rozwiązań, a na pojedynczym rozwiązaniu, które w kolejnych krokach algorytmu jest 'poprawiane'. Przeszukiwanie lokalne jest algorytmem 'lokalnym' (jak sama nazwa wskazuje) dlatego otrzymane tą metodą rozwiązanie nie zawsze (prawie nigdy) będzie rozwiązaniem globalnie najlepszym.
Jak działa takowy algorytm?

1. Wygeneruj rozwiązanie początkowe.
2. W zależności od algorytmu są dwie możliwości:
   1. Wygeneruj całe sąsiedztwo aktualnego rozwiązania i przejdź do najlepszego z nich (aktualny <- najlepszy z sąsiadów)
   2. Generuj po kolei wszystkich sąsiadów i przejdź do pierwszego z wartością funkcji celu lepszą od aktualnego (aktualny <- pierwszy lepszy z sąsiadów)
3. Jeśli w punkcie drugim nie można było znaleźć rozwiązania lepszego to znaczy, że kończymy poszukiwania, a rozwiązanie aktualne staje się rozwiązaniem końcowym.

I po kolei:
Generowanie początkowego rozwiązania
Krok ten jest taki sam jak generowanie początkowej populacji w algorytmie genetycznym. Jedyna różnica to liczba generowanych osobników. Przy przeszukiwaniu lokalnym tworzy się tylko jedno rozwiązanie. W tym kroku należy zadbać o wygodną i w miarę mało pamięciorzerczą reprezentację (ale o tym dokładnie się nie będę rozpisywał - większość zasad jest opisana przy tekście na temat podstawowych elementów algorytmu genetycznego (tutaj)). W przypadku przeszukiwania lokalnego rozwiązanie początkowe może być wygenerowane całkowicie losowo (podobnie jak w przypadku algorytmu genetycznego). Jednak tutaj mamy do dyspozycji tylko jednego osobnika, więc dobrze by było zrobić na początku jakąś bardziej wyszukaną procedurkę do znajdowania rozwiązania początkowego. Może to być np. algorytm zachłanny. Dla przykładu gdy do rozwiązania jest problem komiwojażera to początkowe rozwiązanie może być wygenerowane według następującego algorytmu:

1. Wylosuj jakieś miasto - jest to pierwsze odwiedzane miasto
2. Przejdź do najbliższego nie odwiedzonego miasta - jest to kolejne odwiedzane miasto
3. Jeśli nie skompletowano całej trasy przejdź do punktu drugiego

Jest to zachłanny algorytm, który w czasie wielomianowym wygeneruje całkiem znośną trasę komiwojażera. Można ten algorytm trochę zmodyfikować. Np. zamiast na początku (w pierwszym kroku) losować jakieś miasto można uruchamiać ten algorytm n-krotnie (n - liczba miast) i po kolei sprawdzać jaka będzie końcowa wartość rozwiązania dla różnych miast początkowych. Do dalszej analizy wybiera są to rozwiązanie które daje najkrótszą trasę.

Przejście do rozwiązania lepszego
W tym kroku mamy do wyboru dwie drogi. Obie używają pojęcia sąsiedztwa. Więc może opis tego kroku zacznę od pobieżnego opisania co to znaczy owe sąsiedztwo. Ogólnie rzecz ujmując sąsiadem danego rozwiązania jest rozwiązanie niewiele się od niego różniące. Np jeśli mamy listę miast 1-2-3-4 (jest to przykładowe rozwiązanie problemu komiwojażera) to jego sąsiadem może być np. rozwiązanie 1-3-2-4 (dwa miasta wymieniły się pozycjami). W zasadzie od definicji sąsiedztwa zależy czas działania algorytmu przeszukiwania lokalnego oraz (co ważniejsze) liczba sprawdzanych rozwiązań. W kroku tym możemy sprawdzić maksymalnie całe sąsiedztwo danego rozwiązania. Np. dla problemu komiwojażera, jeśli przyjmiemy, że sąsiadem jest rozwiązanie w którym dwa miasta zamieniły się miejscami, mamy do sprawdzenia (n²-n)/2 rozwiązań (przykład: sąsiadami 1-2-3-4 będą: 1: 2-1-3-4, 2: 3-2-1-4, 3: 4-2-3-1, 4: 1-3-2-4, 5: 1-4-3-2, 6: 1-2-4-3). Jeśli natomiast przyjmiemy, że sąsiadem jest rozwiązanie w którym nastąpiła wymiana z miastem pierwszym mamy do sprawdzenia n-1 rozwiązań (przykład: sąsiadami 1-2-3-4 będą: 1: 2-1-3-4, 2: 3-2-1-4, 3: 4-2-3-1). Jeśli reprezentacją rozwiązania będzie ciąg bitów to sąsiadem może być rozwiązanie różniące się na maksymalnie jednym bicie. Wtedy sąsiadów do sprawdzenia będzie n (n - długość ciągu bitów) (przykład: sąsiadami 00101110 będą: 1: 10101110, 2: 01101110, 3: 00001110, 4: 00111110, 5: 00100110, 6: 00101010, 7: 00101100, 8: 00101111).
Teraz pora wyjaśnić czym różnią się te dwie drogi postępowania z przeglądanym sąsiedztwem. Punkt a. nakazuje sprawdzenie (wygenerowanie i obliczenie wartości funkcji oceny) wszystkich rozwiązań sąsiednich i wybraniu z nich rozwiązania najlepszego (oczywiście jednocześnie lepszego od rozwiązania aktualnego - jeśli ten warunek nie jest spełniony to kończymy przeszukiwanie). Ten algorytm nazywany jest algorytmem największego spadku. Charakteryzuje się on małą liczbą kroków (iteracji) a każdy krok dość znacznie poprawia wartość rozwiązania aktualnego. Natomiast w punkcie b. (algorytm zachłanny) przeglądanie sąsiedztwa kończy się z chwilą znalezienia rozwiązania chociaż odrobinę lepszego od aktualnego. Dzięki temu poszczególne kroki algorytmu wykonywane są szybciej (nie jest sprawdzane całe sąsiedztwo), jednak kroków tych jest więcej, a różnice pomiędzy wartościami kolejnych aktualnych rozwiązań są niewielkie.

Zakończenie przeszukiwania
Jeśli w punkcie drugim zostało przeszukane całe sąsiedztwo i nie zostało znalezione rozwiązanie lepsze od aktualnego to należy przerwać przeszukiwania. W tym miejscu widać wyraźnie 'lokalność' takiego algorytmu. Jeśli np. naszym aktualnym rozwiązaniem jest 1-2-3-4-5 o wartości funkcji celu np. 5 (przyjmujemy maksymalizację f. celu), a wszyscy sąsiedzi mają wartość mniejszą niż 5 to nigdy nie zostanie osiągnięte np. rozwiązanie 2-1-4-3-5 o wartości 7. Rozwiązanie to różni się od aktualnego dwoma przestawieniami, więc nie jest jego sąsiadem. Można próbować 'przeskoczyć' to ograniczenie zmieniając definicję sąsiedztwa np. na taką która dopuszcza dwa przestawienia. Należy jednak pamiętać że zwiększy to znacznie liczbę sąsiadów (w tym przypadku do liczby rzędu n⁴), a to z kolei wydłuży znacznie czas jednego kroku, co spowoduje znaczne wydłużenie całkowitego czasu obliczeń. Poza tym tylko pełna definicja sąsiedztwa (wszystkie rozwiązania są swoimi sąsiadami) zapewnia przeszukanie całej przestrzeni rozwiązań. Jednak stosowanie takiej definicji sąsiedztwa mija się z celem (wraca problem NP-trudności).

Aby poprawić jakość generowanych przez przeszukiwanie lokalne rozwiązań można zastosować 'wielokrotnie startujący' algorytm lokalnego przeszukiwania. Wygląda on następująco:

1. Najlepszy = NULL
2. Uruchom przeszukiwanie lokalne z losowym punktem startowym
3. Jeśli Najlepszy jest gorszy od NajlepszyZPrzeszukiwaniaLokalnego to Najlepszy <- NajlepszyZPrzeszukiwaniaLokalnego
4. Dopóki nie koniec wróć do 2.

Warunkiem kończącym jest tu najczęściej liczba iteracji lub czas. Podobnie jak w przypadku generowania rozwiązywania początkowego dla AL (algorytmu przeszukiwania lokalnego) można tutaj wykorzystać jakieś bardziej wymyślne algorytmy otrzymywania początkowego rozwiązania. Np. wspomniany wcześniej zachłanny algorytm tworzący trasę komiwojażera dla różnych miast początkowych.

Przeszukiwanie lokalne jest bardzo często wykorzystywane do naprawiania pojedynczych rozwiązań w algorytmach genetycznych. Tuż przed krokiem selekcji każdy osobnik jest poddawany działaniu algorytmu przeszukiwania lokalnego. Po takiej operacji wartość funkcji oceny najczęściej ulega poprawie. Dzięki temu algorytm genetyczny działa szybciej i generuje lepsze rozwiązania końcowe. Istnieją dwa podejścia do 'poprawiania' osobników:

1. Do selekcji brana jest wartość funkcji oceny 'poprawionego' osobnika, jednak sam osobnik nie jest modyfikowany
2. Do selekcji brana jest wartość f. oceny 'poprawionego' osobnika, a sam osobnik jest modyfikowany

Przykład:
Wyjściowy osobnik wyglądał następująco: 1-2-3-4-5-6 i miał wartość funkcji oceny 55. Po przeszukiwaniu lokalnym osobnik wygląda 2-1-3-4-5-6 i ma wartość funkcji oceny 59. W pierwszym przypadku do selekcji idzie osobnik 1-2-3-4-5-6 z wartością funkcji oceny 59 natomiast w drugim przypadku do selekcji idzie osobnik 2-1-3-4-5-6 z wartością 59.

Wady lokalnego przeszukiwania próbują eliminować inne algorytmy np. symulowane wyżażanie, czy algorytmy wykorzystujące listę tabu, ale o nich może innym razem.
Na górę

---

Wprowadzenie do programowania strategii w grach obliczalnych
- czyli jak napisać program grający w kółko i krzyżyk albo w szachy ...
Michał Czardybon

Na początek ważna uwaga dla uczniów:
Notatki z lekcji polskiego prowadź zawsze w zeszycie w kratkę - inaczej się zanudzisz.

Do napisania programu grającego w kółko i krzyżyk skłoniły mnie porażki w partiach z moim tatą. Nie mogąc temu zaradzić obiecałem mu, że napiszę program, który z nim wygra. Było to w I albo II klasie liceum, gdy moje zdolności programowania nie obejmowały jeszcze podstaw algorytmiki, toteż pierwsze podejście nie było zbyt udane. Nie wiedziałem wtedy o czymś takim jak rekurencja więc mój program pracował tak: dla każdego możliwego ruchu sprawdzał jaki po tym ruchu może być najlepszy ruch przeciwnika, po czym wybierał taki ruch aby odpowiedź przeciwnika była jak najsłabsza. Musiałem jeszcze napisać funkcję, która oceniała sytuację aby możliwe było obliczenie, który z dwóch lub więcej stanów gry jest najkorzystniejszy. W przypadku sytuacji kończącej grę (5 znaków jest w rzędzie) funkcja ta zwraca +nieskończoność, w przeciwnym razie jakąś liczbę - dodatnią, gdy przewagę ma bieżący gracz, ujemną, gdy przegrywa. Dobra realizacja tego elementu wymaga poświęcenia sporo czasu na eksperymenty i ma bardzo znaczący wpływ na ostateczną efektywność programu.
      W grze kółko i krzyżyk można w celu wartościowania sytuacji przyjąć takie kryteria jak liczba nie blokowanych dwójek i trójek znaków, czy skrzyżowania takich układów. W szachach można zliczać bierki wg wag odpowiednich dla różnych figur i z uwzględnieniem ich położenia na szachownicy i liczby możliwych ruchów, możliwych bić i możliwości bycia zbitym. Tutaj pole manewru dla inwencji programisty jest ogromne.
      Wracając do głównego algorytmu, to domyślasz się chyba, że profesjonalne programy nie analizują tylko 2 ruchów do przodu, jak mój pierwszy program. Aby komputer mógł powalczyć z przeciętnym człowiekiem potrzeba przewidywania co najmniej 5 ruchów do przodu, a w przypadku gry z profesjonalistą nawet kilkanaście może nie wystarczać. Algorytm wymaga więc modyfikacji i uogólnienia. W moim przypadku polegało to na napisaniu programu od nowa. Zabrałem się do tego w 3 klasie liceum, gdy mania kółko i krzyżyk na dobre opanowała moją klasę. Uogólnienie algorytmu polegało na zmianie sposobu wybierania najlepszego ruchu przeciwnika, na taki sam jak dla bieżącego gracza, tzn. najlepszy ruch przeciwnika, jest ruchem po którym bieżący gracz może dać najsłabszą odpowiedź, a ten ruch jest tym, po którym wykazać nie może się przeciwnik itd. Jest to algorytm rekurencyjny, który trzeba ograniczyć, bo inaczej przeszukiwał by wszystkie możliwe rozgrywki, co wymagałoby praktycznie nieskończonego czasu. Wynika to ze złożoności. Zakładając, że liczba możliwych ruchów dla konkretnej sytuacji jest stała i wynosi x, to możliwości rozegrania n ruchów jest x^n. Skoro jedna partia trwa przeciętnie 60 ruchów, a w jednym ruchu jest, załóżmy, 10 sensownych możliwych posunięć, to wykonanie algorytmu wymagałoby przeanalizowania ok. 10^60 sytuacji. Praktycznie przeszukiwanie trzeba zakończyć po najwyżej 5 ruchach i wtedy dokonać oceny sytuacji przy pomocy wcześniej opisanej funkcji - tutaj evaluate(). Praktycznie wygląda to jakoś tak:

class tmove {int x, y, val;};

tmove bestmove(int h)
{
  if (h == MAX_H) return evaluate(); /* nie ma znaczenia jaki to ruch */
									 /* ważne tylko jak dobry */
  tmove move[MAX_MOVE_NUM],          /* lista możliwych ruchów */
		best;                        /* aktualnie najlepszy */
  int   num;                         /* liczba możliwych ruchów */
  int   v;                  
  get_possible_moves(move, num);     /* utwórz liste możliwych ruchów */
  best.val = -INF;                   /* inicjacja */
  for (int i = 0; i < num; i++)      /* dla każdego z możliwych ruchów */
	 {
		perform_move(move[i]);       /* wykonaj ruch */
		v = -bestmove(h + 1).val;    /* ocen go z punktu widzenia bieżącego gracza */
		if (v > best.val)            
		   {
			  best = move[i];
			  best.val = val;
		   }
	   undo_move();                 /* cofnij ruch */
	 }
  return best;
}
			

Wywołanie: bestmove(0); Funkcja perform_move(...) stawia na przemian kółka i krzyżyki - to ona załatwia techniczną realizację zmiany graczy. Funkcja undo_move() przywraca sytuację sprzed ostatniego ruchu. Podkreślam, że dane wywołanie funkcji bestmove() znajduje najlepszy ruch dla gracza, który w danej sytuacji ma wykonać ruch. Kolejne rekurencyjne jej wywołania realizują to zadanie z punktu widzenia różnych graczy (na przemian).
Okazuje się jednak, że taki algorytm nie jest optymalny. Rozważmy następującą sytuację w grze, w której zawsze są dokładnie dwa możliwe ruchy:

       |
    -------
   |       |
   A       B     - ruchy gracza X
   |       |
  ---     ---
 |   |   |   |   - ruchy gracza Y
 C   D   E   F
			

Jest to fragment drzewa ruchów gry. Bieżący gracz - gracz X - ma do wyboru dwa możliwe ruchy: A albo B. Po wykonaniu ruchu A jego przeciwnik - gracz Y - będzie mógł wykonać ruch C albo D, w przeciwnym razie E albo F. Załóżmy teraz, że ruch C prowadzi do sytuacji ocenionej wartością -1, D do -2, a E do 5. Ruch F na razie ignorujemy. Wartości są podane z punktu widzenia gracza Y. Dla X-a są to wartości odpowiednio 1, 2, -5. Gracz X analizuje najpierw konsekwencje ruchu A i otrzymuje, że z perspektywy dwóch ruchów do przodu, ruch A ma wartość 1 (zakładamy cały czas, że przeciwnik wybiera strategię optymalną, czyli w tym przypadku po ruchu A ruch C). Teraz X zaczyna analizować fragment drzewa ruchu pod wierzchołkiem B - przeciwnik ma do wyboru ruchy E i F. Jednak zauważmy, że skoro ruch E ma wartość 5 dla gracza Y, to niezależnie od tego jak wartościowy jest ruch F, ruch B będzie przez gracza X oceniony najwyżej -5 punktami, czyli nie ma sensu zastanawiać się nad ruchem F, tylko po sprawdzeniu ruchu E, gracz X od razu odrzuci możliwość wykonania ruchu B - wybierze ruch A. Tym sposobem, przy głębszej analizie drzewa ruchów, można zaoszczędzić bardzo dużo czasu.
      Modyfikacja naszej funkcji bestmove polega na wprowadzeniu dodatkowego parametru "beta" i dodatkowego warunku: best.val < beta. Jeśli ten ostatni warunek w pewnym momencie przestanie być spełniony, to wtedy natychmiast dokonywane jest wyjście z funkcji ze zwróceniem aktualnej wartości najlepszego ruchu, która i tak nie będzie miała wpływu na wartości ruchów na wyższym poziomie drzewa ruchów. W przypadku analizy głębszej niż 2 ruchy do przodu, należy wprowadzić jeszcze jeden parametr - "alpha", który będzie zawierał wartość przeciwną do wartości bety z poziomu o jeden wyższego. Jego funkcją będzie przekazywanie do kolejnego rekurencyjnego wywołania bestmove() wartości parametru beta, jeśli będzie większy od wartości najlepszego ruchu w bieżącym wywołaniu bestmove(). W praktyce oznacza to, ze na początku bestmove() wartość najlepszego ruchu inicjowana jest nie -INF, tylko właśnie alfą.

Konkretnie po zmianach bestmove() wygląda tak:

tmove bestmove(int h, int alpha, int beta)
{
  if (h == MAX_H) return evaluate(); 
									 
  tmove move[MAX_MOVE_NUM],          
		best;                        
  int   num;                         
  int   v;                  
  get_possible_moves(move, num);     
  best.val = alpha;                   /* zmiana ! */
  for (int i = 0; i < num; i++)      
	 {
		perform_move(move[i]);       
		v = -bestmove(h + 1, -beta, -best.val).val; /* zmiana */   
		if (v > best.val)            
		   {
			  best = move[i];
			  best.val = v;
			  if (v >= beta) return best;  /* dodatkowy warunek */
		   }
	   undo_move();                 
	 }
  return best;
}
			

Wywołanie zmienia się na: bestmove(0, -INF, +INF);

Takie przeszukiwanie drzewa ruchów nazywa się algorytmem cięć alfa-beta, lub przeszukiwaniem z odcięciami.
Dalszy wzrost wydajności można uzyskać zapamiętując jak najwięcej informacji między kolejnymi ruchami, ponieważ szukając najlepszego ruchu w kolejnych ruchach, tzn. już w konkretnej grze komputera z człowiekiem, przechodzi się w dużej części te same fragmenty drzewa ruchów. Sensownie jest więc wykorzystać dane z poprzedniej kolejki i analizować tylko te końcowe gałęzie drzewa, które były poza zasięgiem algorytmu w poprzednim ruchu.
Ważne jest też aby przed przeanalizowaniem ruchów posortować je malejąco względem wstępnie oszacowanej ich wartości - dzięki temu można znacznie podnieść efektywność cięć alfa-beta. W tym celu można też wykorzystać analizę drzewa ze zmniejszoną głębokością. Jeśli na przykład analizujemy 10 ruchów do przodu, można najpierw przeanalizować 8 ruchów do przodu, w czasie wielokrotnie mniejszym, co wynika z wykładniczej złożoności algorytmu, aby zebrać informację w jakiej kolejności analizować ruchy we właściwym przeszukiwaniu i tym samym osiągnąć wyższą wydajność.
Jeśli potrafilibyśmy skutecznie ocenić w jakim przedziale może znajdować się wartość najlepszego ruchu, jaki może wykonać komputer, to można użyć innego, w takim przypadku skuteczniejszego wywołania funkcji:
bestmove(0, v - delta, v + delta); // v - oczekiwana wartość ruchu
Jeśli takie wywołanie da wynik niewiększy od v - delta lub niemniejszy od v + delta, to aby znaleźć najlepszy ruch należy odpowiednio zmodyfikować ten przedział i wywołać tę funkcję jeszcze raz. Na przykład w przypadku otrzymania wartości niewiększej od v - delta, można spróbować:
bestmove(0, v - 2 * delta, v - delta);

No i na koniec najważniejsze - mój program ogrywa mojego tatę za każdym razem :-)) ... mnie też :-((
Na górę

---

O interpretacji wyrażeń arytmetycznych...

Stosowana przez nas na codzień notacja wyrażeń matematycznych dla ludzi jest naturalna i bardzo przyjemna. Jednak jeśli chcemy napisać program, który będzie potrafił rozwiązać dowolne wyrażenie to stajemy przed poważnym problemem. Wszystkiemu winne są priorytety działań, wyrażenia w nawiasie i inne tego typu pułapki utrudniające analizę. Przez nie musimy najpierw znaleźć wyrażenie o najwyższym priorytecie, później o trochę niższym itd. Jest to bardzo niewygodne i czasochłonne. Zanim przedstawię całkiem prosty, efektywny i elegancki (bazujący na rekurencji) algorytm na rozwiązywanie wyrażeń chciałbym opisać inną notację wymyśloną dawno temu przez pewnego Polaka o nazwisku Łukasiewicz. Jest to notacja wymarzona dla maszyn, jednak dla nas przyzwyczajonych do starej notacji jest nie do przetrawienia. Może mały przykładzik wyrażenia w Odwrotnej Notacji Polskiej (bo tak została ochrzczona notacja pana Łukasiewicza):
2 3 + 5 * 5 2 - *
Wynikiem tego wyrażenia jest 75. A w jaki sposób się je oblicza? Najprościej jak tylko się da. Wyrażenie czytamy od lewej do prawej. Bez żadnego nawrotu. Jeśli natrafimy na liczbę rzucamy ją na stos. Jeśli trafimy na operator to pobieramy dwie ostatnie liczby ze stosu, wykonujemy operację, a wynik z powrotem umieszczamy na stosie. Po przetworzeniu całego wyrażenia (gdy nie będzie ono zawierało błędów) na szczycie stosu będzie na nas czekał wynik. Prawda, że proste? Proszę zauważyć, że w wyrażeniach ONP nie występują nawiasy (dlatego czasami na notacja nazywana jest beznawiasową), o priorytecie działań decyduje kolejność ich występowania w wyrażeniu.
Niestety nie możemy wymagać od użytkownika, że będzie znał ONP i chciał ją zastosować podczas pracy z naszym programem. Dlatego pod koniec tego tekstu przedstawię programik konwertujący wyrażenia z notacji normalnej (dla ludzi) na normalną (dla komputerów).
Wracając do interpretacji wyrażeń. Dla każdego zapisu w języku formalnym możemy napisać gramatykę, czyli zbiór reguł które musi spełniać zapis aby był poprawny. Przykładem może być zapis imienia: Na początku mamy jedną dużą literę, a później kilka małych. W imieniu nie może występować nic innego. Gramatykę tę można zapisać w następujący sposób:
IMIE       -> duzaliterka RESZTALITER
RESZTALITER-> malaliterka RESZTALITER
           -> malaliterka
Dla tych którzy nie rozumieją tego zapisu tłumaczę. Dużymi literami zostały zapisane wszystkie występujące w gramatyce produkcje. Jeśli nazwa produkcji jest po lewej stronie strzałki oznacza to definicję(rozwinięcie, dopasowanie) produkcji (jej zawartości), jeśli po prawej to znaczy, że podczas interpretacji należy wstawić tam zawartość produkcji. Jeśli po lewej stronie strzałki nic nie ma to znaczy, że jest to kolejne rozwinięcie ostatnio definiowanej produkcji (produkcje mogą mieć po kilka rozwinięć). Małymi literkami napisałem natomiast wszystkie wartości stałe, nie rozwijające się. Wiadomo, że duzaliterka to jeden ze znaków od A do Z i nic innego, malaliterka to cos pomiędzy a-z. I jeszcze jedno: gdy z prawej strony strzałki (w miejscu definicji produkcji) nie ma żadnego znaku to jest to tzw. puste rozwinięcie. Oznacza ono, że definiowana produkcja może wystąpić, ale nie musi. Nawiązując do poprzedniego przykładu przedstawię teraz gramatykę na imię i nazwisko:
OSOBA      -> IMIE NAZWISKO
IMIE       -> duzaliterka RESZTALITER
IMIE       ->
NAZWISKO   -> duzaliterka RESZTALITER
RESZTALITER-> malaliterka RESZTALITER
           -> malaliterka
Powyższa gramatyka definiuje osobę (jej imię i nazwisko), przy czym imię nie jest wymagane. Ale wróćmy do wyrażeń arytmetycznych. Przedstawię teraz gramatykę na dowolne wyrażenie zawierające dodawanie, odejmowanie, mnożenie i nawiasy:
WYRAZENIE->SKLADNIK
         ->SKLADKIK '+' WYRAZENIE
         ->SKLADKIK '-' WYRAZENIE
SKLADNIK ->CZYNNIK
         ->CZYNNIK '*' SKLADNIK
CZYNNIK  ->liczba
         ->'(' WYRAZENIE ')'
Jeśli ktoś załapał wcześniejsze wywody na temat gramatyk to nie będzie miał problemów z analizą i interpretacją tej gramatyki. Poza tym gramatyka ta jest strasznie uboga, więc do poważnych zastosowań należy ją rozwinąć o dzielenie, modulo, można dodać operacje binarne, logiczne. Wedle własnej fantazji. Wiemy już jak napisać gramatykę do wyrażeń. Pora teraz zastanowić się jak ją przenieść do programu. Procedury wywoływane rekurencyjnie to nic innego jak procedury (lub funkcje). Natomiast takie rzeczy jak '+' czy malaliterka należy sprawdzać wprost, czy to co jest w tej chwili odczytywane jest tym czego się spodziewamy. Jeśli produkcja ma kilka rozwinięć należy zastosować jakiegoś case'a lub switch'a. Należy też pamiętać o sprawdzaniu czy w analizowanym ciągu nie ma jakiś danych, których gramatyka nie przewiduje (wtedy należy zgłosić błąd).
No i mamy napisaną gramatykę, wprowadzoną do programu, nasza gramatyka sprawdza poprawność składniową analizowanego tekstu. Ale jeszcze nic nie liczy. Należy więc naszą gramatykę ożywić dodając trochę akcji. Wszystkie akcje do produkcji umieszcza się na samym końcu. Dzięki temu mamy pewność, że najpierw zostaną wykonane najbardziej zagłębione akcje. Czyli np: dla wyrażenia 3*2 najpierw wykona się akcja przy produkcji CZYNNIK->liczba (dla trójki), później CZYNNIK->liczba (dla dwójki), później SKLADNIK->CZYNNIK (dla późniejszego zagłębienia się dla 2), później SKLADNIK->CZYNNIK*SKLADNIK, a na samym końcu produkcja startowa WYRAZENIE->SKLADNIK. I taka kolejność nam się bardzo podoba, bo najpierw mamy dostęp do liczb (argumentów) tych wyrażeń które są liczone jako pierwsze, później do samych wyrażeń o najwyższym priorytecie, później do liczb biorących udział w wyrażeniach o trochę mniejszym priorytecie itd.
Czy nie przypomina nam to już trochę ONP? Raczej tak. Okazuje się, że akcje sprowadzają się tylko do zrzucania pewnych elementów na stos (produkcja CZYNNIK->liczba) i do pobierania dwóch ostatnich i obliczania wyrażenia (wszystkie produkcje z operatorami).

Jeśli powyższe wypociny są dla kogoś niejasne to zamieszczam dwa kody:

• Program konwertujący wyrażenia normalne na ONP. Z tego kodu korzystało już kilka osób i kod ten wiele im wyjaśnił. Jest dużo komentarzy i kod jest pisany jak najprostszym językiem. Konwerter
  (Uwaga! Gramatyka w tym przykładzie nie jest idealna dlatego czasami kolejność działań nie jest zachowana (proszę spróbować skonwertować następujące wyrażenie: 5-2+3). Za jakiś czas postaram się umieścić tutaj wersję z lepszą gramatyką)
  
• Część kodu z kalkulatora. W przeciwieństwie do poprzedniego kod ten jest trochę zamieszany i są w nim tylko szczątkowe komentarze. W zamian za to dostajemy narzędzie do obliczania dowolnego wyrażenia arytmetycznego, pozwalające stosować liczby z różnych systemów liczenia i kilku przydatnych funkcji (pow, sqrt...). Program pisałem pod Borlandem 5.01. Z tym fragmentem kodu nie powinno być problemów, bo korzystam tylko (chyba) ze standardowych funkcji C. Kalkulator
  
  
  

To wszystko, życzę przyjemnego liczenia
Na górę

---

O stereogramach...

Algorytm

Tak jak wiele innych efektów wizualnych efekt 3d na płaskim obszarze możemy uzyskać tylko dzięki oszukaniu naszych oczu.
Żeby zobaczyć efekt 3d należy patrzeć "przez ekran" dzięki temu możliwe jest wpływanie na odległość z jaką nasze oczy będą interpretować widziane obrazy. Poniższy obrazek pokazuje jak patrzymy na rzeczy bliższe i dalsze:

Widać z niego wyraźnie, że oczy interpretują odległość na podstawie kąta jaki tworzą "promienie patrzenia" poszczególnych oczu. Wykorzystując ten fakt możemy już zabrać się do analizy algorytmu 3d. Aby to jednak było możliwe należy przyjąć, że patrzymy na ekran w ten sposób:

Jest to właśnie 'patrzenie przez ekran'. Na początku bardzo trudno jest 'namówić' oczy aby nie skupiały swojej uwagi na monitorze, ale na jakimś fikcyjnym punkcie za nim. Istnieje kilka metod na nauczenie się 'zezowania'. Moim zdaniem najprościej jest się nauczyć patrząc w monitor na swoje odbicie (ewentualnie czegoś jasnego (np. lampka na biurku)). Warto jest się nauczyć patrzeć na steregoramy, ponieważ efekt jest wspaniały. A dlaczego na ekranie widzi się trzeci wymiar. Możliwe jest ono tylko dzięki temu, że poszczególne kolumny ekranu są do siebie bardzo podobne (dzięki temu oczy mogą "złapać ostrość"). Każda para kolumn składa się z "bliźniaczych" punktów (na powyższym obrazku są to punkty A i A' oraz B i B').
W zależności od tego czy są one względem siebie przesunięte czy nie możemy otrzymać efekt głębi. Na powyższym obrazku odległość pomiędzy A i A' jest mniejsza niż pomiędzy B i B' dlatego oczy muszą ustawić się pod mniejszym kątem i widzą ten punkt w odległości mniejszej niż punkt tworzony przez B i B'.
A w jaki sposób tworzy się obrazek 3d... Na początku należy ustalić na ile kolumn będziemy dzielić ekran. W zależności od rozdzielczości i przekątnej ekranu mogą to być wartości od 6 do 15 pasków. Pierwszy pasek od lewej wypełniamy w sposób całkowicie dowolny (mogą to być losowo rozsypane punkty, może to być jakaś tekstura...). Natomiast kolejne paski są punkt po punkcie kopiowane z paska poprzedzającego dany, jednak z ewentualnym przesunięciem kopiowanych punktów. Wielkość przesunięcia określa tzw. mapa głębokości, która jest niezbędna do stworzenia stereogramu. Np. jeśli mapa głębokości mówi nam, że aktualnie obrabiany punkt powinien być na głębokości +3 to rysujemy go przesuniętego o trzy punkty w lewo.
W ten sposób tworzymy cały obrazek. Należy przy implementowaniu tego algorytmu pamiętać o nie przesadzaniu z ilością pasków oraz ilością dostępnych głębokości. Niedobre wartości tych parametrów powodują, że stereogram jest trudny do zobaczenia.

Przykładowe obrazki

Delfin

Sześcian i walec

'Kolczata' kostka

Na górę