2. Projektowanie algorytmu

W tym rozdziale skoncentrujemy się na przedstawieniu systematycznych metod budowania algorytmów, za pomocą których rozwiązuje się rozmaite problemy. Projektowanie algorytmów jest sztuką, której najlepiej uczyć się na przykładach. Jednakże wiele algorytmów opiera się na jednym z kilku schematów i poznawszy te schematy, można rozwiązywać nowe problemy znanymi metodami. Istnieją cztery obszerne grupy algorytmów - bieżący rozdział zawiera proste przykłady z każdej z nich. W dalszej części książki będziemy rozpatrywać te grupy, konstruując algorytmy związane z sortowaniem, listami, drzewami i grafami.

2.1. Algorytmy zachłanne

Algorytm zachłanny (ang. greedy algorithm) wykonuje działanie, które wydaje się najlepsze w danej chwili, nie uwzględniając tego, co się może dziać w przyszłości. Zaletą algorytmu zachłannego jest to, że nie traci się tu czasu na rozważanie, co się może zdarzyć później. Zadziwiające jest, że w wielu sytuacjach daje on optymalne rozwiązanie. Rozpatrzmy dla przykładu problem kasjera, który ma wydać resztę, będącą dowolną kwotą między 0,01$ a 0,99$, przy użyciu minimalnej liczby monet. Jednym z możliwych rozwiązań jest najpierw użycie monety o największej dopuszczalnej wartości, redukując w ten sposób problem do wypłacenia mniejszej kwoty. Aby na przykład wydać 0,94 $, kasjer wypłaci półdolarówkę (zostawiając do zapłacenia 0,44 $), następnie ćwierćdolarówkę (zostaje 0,19 $), dziesięciocentówkę (0,09 $), pięciocentówkę (0,04 $) i w końcu cztery jednocentówki - w sumie osiem monet. Jest to minimalna liczba i faktycznie algorytm zachłanny jest optymalny dla monet amerykańskich (chociaż niekoniecznie dla innych systemów monetarnych).
Techniczną nazwą metody wyboru następnego kroku jest decyzja lokalnie optymalna. Inną nazwą tej metody, stosowaną w dziedzinie sztucznej inteligencji, jest "podchodzenie na wzgórze". Rozważmy na przykład problem znalezienia maksymalnej wartości przyjmowanej przez jakąś funkcję. Jednym ze sposobów rozwiązania jest rozpoczęcie od pewnej liczby i kolejne powiększanie jej o ustaloną wielkość tak
36
długo, jak długo wartość funkcji w tym punkcie wzrasta. Gdy wartość funkcji zaczyna się zmniejszać, przerywamy działanie i cofamy się do ostatniej pozycji. Chociaż metoda ta nie musi prowadzić do znalezienia globalnego maksimum (mogliśmy wystartować tuż przed niewielkim wzniesieniem), umożliwi przynajmniej znalezienie maksimum lokalnego.
Książka ta zawiera kilka przykładów, w których algorytm zachłanny jest optymalny. Algorytmami zachłannymi są między innymi algorytm Dijkstry znajdowania najkrótszych ścieżek w grafie i algorytm Kruskala znajdowania minimalnego drzewa rozpinającego.

2.2. Algorytmy oparte na strategii "dziel i zwyciężaj"

