[ Pobierz całość w formacie PDF ]
.Tak też jest i w naszym przykładowym labiryncie - są to dwu-, trzy- lub czteroelementowe zbiory o wartościach różniących się o 1, lub o 5 od wartości i.Natomiast zbiory Oi są albo z góry zadane i na ogół nie zmieniają się w trakcie realizacji algorytmu, albo (w przypadku bardziej ogólnym) są generowane dla punktu i (a często i dla najbliższego jego otoczenia), na bieżąco w trakcie realizacji algorytmu.Tak się dzieje, na przykład, w większości zręcznościowych gier komputerowych.Rozwiązaniem częściowym jest częściowy wektor rozwiązań (a1, a2,., ak), zawierający nie powtarzające się numery punktów i reprezentujący częściową, dopuszczalną drogę z punktu wyjściowego a1 do punktu ak.Przykładem rozwiązania częściowego dla rozważanego labiryntu może być wektor ( 1, 2, 7, 12, 14, 16, 17, 18, 13 ).Próba rozszerzenia rozwiązania częściowego polegać będzie na wyborze ze zbioru Sk kolejnego kandydata, rozszerzając rozwiązanie częściowe do (a1, a2,., ak, ak+1 ) a następnie sprawdzenie, czy w ten sposób osiągamy rozwiązanie końcowe ( w naszym przykładzie - dochodzimy do pola docelowego labiryntu ).Jeśli nie - kontynuujemy rozszerzanie rozwiązania częściowego wybierając kolejnego kandydata ze zbioru Sk+1.Dla zaznaczenia, że przejście z punktu ak, do ak+1 miało już miejsce i w przyszłości nie powinno już być badane, usuwamy ze zbioru Sk kandydata Sk+1.Takie poruszanie się w głąb labiryntu musimy przerwać, jeśli napotkamy pusty zbiór Sk.Wtedy algorytm usuwa z rozwiązania częściowego kandydata ak, wybierając kolejnego kandydata ze zbioru Sk-1.Gdyby i ten zbiór okazał się pusty, trzeba usunąć z rozwiązania częściowego punkt ak-1, próbując rozszerzyć to rozwiązanie punktem ze zbioru Sk-2.Poniżej przedstawiono w tak zwanym pseudokodzie opartym na języku TP ogólną postać algorytmu z powrotami.Pojęcie pseudokodu, chociaż może niezbyt zręczne, ma ilustrować fakt używania w opisie algorytmu, obok typowych konstrukcji języka programowania, pewnych sformułowań w języku naturalnym.Takie postępowanie pozwala zapisywać algorytmy, a raczej ich strukturę, w sposób bardzo ogólny.Przystosowanie algorytmu, zapisanego w pseudokodzie do rozwiązywania pewnych konkretnych problemów polegać będzie na uszczegółowieniu sformułowań zapisanych w języku naturalnym i ich zapisie na poziomie języka programowania.Przedtem należy wybrać oczywiście odpowiednią reprezentację danych.procedure próbuj;begin zapoczątkuj wybieranie kandydatów;repeatwybierz następnego kandydata;if dopuszczalny thenbeginzapisz go;if rozwiązanie niepełne thenbeginpróbuj; {próba wykonania następnego kroku}if próba nieudana then usuń zapisendenduntil próba udana or nie ma następnego kandydataend;Rys.3.4 Ogólna postać algorytmu z powrotami zapisana w pseudokodzie13.2 Implementacja algorytmu z powrotami w postaci drzewaDrzewo jest właściwą strukturą do przechowania informacji o możliwych drogach poszukiwania rozwiązania za pomocą algorytmu z powrotami.Poniższy rysunek przedstawia początkową część drzewa, tak zwanego drzewa poszukiwań, w którym wszystkie możliwe ścieżki zaczynające się od korzenia drzewa są możliwymi drogami w labiryncie zaczynającymi się od pola o numerze 1.Jest to drzewo stopnia czwartego.Znając wszystkie zbiory Si stosunkowo łatwo jest napisać rekurencyjny algorytm generujący takie drzewo.labiryntRys.3.5 Początkowa część drzewa poszukiwań dla labiryntu z rys.3.1, gdy polem wyjścio-wym jest pole o numerze 1Ponieważ drzewo takie przedstawia wszystkie możliwe ścieżki, jego rozległość, a więc i zajętość pamięci, jest znaczna.Pełne drzewo poszukiwań dla labiryntu przedstawionego na rys.3.3 zawiera bardzo dużo węzłów.Natomiast niewątpliwą zaletą takiej reprezentacji jest możliwość przeglądania drzewa przy użyciu prostych metod, na przykład - metody preorder, w której liczba wywołań rekurencyjnych, jak również głębokość rekurencji, będzie zaledwie równa głębokości drzewa.Raz jeszcze sprawdza się przytaczana już wcześniej zasada „coś za coś”.Jest oczywistym, że kształt drzewa, będzie zależał od uporządkowania wartości w poszczególnych zbiorach Si, powinniśmy więc przyjąć uporządkowanie generujące drzewo o możliwie małej wysokości, co zniweluje głębokość rekursji dla algorytmu przeglądającego drzewo.Pojedyncze drzewo poszukiwań pozwala badać jedynie ścieżki rozpoczynające się w punkcie umieszczonym w korzeniu drzewa.Dlatego dla pełnej reprezentacji labiryntu musimy utworzyć las zawierający drzewa rozpoczynające się od wszystkich punktów labiryntu.Aby więc można było stosować algorytm pozwalający badać ścieżki między dwoma dowolnymi polami labiryntu musimy dysponować strukturą zajmującą ogromny obszar pamięci [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl matkasanepid.xlx.pl
.Tak też jest i w naszym przykładowym labiryncie - są to dwu-, trzy- lub czteroelementowe zbiory o wartościach różniących się o 1, lub o 5 od wartości i.Natomiast zbiory Oi są albo z góry zadane i na ogół nie zmieniają się w trakcie realizacji algorytmu, albo (w przypadku bardziej ogólnym) są generowane dla punktu i (a często i dla najbliższego jego otoczenia), na bieżąco w trakcie realizacji algorytmu.Tak się dzieje, na przykład, w większości zręcznościowych gier komputerowych.Rozwiązaniem częściowym jest częściowy wektor rozwiązań (a1, a2,., ak), zawierający nie powtarzające się numery punktów i reprezentujący częściową, dopuszczalną drogę z punktu wyjściowego a1 do punktu ak.Przykładem rozwiązania częściowego dla rozważanego labiryntu może być wektor ( 1, 2, 7, 12, 14, 16, 17, 18, 13 ).Próba rozszerzenia rozwiązania częściowego polegać będzie na wyborze ze zbioru Sk kolejnego kandydata, rozszerzając rozwiązanie częściowe do (a1, a2,., ak, ak+1 ) a następnie sprawdzenie, czy w ten sposób osiągamy rozwiązanie końcowe ( w naszym przykładzie - dochodzimy do pola docelowego labiryntu ).Jeśli nie - kontynuujemy rozszerzanie rozwiązania częściowego wybierając kolejnego kandydata ze zbioru Sk+1.Dla zaznaczenia, że przejście z punktu ak, do ak+1 miało już miejsce i w przyszłości nie powinno już być badane, usuwamy ze zbioru Sk kandydata Sk+1.Takie poruszanie się w głąb labiryntu musimy przerwać, jeśli napotkamy pusty zbiór Sk.Wtedy algorytm usuwa z rozwiązania częściowego kandydata ak, wybierając kolejnego kandydata ze zbioru Sk-1.Gdyby i ten zbiór okazał się pusty, trzeba usunąć z rozwiązania częściowego punkt ak-1, próbując rozszerzyć to rozwiązanie punktem ze zbioru Sk-2.Poniżej przedstawiono w tak zwanym pseudokodzie opartym na języku TP ogólną postać algorytmu z powrotami.Pojęcie pseudokodu, chociaż może niezbyt zręczne, ma ilustrować fakt używania w opisie algorytmu, obok typowych konstrukcji języka programowania, pewnych sformułowań w języku naturalnym.Takie postępowanie pozwala zapisywać algorytmy, a raczej ich strukturę, w sposób bardzo ogólny.Przystosowanie algorytmu, zapisanego w pseudokodzie do rozwiązywania pewnych konkretnych problemów polegać będzie na uszczegółowieniu sformułowań zapisanych w języku naturalnym i ich zapisie na poziomie języka programowania.Przedtem należy wybrać oczywiście odpowiednią reprezentację danych.procedure próbuj;begin zapoczątkuj wybieranie kandydatów;repeatwybierz następnego kandydata;if dopuszczalny thenbeginzapisz go;if rozwiązanie niepełne thenbeginpróbuj; {próba wykonania następnego kroku}if próba nieudana then usuń zapisendenduntil próba udana or nie ma następnego kandydataend;Rys.3.4 Ogólna postać algorytmu z powrotami zapisana w pseudokodzie13.2 Implementacja algorytmu z powrotami w postaci drzewaDrzewo jest właściwą strukturą do przechowania informacji o możliwych drogach poszukiwania rozwiązania za pomocą algorytmu z powrotami.Poniższy rysunek przedstawia początkową część drzewa, tak zwanego drzewa poszukiwań, w którym wszystkie możliwe ścieżki zaczynające się od korzenia drzewa są możliwymi drogami w labiryncie zaczynającymi się od pola o numerze 1.Jest to drzewo stopnia czwartego.Znając wszystkie zbiory Si stosunkowo łatwo jest napisać rekurencyjny algorytm generujący takie drzewo.labiryntRys.3.5 Początkowa część drzewa poszukiwań dla labiryntu z rys.3.1, gdy polem wyjścio-wym jest pole o numerze 1Ponieważ drzewo takie przedstawia wszystkie możliwe ścieżki, jego rozległość, a więc i zajętość pamięci, jest znaczna.Pełne drzewo poszukiwań dla labiryntu przedstawionego na rys.3.3 zawiera bardzo dużo węzłów.Natomiast niewątpliwą zaletą takiej reprezentacji jest możliwość przeglądania drzewa przy użyciu prostych metod, na przykład - metody preorder, w której liczba wywołań rekurencyjnych, jak również głębokość rekurencji, będzie zaledwie równa głębokości drzewa.Raz jeszcze sprawdza się przytaczana już wcześniej zasada „coś za coś”.Jest oczywistym, że kształt drzewa, będzie zależał od uporządkowania wartości w poszczególnych zbiorach Si, powinniśmy więc przyjąć uporządkowanie generujące drzewo o możliwie małej wysokości, co zniweluje głębokość rekursji dla algorytmu przeglądającego drzewo.Pojedyncze drzewo poszukiwań pozwala badać jedynie ścieżki rozpoczynające się w punkcie umieszczonym w korzeniu drzewa.Dlatego dla pełnej reprezentacji labiryntu musimy utworzyć las zawierający drzewa rozpoczynające się od wszystkich punktów labiryntu.Aby więc można było stosować algorytm pozwalający badać ścieżki między dwoma dowolnymi polami labiryntu musimy dysponować strukturą zajmującą ogromny obszar pamięci [ Pobierz całość w formacie PDF ]