Algorytmy z powrotami
Algorytmy z powrotami sÄ… wykorzystywane do rozwiÄ…zywania
problemów, w których z określonego zbioru jest wybierana sekwencja
obiektów tak, aby spełniała ona określone kryteria.
Klasycznym przykładem jest rozwiązanie problemu n-królowych.
Zadaniem jest ustawienie n-królowych na szachownicy n × n w taki
sposób, aby się wzajemnie nie szachowały.
Sekwencją w tym problemie jest n pozycji, na których są umieszczone
królowe, zbiorem dla każdego wyboru jest n2 możliwych pól na
szachownicy. Kryterium jest takie, że królowe nie mogą się
wzajemnie szachować.
Algorytmy z powrotami sÄ… zmodyfikowanym przeszukiwaniem
drzewa ( z korzeniem ) w głąb. Na początku odwiedzamy korzeń, a
poz
niej po przejściu do węzła przeglądane są wszystkie węzły
potomne.
Generalnie przeszukiwanie nie wymaga określonego porządku
odwiedzania węzłów, ale wygodniej jest gdy przeszukiwane są węzły
od lewej do prawej.
Przykład przeszukiwania drzewa w głąb z węzłami ponumerowanymi
w kolejności ich odwiedzania:
Węzły są ponumerowane w kolejności ich odwiedzania. Jak widać
podczas wyszukiwania w głąb przechodzi się po ścieżce tak głęboko,
jak jest to możliwe, aż do osiągnięcia ślepego zaułka. Następnie
wracamy do węzła z niodwiedzonymi węzłami potomnymi i znów
przechodzimy w głąb tak daleko, jak jest to możliwe.
Rozważmy ustawienie 4 królowych na szachownicy 4 × 4.
Problem można rozwiązać przez ustawienie królowych w kolejnych
wierszach i sprawdzanie, która kombinacja kolumn daje prawidłowe
rozwiÄ…zanie. Daje to 4 × 4 × 4 × 4 = 256 potencjalnych rozwiazaÅ„.
Można tworzyć potencjalne rozwiązania przez tworzenie drzewa:
w węzłach drzewa z poziomu 1 będą zapisane kolumny wybrane dla
pierwszej królowej, w węzłach poziomu 2 wybrane kolumny dla
drugiej królowej, etc.
Ścieżka od węzła głównego do liścia jest potencjalnym rozwiazaniem.
Liść to jest węzeł bez węzłów potomnych. Drzewo takie nazywamy
drzewem przestrzeni stanów.
Fragment drzewa przestrzeni stanów pokazano poniżej:
Całe drzewo ma 256 liści, po jednym dla każdego potencjalnego
rozwiązania. W każdym węz
le przechowywana jest para liczb ,
oznaczająca, że królowa z wiersza i jest umieszczona w kolumnie j.
Aby określić rozwiązanie, węzły są odwiedzane zgodnie z metodą
przeszukiwania w głąb, w którym węzły pochodne są odwiedzane od
strony lewej do prawej.
Pierwsze sprawdzane scieżki to:
[<1.1><2.1><3.1><4.1>]
[<1.1><2.1><3.1><4.2>]
[<1.1><2.1><3.1><4.3>]
[<1.1><2.1><3.1><4.4>]
[<1.1><2.1><3.2><4.1>]
Algorytm z powrotami jest algorytmem, w którym po zorientowaniu
się, że węzeł prowadzi do ślepego zaułka, wracamy do węzła
nadrzędnego i kontynuujemy wyszukiwanie od następnego węzła.
Węzeł nazywamy nieobiecującym, gdy w czasie jego odwiedzania
można określić, że nie może on doprowadzić do rozwiązania
(przykład poniżej).
W przeciwnym razie węzeł jest nazywany obiecującym.
Algorytm z powrotami polega na wykonywaniu przeszukiwania w
głąb drzewa przestrzeni stanów, aby sprawdzić czy węzeł jest
obiecujący, czy nie. Jeżeli węzeł nie jest obiecujący, wracamy do
węzła nadrzędnego.
Ogólny algorytm z powrotami:
void checknode (node v)
{
node u;
if (promising(v))
if(istnieje rozwiÄ…zanie dla v)
drukuj rozwiÄ…zanie;
else
for(każdy węzeł pochodny u węzła v)
checknode(u);
}
Algorytm z powrotami jest identyczny jak przeszukiwanie w głąb,
poza tym, że węzły pochodne są odwiedzane tylko w przypadku, gdy
węzeł macierzysty jest obiecujący i nie znaleziono w nim rozwiązania
Dla problemu n-królowych funkcja promising zwraca false , jeżeli
węzeł i dowolny z jego przodków oznaczają umieszczenie królowej w
tej samej kolumnie lub przekÄ…tnej (oznaczenie x na rys.).
Algorytm z powrotami sprawdza 27 węzłów w celu odszukania
rozwiązania, bez zastosowania tego algorytmu trzeba sprawdzić 155
wezłów w celu odszukania tego samego rozwiązania.
Nieefektywność w ogólnym algorytmie z powrotami (procedura
checknode) wynika z faktu, że sprawdzamy czy węzeł jest obiecujący,
po przekazaniu go do procedury. Rekordy aktywacji wezłów
nieobiecujących są niepotrzebnie odkładane na stos rekordów
aktywacji.
Algorytm ze sprawdzeniem czy wezeł jest obiecujący, przed
wywołaniem rekurencyjnym, wyglądałby następujaco:
void expand (node v)
{
node u;
for (każdy węzeł pochodny u węzła v)
if (promising(u))
if (istnieje rozwiazanie dla u)
drukuj rozwiazanie;
else
expand(u);
}
Wersja poprzednia jest łatwiejsza do zrozumienia, gdyż wszystkie
operacje są wykonywane w checknode tzn. : sprawdzanie czy węzeł
jest obiecujący; jeżeli jest obiecujący to czy zawiera rozwiązanie;
drukowanie rozwiÄ…zania.
Problem n-królowych
Funkcja sprawdzająca, czy węzeł jest obiecujący, musi sprawdzać, czy
dwie królowe są w tej samej kolumnie lub na tej samej przekątnej.
Sprawdzenie kolumny to:
col(i) = col(k)
gdzie col(i) jest kolumną w której jest umieszczona królowa z i-tego
wiersza.
Sprawdzenie przekÄ…tnej to:
col(i) - col(k) = i  k lub col(i) - col(k) = k  i
Przykładowo:
col(6)  col(3) = 4-1 = 3 = 6-3
col(6)  col(2) = 4-8 = -4 = 2-6
Algorytm z powrotami dla problemu n-królowych
Problem: umieść n królowych na szachownicy w taki sposób, żeby
żadne dwie królowe nie znalazły się w tym samym wierszu, tej samej
kolumnie oraz na tych samych przekÄ…tnych.
Dane wejściowe: dodatnia liczba całkowita n.
Wynik: wszystkie możliwe sposoby na umieszczenie n królowych na
szachownicy n×n tak, aby siÄ™ wzajemnie nie szachowaÅ‚y. Każdy
wynik cząstkowy składa się z tablicy liczb całkowitych col,
indeksowanych od 1 do n, gdzie col(i) jest kolumną, w której
umieszczona została królowa z wiersza i.
void queens (index i)
{
index j;
if (promising(i) )
if(i= = n)
cout<< od col[i] do col[n];
else
for(j=1;j<=n;j++){//Sprawdzenie czy królow
col[i+1] = j; //w i+1-tym wierszu moze
queens(i+1); //byc ustawiona w kazdej
//z n kolumn
}
}
bool promising (index i)
{
index k;
bool switch;
k=1;
switch = true; //Sprawdz
czy jakas
//krolowa szachuje królową
while(k if(col[i]==col[k] || abs(col[i]-col[k])==i-k)
switch = false;
k++;
}
return switch;
}
Algorytm powyższy tworzy wszystkie rozwiązania problemu n-
królowych. Przerobienie programu tak, aby zatrzymywał się po
znalezieniu pierwszego rozwiazania, jest proste.
W analizie algorytmu należy określić ilość sprawdzonych węzłów
jako funkcję wartości n, czyli liczby królowych. Górną granicę liczby
węzłów w drzewie przestrzeni stanów można dośc łatwo policzyć.
Drzewo zawiera 1 węzeł na poziomie 0, n węzłów na poziomie 1, n2
węzłów na poziomie 2 oraz nn na poziomie n.
Całkowita liczba węzłów wynosi
1+n+n2+n3+& +nn = (nn+1  1) / (n  1)
Przykladowo, dla n=8 mamy
(88+1  1) / (8  1) = 19 173 961 węzłów
Analiza ta jest nie w pełni użyteczna bo zadaniem algorytmu z
powrotami jest uniknięcie sprawdzania wielu z tych węzłów.
Można również określić górną granicę ilości węzłów obiecujących
(dla n=8). Pierwsza królowa może być umieszczona w dowolnej z
ośmiu kolumn, druga może być umieszczona w jednej z siedmiu
kolumn. Po ustawieniu drugiej królowej dla trzeciej zostanie do
wyboru sześć kolumn. Dlatego mamy co najwyżej:
1 + 8 + 8×7 + 8×7×6 + 8×7×6×5 + & + 8! = 109 601
obiecujących węzłów.
Ogólnie dla dowolnego n mamy co nawyżej
1 + n + n(n-1) + n(n-1)(n-2) + & + n! obiecujących węzłów.
Analiza ta nie jest pełna, gdyż po pierwsze nie bierze pod uwagę
sprawdzania przekątnych, po drugie całkowita liczba odwiedzanych
węzłów zawiera zarówno węzły obiecujące, jak i nieobiecujące.
NajprostszÄ… metodÄ… byloby uruchomienie programu na komputerze i
zliczanie odwiedzanych węzłów.
 n Algorytm A Algorytm B Algorytm z powrotami