Inną metodą rozwiązywania problemu jest podzielenie go na mniejsze części tej samej postaci co problem pierwotny. Teraz te podproblemy można dalej dzielić na coraz mniejsze, używając tej samej metody, aż rozmiar problemu stanie się tak mały, że rozwiązanie będzie oczywiste lub będzie można użyć jakiejś innej efektywnej metody rozwiązania. Rozwiązania wszystkich podproblemów muszą być połączone w celu utworzenia rozwiązania całego problemu. Metoda ta nosi nazwę dziel i zwyciężaj i zazwyczaj jest implementowana z użyciem technik rekurencyjnych, omawianych w rozdziale 7. Jeśli problem redukuje się do jednego tylko podproblemu, to można zwykle skonstruować rozwiązanie iteracyjne. Niektóre problemy wymagają podziału na więcej niż dwa podproblemy.
Rozważmy prosty przykład znajdowania minimum w ciągu liczb. Alternatywą dla zwykłego, iteracyjnego rozwiązania jest podzielenie ciągu na dwie części (równej długości lub różniące się długością o 1), znalezienie minimum w każdej z nich, a następnie wzięcie minimum tych dwóch liczb jako najmniejszej liczby w całym ciągu. Ciąg możemy dzielić dopóty, dopóki nie będzie zawierał on tylko jednej liczby - wówczas będzie ona oczywiście najmniejsza w tym ciągu.
Jako bardziej złożony przykład rozważmy sortowanie ciągu liczb. Aby posortować ciąg liczb, możemy go, jak poprzednio, podzielić na dwie części w przybliżeniu równej długości, posortować je, a następnie połączyć dwa uporządkowane ciągi w posortowaną całość. Ostatnią fazę nazywamy scalaniem (ang. merge), a ta metoda sortowania nosi nazwę sortowania przez scalanie (ang. mergesort) i jest szczegółowo omówiona w rozdziale 11. Aby scalić dwa niepuste ciągi, porównujemy pierwsze elementy obu ciągów i przenosimy mniejszy z nich do trzeciego ciągu. Powtarzamy ten proces dopóty, dopóki jeden z ciągów nie stanie się pusty. Pozostały ciąg dołączamy wtedy na koniec nowego ciągu, co kończy operację scalania. Aby posortować dwa ciągi, możemy znowu podzielić każdy na dwie części, posortować je i scalić. Możemy to powtarzać tak długo, aż nasz ciąg będzie pusty albo jednoelementowy.
Zamiast dzielić początkowy ciąg na połowy, moglibyśmy rozbić go na dwa podciągi: jeden zawierający wszystkie małe liczby, a drugi - wszystkie duże. Aby zdefiniować, co jest duże, a co małe, wybierzemy dowolną liczbę i powiemy, że wszystkie
37
liczby nie większe od niej są małe, a wszystkie większe - duże. W rzeczywistości dzielimy ciąg na trzy podciągi: liczby mniejsze od wybranej, równe jej i większe od niej. Środkowy ciąg nie musi być sortowany. Po dokonaniu podziału (nie twierdzimy już, że podciągi będą równych rozmiarów - znalezienie mediany, dzielącej ciąg na połowę, jest zbyt pracochłonne) sortujemy ciąg małych i ciąg dużych liczb niezależnie, rozbijając je na mniejsze podciągi, a następnie sklejając fragmenty z powrotem. W algorytmie tym, zwanym sortowaniem szybkim (ang. quicksort), skomplikowaną częścią jest faza podziału. Połączenie podciągów polega po prostu na ich sklejeniu, ponieważ wszystkie liczby w pierwszym podciągu są mniejsze niż w drugim, a te z kolei są mniejsze niż liczby w trzecim podciągu. Tak jak przy sortowaniu przez scalanie, możemy przestać dzielić podciąg, gdy jest on pusty albo jednoelementowy, a więc już uporządkowany. Jednak w praktyce często lepiej zatrzymać się na dłuższym ciągu i użyć innej metody sortowania do jego uporządkowania.
Aby metodę "dziel i zwyciężaj" można było stosować do tworzenia algorytmów, podproblemy muszą być tej samej postaci co problem pierwotny, żeby można je było dzielić w ten sam sposób, i muszą też - oczywiście - być mniejszego rozmiaru. Rozmiar jest pewną miarą problemu; w sortowaniu jest to liczba elementów do uporządkowania. W sortowaniu szybkim możemy zapewnić, że oba ciągi - małych i dużych liczb - będą mniej liczne od ciągu początkowego, jeśli do podziału wybierzemy jedną z liczb tego ciągu.
Rysunek 2.1 ilustruje problem znalezienia pary punktów leżących najbliżej siebie na płaszczyźnie ograniczonej prostokątem. Rozwiązując zadanie metodą "dziel i zwyciężaj", dzielimy płaszczyznę tak, że połowa punktów znajduje się na jednej półpłaszczyźnie, a połowa na drugiej. Teraz znajdujemy parę najbliżej siebie leżących punktów na każdej półpłaszczyźnie. Albo któraś z tych par jest parą najbliżej siebie leżących punktów w całym zbiorze, albo na jednej półpłaszczyźnie istnieje punkt leżący bliżej innego punktu umieszczonego na drugiej półpłaszczyźnie niż punkty w każdej z tych par. Wystarczy zatem sprawdzić, czy na granicy półpłaszczyzn nie ma pary najbliżej siebie leżących punktów.

