Wieczorowe Studia Licencjackie
Wrocław, 05.12.2006
Wstęp do programowania
Wykład nr 10
(w oparciu o notatki K. Lorysia z modyfikacjami)
Wędrówka skoczka po szachownicy
Problem polega na znalezieniu takiego ciągu ruchów skoczka na szachownicy n× n, aby przechodził on dokładnie raz przez każde pole szachownicy jeden raz. Stosujemy następującą metodę:
-
ustalamy porządek między ruchami skoczka startującymi ze wskazanego pola (x,y),
-
startując z pola startowego, przechodzimy do kolejnych pól wybierając z każdego pola pierwszy ruch, który jest dozwolony (nie powoduje kolizji ani wyjścia poza szachownicę),
-
w przypadku braku możliwości wykonania kolejnego kroku z danego pola, rezygnujemy ze skoku na to pole i cofamy się do najbliższego pola, z którego można wykonać jeszcze inny ruch niż wybrany dotychczas;
-
dla każdego odwiedzonego pola pamiętamy numer ostatnio wykonanego ruchu startującego z tego pola; po powrocie na dane pole wybieramy następny numer dozwolonego ruchu;
-
pomocnicza zmienna przechowuje informację o liczbie odwiedzonych pól – łatwo pozwala ustalić czy znaleźliśmy rozwiązanie (tzn. czy odwiedziliśmy już wszystkie pola).
Opis funkcji:
init()
Nadaje tablicom sz i droga wartości początkowe:
-
wartość sz[i][j]=-1 oznacza, że pole (i,j) nie zostało jeszcze odwiedzone; sz[i][j]=k dla k z przedziału 0..7 oznacza, że pole (i,j) zostało odwiedzone i po odwiedzeniu tego pola wybrany został
ruch[k]
-
(droga[k][0], droga[k][1]) opisuje k-tą pozycję w drodze, którą aktualnie analizujemy int nast(int x, int y)
-
wynikiem jest najmniejszy numer ruchu z pola (x,y) na pole dotychczas nieodwiedzone, ale rozważane są tylko ruchy o numerach większych od sz[x][y]
druk()
-
wypisuje drogę opisaną w tablicy ruch
przesun(int x, int y, int k)
-
wykonuje skok o numerze k, startujący z pola (x,y); wymaga to odpowiedniej aktualizacji tablic sz i droga; zmienna globalna r oznacza liczbę odwiedzonych dotychczas pól.
cofnij(int x, int y)
-
cofnięcie o jeden krok, anulowanie ruchu, który ustawiał skoczka na pozycji (x,y) main()
-
pętla poszukująca rozwiązania kończy działanie gdy
o (r=nm-1) co oznacza, że wszystkie pola zostały odwiedzone
o (r<0) co oznacza, że nie udało się znaleźć rozwiązania (wszystkie możliwości startujące z pola startowego zostały sprawdzone)
przesun(int x, int y, int k)
#define n 8
{ sz[x][y]=k;
#define m 8
X=x+ruch[k][0];
#define nm n*m
Y=y+ruch[k][1];
r++;
int sz[n][m], droga[nm][2];
droga[r][0]=X;
int ruch[8][2]={{2,1},
droga[r][1]=Y;
{1,2},
}
{-1,2},
{-2,1},
{-2,-1},
cofnij(int x, int y)
{-1,-2},
{ sz[x][y]=-1;
{1,-2},
droga[r][0]=droga[r][1]=-1;
{2,-1}};
r--;
int X,Y; /*aktualna pozycja skoczka */
if (r>=0){
int r; /* liczba wykonanych skokow */
X=droga[r][0];
Y=droga[r][1];
}
init()
}
{ int i,j;
for (i=0;i<n;i++)
druk()
for (j=0;j<m;j++) sz[i][j]=-1;
{int i;
for (i=1; i<nm; i++)
droga[i][0]=droga[i][1]=-1;
for (i=0; i<nm; i++)
X=Y=droga[0][0]=droga[0][1]=0;
cout << droga[i][0] << ”,” <<
r=0;
droga[i][1] << endl;
}
}
int nast(int x, int y)
main()
{int s,xz,yz;
{int k,u=0;
s=sz[x][y];
init();
s++;
k = nast(X,Y);
while (s<8)
przesun(X,Y,k);
{ xz=x+ruch[s][0]; yz=y+ruch[s][1];
while (r>=0 && r<nm-1)
if (xz<0 || xz>=n || yz<0 ||
{ k=nast(X,Y);
yz>=m || sz[xz][yz]!=-1) s++;
if (k<8) przesun(X,Y,k);
else break;
else cofnij(X,Y);
}
}
return s;
if (r==nm-1) druk();
}
else cout << ”Nie ma drogi” ;
}
Teraz chcemy zliczyć liczbę różnych rozwiązań dla zadania wędrówki skoczka po szachownicy. Rozwiązanie oprzemy na poprzednim programie, wprowadzimy następujące modyfikacje:
-
po znalezieniu drogi skoczka nie kończymy przeszukiwania, a jedynie zwiększamy licznik określający liczbę rozwiązań;
while (r>=0)
-
aby po znalezieniu drogi kontynuować poszukiwanie kolejnych rozwiązań, cofamy skoczka na przedostatnie pole (takie cofnięcie w poprzednim programie oznaczało dalsze próby poszukiwania dróg kontynuujących drogę prowadzącą do przedostatniego pola)
-
if (r==nm-1){
cofnij(X,Y); ile++; }
W efekcie, możemy wykorzystać poprzedni program, zmieniając jedynie funkcję main(): main()
{int k,u,ile=0;
init();
k=nast(X,Y);
przesun(X,Y,k);
while (r>=0)
{ k=nast(X,Y);
if (k<8){
przesun(X,Y,k);
if (r==nm-1){
cofnij(X,Y); ile++; }
}
else cofnij(X,Y);
}
printf("\n Liczba mozliwych ustawien: %d \n",ile);
}
Zadanie
Dany jest labirynt w postaci tablicy rozmiaru n× m, pola o wartości –1 to korytarze, pola o wartości –2 to mury.
Wejście do labiryntu znajduje się w polu (1,1) a wyjście w polu (n,m). Z pola (i,j) przejść można tylko do pól, które mają z nim wspólne krawędzie, czyli (i-1,j), (i+1,j), (i,j-1) oraz (i,j+1). Należy:
-
sprawdzić czy istnieje droga prowadząca od wejścia do wyjścia z labiryntu;
-
jeśli taka droga istnieje, wyznaczyć taką drogę.
Metoda rozwiązania:
-
ustalamy porządek między ruchami ze wskazanego pola (x,y) (ruchy te można opisać zmianą współrzędnych (-1,0), (1,0), (0,-1), (0,1));
-
stosujemy przeszukiwanie z nawrotami, analogiczne do metody stosowanej przy poszukiwaniu drogi skoczka.
-
w każdym polu, wartość –1 traktujemy jak pole wolne, wartość –2 jako mur a wartość i z zakresu [0,3]
jako pole odwiedzone, z którego wyszliśmy wykonując ruch i;
-
UWAGA: nie rozważamy dróg, które więcej niż jeden raz odwiedzają jakieś pole (mimo, że takie mogą istnieć), bo takie drogi zawsze można skrócić.
Poniżej przedstawiamy program realizujący powyższą metodę:
-
Warunkiem określającym znalezienie rozwiązania jest teraz przejście na pole o współrzędnych (n,m)
-
W stosunku do programu wyszukującego drogę skoczka szachowego, zastosowaliśmy następującą modyfikację:
o Pole labiryntu nie mieści się w obrębie współrzędnych od (0,0) do (n-1,m-1) lecz od (1,1) do (n,m)
o Wokół labiryntu „postawiliśmy mur”, co oznacza wypełnienie wartościami –2 pól o pierwszej współrzędnej ze zbioru {0,n+1} i drugiej współrzędnej ze zbioru {0,m+1}. W konsekwencji warunek sprawdzający czy przejście na nowe pole jest dozwolone zmieniło swoją postać z: (xz<0 || xz>=n || yz<0 || yz>=m || sz[xz][yz]!=-1)
na
(sz[xz][yz]!=-1)
ponieważ wyjście za szachownicę oznacza napotkanie „wirtualnego muru”
Na przykład, labirynt postaci
-1
-2
-1
-1
-1
-1
-1
-2
-1
-2
-1
-1
reprezentować będziemy jako
-2
-2
-2
-2
-2
-2
-2
-1
-2
-1
-1
-2
-2
-1
-1
-1
-2
-2
-2
-1
-2
-1
-1
-2
-2
-2
-2
-2
-2
-2
Kod programu wyszukującego wyjście z labiryntu:
#include <stdio.h>
#define n 4
int przesun(int x, int y, int k)
#define m 4
{ sz[x][y]=k;
#define nm (n+2)*(m+2)
X=x+ruch[k][0];
Y=y+ruch[k][1];
int sz[n+2][m+2], droga[nm][2];
r++;
int ruch[4][2]={{1,0},
droga[r][0]=X;
{0,1},
droga[r][1]=Y;
{-1,0},
}
{0,-1}};
int X,Y; /* aktualna pozycja
poszukiwacza */
int cofnij(int x, int y)
int r; /* liczba wykonanych ruchow */
{ sz[x][y]=-1; //lub sz[x][y]=-2;
FILE *fi;
droga[r][0]=droga[r][1]=-1;
r--;
// Dane:
if (r>=0){
// -2 mur
X=droga[r][0];
// -1 wolne pole
Y=droga[r][1];
}
int init()
}
{ int i,j;
fi=fopen("labirynt.txt","r");
void druk()
{int i;
for (i=1;i<=n;i++)
FILE *fi;
for (j=1;j<=m;j++)
fscanf(fi, "%d", &sz[i][j]);
fi=fopen("labirynt.out","w");
for (i=0; i<=n+1; i++)
for (i=0; i<r; i++)
{ sz[i][0]=-2; sz[i][m+1]=-2; }
fprintf(fi,"%d, %d \n", droga[i][0],
for (i=0; i<=m+1; i++)
droga[i][1]);
{ sz[0][i]=-2; sz[n+1][i]=-2; }
fclose(fi);
for (i=1; i<nm; i++)
printf("\n Droga znaleziona\n");
droga[i][0]=droga[i][1]=-1;
}
X=Y=droga[0][0]=droga[0][1]=1;
r=0;
main()
fclose(fi);
{int i,j,k,u,ile=0;
init();
}
k = nast(X,Y);
int nast(int x, int y)
przesun(X,Y,k);
{int s,xz,yz;
while ((X!=n || Y!=m) && r>=0)
//sz[x][y] zawiera -1 dla pola wolnego
{ k=nast(X,Y);
s=sz[x][y];
if (k<4)
s++;
przesun(X,Y,k);
while (s<4)
else cofnij(X,Y);
{ xz=x+ruch[s][0]; yz=y+ruch[s][1];
}
if (sz[xz][yz]!=-1) s++;
if (X==n && Y==m) druk();
else break;
else cout << “Brak wyjscia";
}
return s;
}
}
Koszt przeszukiwania z nawrotami
Załóżmy, że wykonujemy przeszukiwanie z nawrotami w „grze” w której:
-
wykonać można n ruchów,
-
w każdym ruchu wybrać można jedną z k możliwości.
Wówczas, w najgorszym przypadku, sprawdzić musimy kn możliwości.
Oznacza to w szczególności:
-
8 n⋅ n możliwości w przypadku drogi konika szachowego na szachownicy n× n;
-
nn możliwości w przypadku rozstawienia hetmanów na szachownicy o rozmiarze n× n.
W praktyce, przeszukiwanie z nawrotami pozwala znacznie ograniczyć liczbę badanych możliwości, np.:
-
w przypadku drogi konika szachowego, nie kontynuujemy przeszukiwania drogi kończącej się na polu, z którego nie można przejść do nowego pola;
-
podobnie w przypadku przeszukiwania labiryntu.
Niemniej, analiza pozwalająca oszacować uzyskane oszczędności jest trudna.
UWAGA!
W przypadku wielu problemów istnieją rozwiązania dużo szybsze od przeszukiwania z nawrotami lub przeszukiwanie z nawrotami zawsze działa szybko (tak jest na przykład dla zdefiniowanego powyżej przechodzenia labiryntu).
Jeszcze dwa słowa a rekurencji, czyli ... rekurencja ogonowa
Przypomnijmy, że z wykonywaniem funkcji rekurencyjnych wiążą się następujące koszty:
-
obciążenie pamięci stosu, gdzie zapamiętujemy kolejne wywołania rekurencyjne: odpowiada głębokości drzewa wywołań rekurencyjnych;
-
wywołania rekurencyjne, w szczególności powtarzające te same obliczenia: odpowiada liczbie węzłów w drzewie wywołań rekurencyjnych.
Poniżej zamieszczamy dwa przykłady funkcji rekurencyjnych, z którymi nie wiąże się zwiększona (z powodu rekurencji) ilość obliczeń. Rzeczywiście, drzewa wywołań mają postać ścieżek. Niemniej, duża jest głębokość wyprowadzenia (rzędu n).
int potega(int a, int n)
{
if (n==0) return 1;
return a * potega(a, n-1);
}
int silnia(int n)
{
if (n==0) return 1;
return n * silnia(n-1);
}
Charakterystyczną cechą powyższych funkcji jest:
-
w treści występuje tylko jedno wywołanie rekurencyjne;
-
wywołanie rekurencyjne jest ostatnią instrukcją w treści funkcji.
Rekursję spełniającą te własności nazywamy rekurencją ogonową.
Wiele kompilatorów pozwala na translacją rekurencji ogonowej, która unika zajętości pamięci związanej z całą kaskadą wywołań rekurencyjnych.