A. Considerații teoretice

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.


B. Exemple

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:

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).


C. Teme

  1. 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)

  2. Pentru același labirint se va căuta drumul de ieșire minim și se va afișa.

  3. * Pentru același labirint se va căuta drumul de ieșire care are cele mai puține cotituri.