________________________________________________________________
Liczba węzłów Liczba potencjalnych Liczba węzłów Liczba
sprawdzanych rozwiązań n! sprawdzanych znalezionych
(bez powrotów) (rozne kolumny) (z powrotami) węzłów obiec.
________________________________________________________________
4 341 24 61 17
8 19 173 961 40 320 15 721 2057
12 9.73×1012 4.79×108 1.01×107 8.56×105
14 1.20×1016 8.72×1010 3.78×108 2.74×107
Oczywiście, uruchamianie algorytmu w celu określenia jego
efektywności nie jest faktyczną analizą. Zadaniem analizy jest
określenie jak efektywny jest algorytm, jeszcze przed jego
uruchomieniem.
Co można zrobić w takiej sytuacji ?
Algorytmy Monte-Carlo
Drzewa przestrzeni stanów dla algorytmów z powrotami mają
wykładniczo lub szybciej roznąca liczbę węzłów. Warto zauważyć, że
jeśli mamy dwa przypadki z taką samą wartością n, jeden z nich może
wymagać sprawdzenia kilku węzłów, natomiast inne wymagają
sprawdzenia całego drzewa przestrzeni stanów.
Jeżeli oszacujemy, jak efektywny jest dany algorytm z powrotami dla
danego przypadku, możemy zdecydować, czy zastosowanie go jest
sensowne.
Algorytm Monte-Carlo to algorytm probabilistyczny. Jest to taki
algorytm, w którym następna wykonywana instrukcja jest czasami
określana w sposób losowy, zgodnie z pewnym rozkładem losowym.
Algorytm deterministyczny to taki, w którym przedstawiony
przypadek nie może mieć miejsca.
Algorytm Monte-Carlo pozwala oszacować spodziewaną wartość
zmiennej losowej, zdefiniowanej w przestrzeni próbek, na podstawie
średniej wartości losowych próbek z tej przestrzeni. Nie ma
gwarancji, że to oszacowanie jest bliskie właściwej wartości
oczekiwanej, ale prawdopodobieństwo, że jest bliskie, zwiększa się ze
wzrostem czasu działania algorytmu (ilosci uruchomień algorytmu).
Jak wykorzystać algorytm Monte-Carlo do oszacowania efektywności
algorytmu z powrotami ?
Generujemy w drzewie  typową ścieżkę , składajacą się z węzłów,
które powinny być sprawdzone w danym przypadku, a nastepnie
szacujemy liczbę węzłów, odgałęziających się od tej ścieżki.
Oszacowanie to daje w wyniku szacunkową liczbę węzłów, które
należy sprawdzić w celu znalezienia wszystkich rozwiązań. Inaczej
mówiąc, jest to szacunkowa liczba węzłów w przeciętnym drzewie
stanów.
Muszą być spełnione dwa warunki:
" we wszystkich węzłach na tym samym poziomie drzewa
przestrzeni stanów powinna być używana ta sama funkcja
określająca, czy węzeł jest obiecujący
" węzły na tym samym poziomie w drzewie przestrzeni stanów
muszą mieć taka samą liczbę potomków.
Algorytm dla n-królowych spełnia te warunki.
Technika Monte-Carlo wymaga losowego generowania obiecujÄ…cego
potomka węzła, zgodnie z rozkładem normalnym, czyli generowania
liczb losowych.
Sposób realizacji:
" niech m0 będzie liczbą obiecujących potomków korzenia
" losowo generujemy obiecujący węzeł pochodny na poziomie 1.
Niech m1 będzie liczbą obiecujących potomków tego węzła.
" losowo wygeneruj obiecujący węzeł dla węzła uzyskanego w
poprzednim kroku. Niech m2 będzie liczbą obiecujących
potomków tego węzła.
& &
" Losowo wygeneruj obiecujący węzeł dla węzła uzyskanego w
poprzednim kroku. Niech mi będzie liczbą obiecujących
potomków tego węzła.
Proces jest kontynuowany, dopóki nie zostaną znalezione żadne
obiecujące węzły potomne. mi jest szacunkową średnią liczbą
obiecujących węzłów na poziomie i.
Niech ti = całkowita liczba potomków węzła na poziomie i
Wszystkie ti węzłów zostaje sprawdzone i tylko mi obiecujacych
węzłów potomnych ma sprawdzone węzły potomne. Szacunkowa
liczba węzłów sprawdzonych przez algorytm z powrotami w celu
wyszukania wszystkich rozwiązań wynosi
1+ t0 + m0 t1 + m0m1t2 + m0m1& mi-1ti + ..
.
Ogólny algorytm obliczający tą średnią może wygladać następująco
( mprod = m0m1& mi-1 ) .
Szacowanie Monte-Carlo
Problem: oszacuj efektywność algorytmu z powrotami, korzystając z
algorytmu Monte Carlo.
Dane wejściowe: problem rozwiazywany przez algorytm z
powrotami.
Wynik: szacunkowa liczba węzłów w przyciętym drzewie przestrzeni
stanów generowanych przez algorytm, który jest liczbą węzłów, jaką
musi sprawdzić algorytm w celu znalezienia wszystkich rozwiązań
danego przypadku.
int estimate ()
{
node v;
int m,mprod,t,numnodes;
v = korzeń drzewa stanów;
numnodes = 1;
m=1;
mprod=1;
while (m!=0) {
t=liczba potomków v;
mprod=mprod*m;
numnodes=numnodes+mprod*t;
m=liczba obiecujacych potomków v;
if (m!=0)
v=losowo wybrany obiecujacy potomek v;
}
return numnodes;
}
Dla algorytmu problemu n-królowych może to wyglądać.
________________________________________________________
Oszacowanie metodÄ… Monte Carlo dla algorytmu z powrotami 
problem n-królowych
Problem: oszacowanie efektywności algorytmu
Dane wejściowe: dodatnia wartość całkowita n
Wynik: szacunkowa liczba węzłów w przyciętym drzewie przestrzeni
stanów, generowanym przez algorytm  liczba węzłów, jakie muszą
zostać sprawdzone przez algorytm przed wyszukaniem wszystkich
sposobów na ustawienie n królowych na szachownicy n× n tak, aby
się wzajemnie nie szachowały.
int estimate_n_queens (int n)
{
index i,j,col[1..n];
int m,mprod,numnodes;
set_of_index prom_children;
i=0;
numnodes=1;
m=1;
mprod=1;
while (m!=0 && i!=n) {
mprod=mprod*m;
numnodes=numnodes+mprod*n;//Liczba wezłów t
i++; // wynosi n
m=0;
prom_children="; //Inicjalizacja zbioru
for(j=1;j<=n;j++){ //obiecujacych potomkow
col[i]=j; //pustym zbiorem
if(promising(i)){ //Okreslenie obiecuj.
m++; //potomkow.
prom_children=prom_children *" {j};
}
}
if (m!=0){
j= losowy wybór z prom_children;
col[i]=j;
}
}
return numnodes;
}
Algorytm Monte Carlo można uruchomić wielokrotnie i jako
właściwą wartość wykorzystać średnią z otrzymanych wyników.
Trzeba zauwazyć, że choć prawdopobieństwo uzyskania dobrego
oszacowania jest wysokie przy wielokrotnym uruchomieniu to nigdy
nie mamy gwarancji, że jest to dobre oszacowanie.
Oszacowanie uzyskiwane dla dowolnego przypadku zastosowania
metody Monte Carlo jest prawdziwe tylko dla tego pojedynczego
przypadku. Zdarza się, że gdy mamy dwa różne przypadki dla takiej
samej wartości n, jeden może wymagać sprawdzenia niewielkiej
liczby węzłów, natomiast drugi przejrzenia całego drzewa przestrzeni
stanów.