Rys. 2.1. Znajdowanie pary najbliżej siebie leżących punktów na płaszczyźnie
38
Przy przeszukiwaniu granicy musimy sprawdzać jedynie punkty znajdujące się blisko brzegu. Dokładniej, jeśli dla jednej z dwóch znalezionych par punktów odległość między tymi punktami wynosi 6, to żaden punkt leżący w odległości większej niż 8 od granicy nie może być położony bliżej niż o 8 od punktu z drugiej strony, więc nie musi być sprawdzany. Możemy narysować dwie proste biegnące równolegle do granicy w odległości 8 po obu jej stronach i sprawdzać tylko punkty wewnątrz pasa między nimi, jak to widać na rysunku 2.2. W rzeczywistości dla każdego punktu umieszczonego blisko granicy może być co najwyżej sześciu kandydatów na najbliższego sąsiada po drugiej stronie. Gdyby było ich więcej, dwa punkty spośród nich musiałyby być bliżej siebie niż wynosi odległość 8, a to jest niemożliwe. Jeśli zręcznie zorganizujemy obliczenia, to możemy sprawdzić wszystkie punkty w czasie liniowym, co daje w efekcie szybki algorytm.

Rys. 2.2. Znajdowanie pary najbliżej siebie leżących punktów w pobliżu granicy

Często problem można rozwiązać metodą "dziel i zwyciężaj", ale algorytm okazuje się nieefektywny, ponieważ dużą część pracy powtarza się przy rozwiązywaniu podproblemów. Sposób na uniknięcie tego omawiamy w następnym podrozdziale.

2.3. Algorytmy oparte na programowaniu dynamicznym

Przypuśćmy, że chcemy obliczać liczby Fibonacciego metodą "dziel i zwyciężaj". Liczby Fibonacciego F#1, F#2, F#3, ... są zdefiniowane w następujący sposób:

jeśli F(i) = {1, jeśli i=1; 1, jeśli i=2; F(i-2) + F(i-1) jeśli i>2;

Aby obliczyć F(5), obliczamy F(3) i F(4), a potem dodajemy wyniki. Aby obliczyć F(3), obliczamy F(2) i F(1) - obydwie równe 1, i dodajemy je, otrzymując F(3)=2.
39
Następnym problemem jest obliczenie F(4). Użycie tej samej metody wymaga ponownego obliczenia F(2) i F(3). Zatem F(3) będzie obliczane 2-krotnie. Podczas obliczania F(6) wartość F(3) będzie wyliczana 3-krotnie, a dla F(7) - 5-krotnie. Ogólnie, jeśli obliczamy F(n), to wartość F(3) obliczymy F(n-2) razy. Liczba ta rośnie wykładniczo. Widać, że lepiej byłoby zachować wyniki wcześniejszych obliczeń i wykorzystać je, zamiast obliczać ponownie. Faktycznie, kolejno obliczając i zapamiętując w tablicy F(1), F(2), F(3), ..., zaoszczędzilibyśmy mnóstwo czasu.
Problem Fibonacciego jest jednowymiarowym przykładem programowania dynamicznego. Programowanie dynamiczne można zastosować, kiedy problem daje się podzielić na wiele podproblemów, możliwych do zakodowania w jedno-, dwu- lub wielowymiarowej tablicy, w taki sposób, że w pewnej określonej kolejności można je wszystkie (a więc i cały problem) efektywnie rozwiązać. Gdy mamy do czynienia z problemem jednowymiarowym, nie ma zwykle dużego wyboru, jeśli idzie o kolejność, chociaż niekiedy wygodniej bywa poruszać się od strony prawej do lewej zamiast od lewej do prawej. Przy problemach dwuwymiarowych natomiast czasem lepiej przetwarzać informacje wzdłuż wierszy, czasem wzdłuż kolumn, a nawet wzdłuż przekątnych.
Jako drugi przykład programowania dynamicznego rozważmy problem plecakowy (ang. knapsack problem). Mamy plecak o określonej pojemności i nieograniczoną liczbę przedmiotów różnych typów. Każdy typ przedmiotu ma ustalony rozmiar i wartość. Problem polega na takim wyborze przedmiotów do wypełnienia plecaka, by ich łączna wartość była jak największa (suma rozmiarów zabranych przedmiotów nie może przewyższać pojemności plecaka). Aby obliczyć największą możliwą łączną wartość przedmiotów, które można spakować do plecaka o pojemności k, wyobraźmy sobie, że mamy taki optymalnie spakowany plecak i wyjmujemy z niego pierwszy przedmiot. Jeśli ma on rozmiar s, to sytuacja jest teraz taka, jakbyśmy mieli plecak o pojemności k -s, wypełniony optymalnie. Ponieważ tak naprawdę nie wiemy, jak najlepiej spakować plecak o pojemności k, więc nie możemy wiedzieć, ile wynosi s. Zamiast tego rezerwujemy w plecaku miejsce na przedmiot pierwszego typu, wypełniamy resztę plecaka (optymalnie), a potem wkładamy przedmiot pierwszego typu i patrzymy, jaki wyszedł łączny koszt. Następnie zaczynamy od nowa, zostawiając miejsce na przedmiot drugiego typu, wypełniając plecak i dokładając przedmiot drugiego typu i tak dalej dla wszystkich typów przedmiotów. Rozwiązaniem naszego problemu jest plecak o największej łącznej wartości spośród wypełnionych tym sposobem. Innymi słowy, jeśli przez knapsack(k) oznaczymy łączną wartość przedmiotów optymalnie wypełniających plecak rozmiaru k, to jest ona równa maksimum spośród knapsack(k-s#1,) + c#1, knapsack(k-s#2) + c#2, ..., gdzie s#1, s#2, ... to rozmiary poszczególnych typów przedmiotów, a c#1, c#2, ... to ich wartości. Aby jednak rozwiązywać te podproblemy efektywnie, lepiej zacząć od samego dołu, od plecaka o pojemności 0, i rozważać kolejno pojemności aż do k, zapamiętując rozwiązania podproblemów w miarę ich obliczania, tak jak w problemie Fibonacciego. Kod rozwiązania problemu plecakowego jest przedstawiony na rysunku 2.3.
40
int maxKnapsack(int k)
{
int knapsack[maxSack], max, i, type, total;
int size[maxTypes], numTypes, cost[maxTypes];

knapsack[0] = 0;
for (i=1; i<=k; i++) {
max = -INT_MAX;++)
if (i-size[type]>=0) {
total = knapsack[i-size[type]]+cost[type];
if (maxmax = total;
}
knapsack[i] =max;
}
return knapsack[k] ;
}

Rys. 2.3. Rozwiązanie problemu plecakowego

Jako następny rozważmy problem obliczania liczby kombinacji. Liczba kombinacji (podzbiorów) r-elementowych ze zbioru n-elementowego, oznaczana , jest dana wzorem
(n po r) = (n!) / [r! * (n-r)!]

Do obliczania liczby kombinacji możemy użyć wzorów
(n po r) = 1, jeśli r=0 lub n=r
(n po r) = (n-1 po r) + (n-1 po r-1) dla 0,r,n

W rozwiązaniu opartym na programowaniu dynamicznym buduje się dwuwymiarową tablicę, której wiersze odpowiadają wartościom n, a kolumny - wartościom r.
Wartością zapisaną w n-tym wierszu i r-tej kolumnie będzie (n po r). Przy założeniu, że pozycja (0,0) jest w lewym górnym rogu tablicy, do obliczenia musimy znać wartość powyżej (n-1 po r-1) i na ukos w lewo do góry, (n-1 po r-1). Z tego powodu możemy wyliczać
41
kolejne wartości w tablicy wierszami. Najpierw obliczamy w pierwszym rzędzie wartość na pozycji (0,0), później w drugim rzędzie (1, 0), (1,1), następnie (2,0), (2,1), (2,2) i tak dalej, dopóki nie dojdziemy do szukanej kombinacji. Tak otrzymana tablica, zwana trójkątem Pascala, jest pokazana na rysunku 2.4.

n-kolumna ; r-wiersz
n\r 0; 1; 2; 3; 4
0 1
1 1; 1
2 1 ; 2; 1
3 1; 3; 3 ;1
4 1; 4; 6; 4; 1

Rys. 2.4. Trójkąt Pascala

Często porządek, w jakim trzeba obliczać elementy macierzy, bywa bardziej skomplikowany niż proste przechodzenie kolejnych wierszy. Zdarza się, że elementy muszą być przetwarzane wzdłuż kolejnych przekątnych.
Kilka przykładów algorytmów opartych na programowaniu dynamicznym przedstawiamy w poświęconym grafom rozdziale 10, w szczególności algorytm Warshalla obliczania domknięcia przechodniego grafu skierowanego i algorytm Floyda znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie.

2.4. Algorytmy z powrotami

Często możemy zdefiniować problem jako poszukiwanie jakiegoś rozwiązania wśród wielu możliwych przypadków. Przyjmijmy, że dana jest pewna przestrzeń stanów, przy czym stan jest sytuacją stanowiącą rozwiązanie problemu albo mogącą prowadzić do rozwiązania, oraz sposób przechodzenia od jednego stanu do drugiego. W problemie kasjera na przykład stanem jest zbiór monet. Zaczynamy od pustego zbioru i przechodzimy od stanu do stanu przez dodawanie monety do zbioru. Poprawnym rozwiązaniem jest zbiór monet, których łączna wartość jest równa żądanej kwocie. Problem kasjera polega na znalezieniu poprawnego rozwiązania przy użyciu minimalnej liczby monet. Czasami mogą istnieć stany, które nie prowadzą do rozwiązania.
Przykładami tego typu problemów są gry. Rozważmy partię gry w kółko i krzyżyk, warcaby czy szachy. Każda możliwa pozycja na planszy jest stanem. Przechodzimy od jednego stanu do drugiego przez przestawienie figury (w szachach i warcabach) lub postawienie X albo O (w grze w kółko i krzyżyk). Celem jest dojście (lub zmuszenie do tego przeciwnika) do zwycięskiej dla nas pozycji na planszy. W grze w kółko i krzyżyk rozwiązaniem są trzy krzyżyki (lub trzy kółka) ustawione w jednej linii, w szachach - mat, a w warcabach - plansza, na której nie ma pionków przeciwnika.
42
To, że gracze wykonują ruchy na przemian - a co jest dobrym ruchem dla jednego gracza, jest złe dla drugiego - jest istotne, ale nie będzie grało roli w rozważanych przez nas problemach.
Aby rozwiązać taki problem, musimy przeszukiwać przestrzeń stanów, przechodząc od jednego stanu do drugiego, aż znajdziemy poprawne rozwiązanie. Ponieważ dla każdego stanu może istnieć wiele dopuszczalnych ruchów, czyli wiele stanów, do których można dojść, możemy wybrać złe posunięcie. Jeśli wykonamy zły ruch i znajdziemy się w sytuacji bez wyjścia (nie osiągając poprawnego rozwiązania i nie mając więcej dopuszczalnych posunięć do wykonania), musimy cofnąć ostatni ruch i spróbować zrobić inny. Oto przewaga rozgrywania partii w głowie albo na komputerze nad rzeczywistą grą, gdzie cofanie ruchów nie należy do dobrych obyczajów. Jeśli cofnięcie ostatniego ruchu w dalszym ciągu nie prowadzi do rozwiązania, to cofamy ruch przedostatni i próbujemy dalej. Ta metoda nosi nazwę metody powrotów (ang. backtracking).
Metoda powrotów wymaga zapamiętywania wszystkich wykonanych ruchów czy też wszystkich odwiedzonych stanów, aby możliwe było cofanie posunięć. Stos, opisywany w rozdziale 6, jest idealną strukturą danych do przechowywania tego rodzaju informacji. Zamiast używać odrębnego stosu, moglibyśmy zaimplementować strategię opartą na powrotach z wykorzystaniem rekursji, omawianej w rozdziale 7.
Rozważmy następujący przykład algorytmu z powrotami. Po jednej stronie rzeki znajduje się trzech misjonarzy, dwóch ludożerców i łódka. Wszyscy chcą przeprawić się na drugi brzeg. Łódka może pomieścić jedną lub dwie osoby, a kierować nią musi misjonarz. Jest jeszcze jedno dodatkowe ograniczenie. Jeżeli w jakiejś chwili po którejkolwiek stronie rzeki będzie więcej ludożerców niż misjonarzy, to ci ostatni zostaną pożarci. Chcielibyśmy tego uniknąć. Problem polega na znalezieniu rozwiązania, które umożliwi wszystkim przebycie rzeki.
Każdą możliwą sytuację występującą w naszym problemie będziemy reprezentować przez liczbę misjonarzy (M), ludożerców (C) i łódek (B) na początkowym, powiedzmy, lewym brzegu rzeki. Okresy, kiedy łódka płynie między brzegami, stanowią sytuacje pośrednie i nie będziemy musieli ich reprezentować. Liczbę ludzi i łódek na prawym brzegu łatwo wyliczyć, znając sytuację na brzegu lewym: 3 - liczba misjonarzy, 2 - liczba ludożerców i 1 - liczba łódek. Możemy zatem reprezentować każdą możliwą sytuację bądź stan za pomocą trójki liczb. Zakodujemy stan w postaci jednej liczby całkowitej, traktując te trzy liczby jako jedną liczbę w zapisie czwórkowym: liczba misjonarzy na miejscu jedności, liczba ludożerców na miejscu czwórek, a liczba łódek na miejscu szesnastek. Zatem 3 misjonarzy, 2 ludożerców i 1 łódkę reprezentuje liczba 123#4. Podstawa wynosi cztery, ponieważ może być od 0 do 3 misjonarzy. Musimy zwrócić uwagę, że w ten sposób dają się reprezentować również niedopuszczalne stany, jak 132.
Podczas rozwiązywania tej łamigłówki musimy zapamiętywać wszystkie stany, przez które przechodziliśmy, poczynając od stanu wyjściowego aż do bieżącej pozycji, aby można było się wycofać, jeśli będzie trzeba. Posłużymy się do tego celu tablicą position, wraz z licznikiem n, oznaczającym liczbę stanów w tablicy.
43
Sytuacja początkowa jest zapisana w position[0], a position[n-1] reprezentuje stan bieżący. Rysunki 2.5 i 2.6 zawierają kod programu rozwiązującego nasz problem. Niezbędna jest nam dodatkowa informacja, jakie stany znajdują się aktualnie w tablicy position, aby nie powracać do stanu, przez który już przechodziliśmy, co powodowałoby zapętlenie programu. Użyjemy do tego drugiej tablicy, visited, w której będziemy wstawiać 1 w miejsca odpowiadające stanom znajdującym się w tablicy position.

#include
#include

#def ine MIS 1
#define CAN 4
#define BOAT 16
#define ALL BOAT+2*CAN+3*MIS
#def ine NONED
#defineSUBSET(x,y) ( (x) %4<=(y) %4 && (x) /4%4<= (y) /4%4 && (x) /16<= (y) 716 )
int n, position[ALL+1] , visited [ALL+1] ;

void printSide (int p)
{
printf ( "%*dM %dC %dB\n" , n+1 , p%4 , (p/4)%4, p/16);
}
int validMove(int pos1 , intpos2)
/* Zwraca 1 , jeżeli ruch z pos1 do pos2 jest legalny, a pos2 jest stanem poprawnym i dotychczas nie odwiedzonym. W przeciwnym razie zwraca 0. */
{
int di f f = (SUBSET (pos2 , pos1 ) ?pos1-pos2 : /* różnica między stanami */
(SUBSET(pos1, pos2) ? pos2-pos1 :0) ) ;
int mis2 = pos2%4 ; /* liczba misjonarzy w pos2 */
int can2 =pos2/4%4; /* liczba ludożerców w pos2 */
return
{ ! visited[pos2] /* stan dotychczas nie odwiedzony */
&& (diff==BOAT+MIS | | dif f==BOAT+MIS+CAN | | dif f==BOAT+2*MIS)
/* ruch jest dopuszczalny */
&& can2 <= 2 /* w pos2 jest co najwyżej dwóch ludożerców */
&& (mis2 == O | | can2 <= mis2)
/* misjonarze na lewym brzegu nie będą pożarci */
&& (3-mis2 == O | | 2-can2 <= 3-mis2) } ;
/* na prawym brzegu też */
}

Rys. 2.5. Problem misjonarzy i ludożerców
44

int main ( )
{
position[0] =ALL; /* sytuacja początkowa */
visited[ALL] = 1;
printSide (position[0]> ;
position[l] = NONE; /* zacznij od pierwszego z możliwych następnych ruchów */
n= 1;
while (position[n-l] !=NONE) {
while (position [n] <=ALL && ! validMove (position[n-1], position[n]) )
position[n]++; /* powtarzaj , aż znajdziesz dopuszczalny następny ruch lub brak ruchów */
i f (position[n]<=ALL) { /* istnieje dopuszczalny następny ruch */
visited[position[n]] = 1 ; /* zaznacz, że jest rozważany */
printSide (position[n]) ;
position[++n] = NONE; /* uczyń następny po nim ruch pierwszym możliwym */
}
else { /* nie ma dopuszczalnego następnego ruchu */
visited[position[--n]] = 0; /* zmiana poprzednika bieżącego stanu, powrót */
if (n==0) return 0;
position[n]++; /* zmiana na kolejny następnego ruchu z przedostatniego stanu */
}
}
return 1;
}

Rys. 2.6. Problem misjonarzy i ludożerców (cd.)

Aby wykonać jeden ruch, rozważamy kolejno wszystkie możliwe stany od NONE (nic nie pozostało na lewym brzegu) do ALL (wszystko znajduje się na lewym brzegu). Kiedy znajdziemy stan, który jest poprawny (żaden misjonarz nie jest zjedzony) i do którego można dojść ze stanu bieżącego (uwzględniając ograniczenia związane z łódką), dodajemy go do tablicy. Powtarzamy to dopóty, dopóki nie dojdziemy do końcowego stanu NONE albo nie znajdziemy się w stanie, z którego nie można wykonać dopuszczalnego ruchu. W tym ostatnim przypadku cofamy się, usuwając ostatni stan z tablicy (zmniejszamy n i uaktualniamy tablicę visited), po czym próbujemy wykonać kolejny ruch z bieżącego stanu, jeśli taki ruch jest możliwy. Następny rozważany stan umieszczamy w positionfn], ponieważ tu właśnie będzie zapamiętany, jeśli przejście do niego od stanu bieżącego okaże się dopuszczalne. Tablica i licznik stanowią w rzeczywistości prostą implementację stosu, omawianego w rozdziale 6.
Zaprezentowane rozwiązanie nie jest najefektywniejsze, ale ilustruje, jak wykorzystać metodę powrotów w rozwiązywaniu problemu. Moglibyśmy usprawnić algorytm, wykonując jedynie dopuszczalne ruchy z danego stanu, zamiast przeglądać
45
wszystkie stany i sprawdzać, które z nich są dozwolone. Nasz program wypisuje ciąg analizowanych stanów, przesuwając początek napisu w prawo, gdy znajdzie dopuszczalny ruch, w lewo zaś, gdy następuje powrót. Efekt wykonania programu jest następujący:

3M 2C 1B
2M 1C 0B
3M 1C 1B
1M 1C 0B
2M 1C 1B
1M 0C 0B
3M 0C 1B
0M 1C 0B
1M 1C 1B
0M 0C 0B

Z powyższego wydruku widzimy, że znalezienie rozwiązania wymagało jednego kroku powrotnego, ponieważ stan z jednym misjonarzem, bez ludożerców i łódki zaprowadził w ślepą uliczkę.
Zazwyczaj problemy nie są aż tak proste. Stanów mogą być tysiące lub miliony i bezpośrednie zastosowanie metody powrotów, mogącej prowadzić do odwiedzenia wszystkich stanów, będzie zbyt kosztowne. Dla niektórych problemów inteligentny wybór następnego posunięcia może znacznie poprawić efektywność algorytmu. Wybór taki umożliwia funkcja oceniająca, która dla danego stanu oblicza wartość wskazującą, jaka jest szansa na to, że stan ten prowadzi do rozwiązania, lub też jak dobre rozwiązanie można zeń osiągnąć, jeżeli szukamy optymalnego rozwiązania. Istnieją metody, w których wykorzystuje się funkcje oceniające do takiej organizacji przeszukiwania, by uniknąć przeglądania nieistotnych fragmentów przestrzeni stanów.
Będziemy analizować kilka problemów, do rozwiązania których stosuje się metodę powrotów, przy omawianiu problemu ośmiu hetmanów w rozdziale 7 oraz problemu planowania rozkładu zajęć w rozdziale 10.

2.5. Ćwiczenia

1. Przypuśćmy, że w problemie kasjera jedynymi monetami są ćwierćdolarówka (0,25$), piętnastocentówka (0,15$) i jednocentówka (0,01$). Czy algorytm zachłanny zawsze daje optymalne rozwiązanie?
2. Rozważmy problem znalezienia wyjścia z labiryntu. Przypuśćmy, że wiadomo, gdzie jesteśmy i gdzie jest wyjście. Jak wyglądałoby zachłanne rozwiązanie tego problemu. Czy jest ono skuteczne?
3. Rozważmy ten sam problem co w zadaniu 2. Jak wyglądałoby rozwiązanie metodą powrotów?
46
4. Zaprojektuj algorytm typu "dziel i zwyciężaj" do znajdowania n-tej co do wielkości spośród m liczb, gdzie n jest zmienną. Rozważ adaptację algorytmu sortowania szybkiego do swojego rozwiązania.
5. Dany jest zbiór osób, z których każda chce wymienić uścisk dłoni z wszystkimi pozostałymi. Jak wykorzystałbyś zasadę "dziel i zwyciężaj" do ustalenia kto, kiedy i czyją rękę powinien uścisnąć?
6. Opisz oparte na programowaniu dynamicznym rozwiązanie problemu rozkładu na czynniki pierwsze wszystkich liczb całkowitych od 1 do 1000.
7. Jak rozwiązać problem kasjera za pomocą programowania dynamicznego?
8. Zaprogramuj rozwiązanie problemu misjonarzy i ludożerców dla przypadku 4 misjonarzy i 3 ludożerców.

Bibliografia

[1] Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algońthms. Reading, MA, Addison-Wesley 1983.
[2] Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych. Warszawa, PWN 1983.
[3] Bellman R.E.: Dynamic Programming. Princeton, NJ, Princeton University Press 1957.
[4] Dreyfus S.E, Law A.M.: The Art and Theory of Dynamic Programming. New York, NY, Academic Press 1977.
[5] Nilsson N.J.: Problem-Solving Methods in Artificial Intelligence. New York, NY, McGraw-Hill 1971.
[6] Preparata F.P., Shamos M.L: Computational Geometry: An Introduction. New York, NY, Springer-Verlag 1985.