Există o clasă de probleme a căror rezolvare se pretează la aplicarea unor
algoritmi cu caracter general, care nu se bazează pe un set fix de reguli, ci
pe încercări repetate și reveniri în caz de nereușită. Modalitatea comună de
realizare a acestei tehnici constă în descompunerea obiectivului în obiective
parțiale. De regulă, acestea sunt exprimate în mod natural în termeni
recursivi și constau în explorarea unui număr finit de obiective parțiale.
Obținerea unor soluții parțiale sau finale care nu sunt satisfăcătoare
provoacă revenirea recursivă în cadrul procesului de calcul și continuarea
căutării până la găsirea soluțiilor dorite, motiv pentru care astfel de
soluții se numesc algoritmi cu revenire (backtracking algorithms). Pericolul
care apare este acela al epuizării memoriei, fiecare apel recursiv mărind
stiva programului.
Schema generală a algoritmilor cu revenire este (în pseudocod) următoarea:
procedure incearca_obiectiv_urmator;
begin
if *solutie_dorita then
*afiseaza_solutie
else
begin
*pregateste_pas_urmator;
if *pas_urmator_posibil then
incearca_obiectiv urmator { apel recursiv }
else
*revenire; { se sterg pregatirile pentru pasul urmator }
end;
end;
|
În continuare se va prezenta o metodă de rezolvare a problemei
labirintului.
Labirintul va fi reprezentat în memorie ca un tablou bidimensional de
caractere, de dimensiune NxM, în care, cu ajutorul caracterului chr(219)
- "cărămida neagră" - se reprezintă pereții labirintului, iar cu ajutorul
caracterului ' ' (spațiu), culoarele libere.
Punctul de start este centrul labirintului, drumul de ieșire căutându-se cu
ajutorul unei proceduri recursive drum(X, Y) unde X și Y sunt
coordonatele punctului în labirint și în același timp, indici ai tabloului
care materializează labirintul.
Căutarea se execută astfel:
-
dacă valoarea punctului curent este ' ' se verifică dacă este cumva o
posibilă ieșire (s-a ajuns la marginea labirintului), caz în care punctul se
marchează cu 'S' (s-a găsit un drum de ieșire din labirint) și se execută
afișarea tabloului bidimensional (labirint și drum găsit);
-
dacă punctul curent este ' ', dar nu la marginea labirintului, se
marchează poziția cu caracterul '+', se afișează schimbarea situației și se
apelează recursiv procedura drum pentru cele 4 puncte din vecinatatea
imediată (stânga, dreapta, sus, jos);
-
dacă punctul curent nu este ' ', înseamnă că "am dat de perete" și nu
putem avansa, procedura nu execută nimic, asigurând astfel revenirea la
punctul anterior și explorarea de acolo a celorlalte direcții.
Marcarea cu '+' asigură nu numai memorarea drumului de iesire (firul
Ariadnei), dar înlatură riscul reparcurgeri unui drum deja făcut (ceea ce ar
duce la ciclu infinit). Este important ca marcajul de drum să fie șters (pus
pe ' ') în momentul în care se ajunge la o fundatură și se revine.
Tabloul cu harta labirintului se declară prin:
L: array[0..N-1, 0..M-1] of char;
|
Procedura drum va avea următoarea formă:
Procedure drum(X, Y: integer);
begin
if M[X, Y] = ' ' then
if (((X mod N-1)) = 0) or (Y mod (M-1) = 0)) then
begin
M[X, Y] := 'S'; { punctul de iesire }
*afisare;
M[X, Y] := ' '
end
else
begin
M[X, Y] = '+'; { marcare de drum }
*afisare;
drum(X+1, Y);
drum(X, Y+1);
drum(X-1, Y);
drum(X, Y-1);
M[X, Y] := ' '; { stergere drum }
*afisare;
end;
end;
|
Se observă că la apelul inițial al procedurii drum punctul de
plecare trebuie decalat cu -1 pe axa X și cu -1 pe axa Y (numărătoarea
liniilor și coloanelor începând de la 0).
-
Se dă un fișier text 'LABIRINT.DAT' cu 24 de linii, fiecare linie
formată din 80 de caractere. Fișierul reprezintă harta unui labirint, unde
caracterul 'P' desemnează perete, iar caracterul '.' loc liber. Se citește
acest labirint și se afișează pe ecran. Se va ilustra căutarea drumurilor
din labirint prin afișarea și ștergerea pas cu pas a marcajelor '+'.
Se vor folosi următoarele proceduri predefinite din unit-ul Crt:
ClrScr; {sterge ecranul}
GoToXY(X, Y: byte); {pozitioneaza cursorul in pozitia X, Y}
Delay(T: word); {opreste executia cu T milisecunde}
|
Punctul de plecare este (12, 40).
Click aici pentru un fișier cu date de test
(labirint.dat)
-
Pentru același labirint se va căuta drumul de ieșire minim și se va
afișa.
-
* Pentru același labirint se va căuta drumul de ieșire care are cele mai
puține cotituri.