A. Consideratii teoretice

Cautarea drumului de iesire dintr-un labirint printr-un program recursiv poate duce la umplerea stivei si depasirea spatiului disponibil de memorie.aceasta se intampla daca labirintul are dimensiuni mari si drumuri foarte lungi si ramificate.Problema este si mai costisitoare ca si spatiu de memorie, daca se cauta toata drumurile care trebuie, evident, memorate intr-un fel, ocupand si ele un loc semnificativ in memorie.

Se poate aplica un algoritm de tip "greedy" care va fi mai lent, dar va memora toate drumurile si va gasi si drumul de iesire minim.

Principiul este asemanator cu principiul lui Huygens din teoria undelor: "Un punct de pe o suprafata de unda este un punct de generare a altor unde (de aceeasi frecventa si amplitudine)".


B. Exemple

Se considera labirintul reprezentat ca o matrice bidimensionala formata din numere intregi unde peretii vor avea valoarea -1 si culoarele valoarea 0. Se fixeaza in punctul de plecare valoarea 1 si se memoreaza aceasta valoare intr-o variabila k. Se cauta in matrice elementele egale cu k si in pozitiile vecine (inainte, sus, inapoi, jos) care sunt egale cu 0 se trece valoarea k+1. Variabila k ia valoarea k+1 dupa o astfel de baleiere si se reia procesul, pana cand toate pozitiile labirintului au valoarea diferita de 0. Fenomenul este urmatorul in cazul unui labirint cu 3 iesiri.

care va fi astfel completat:

Matricea se declara cu:

L: array [0..N-1, 0..M-1] of integer;

si se foloseste un tablou auxiliar D:

D: array [1..4, 1..2] of integer;

initializat in felul urmator:

D[1,1] :=-1;

D[1,2] := 0;

D[2,1] := 0;

D[2,2] :=-1;

D[3,1] := 1;

D[3,2] := 0;

D[4,1] := 0;

D[4,2] := 1;

sau ca si constanta:

const D: array [1..4, 1..2] of integer=((-1,0), (0,-1), (1,0), (0,1));

Se mai folosesc variabilele:

var
  k,i,j : integer;
  stop : boolean;
begin
  k:=1;
  i:=<valoarea punctului de plecare pe coordonata x>;
  j:=<valoarea punctului de plecare pe coordonata y>;
  L[i,j]:=k;    { fixarea punctului de plecare };
  repeat
    stop:=true;
    for i:=1 to N-2 do
    for j:=1 to N-2 do
    if L[i,j]=k then
      for DI:=1 to 4 do
      if L[i+D[DI,1], j+D[DI,2]] then
      begin
        L[i+D[DI,1], j+D[DI,2]]:=k+1;
        stop :=false;
      end;       
    k:=k+1;
  until stop;
end.

Pentru afisarea drumurilor se cauta pe perimetrul matricii elemente pozitive. Acestea reprezinta puncte de iesire. Cu un algoritm asemanator se parcurge in sens invers drumul, cautand dintr-un punct cu valoarea k elementele de valoarea k-1, pana cand k=1 (a fost atins punctul de plecare). In pseudocod:

i:=<valoarea coordonatei x a punctului de iesire>;
j:=<valoarea coordonatei y a punctului de iesire>;
k:=L[i,j];
*afiseaza pe ecran punctul de plecare cu 'S'
repeat
  *cauta vecinul de valoare k-1 => L[iurm,jurm]
  i:=iurm;
  j:=jurm;
  *afiseaza pe ecran pasul facut cu '+'
  k:=k-1;
until k=1;

Se observa ca algoritmul gaseste implicit si drumul minim, care este drumul care are in punctul de iesire valoarea cea mai mica dintre toate punctele de iesire de pe perimetru.


C. Teme

  1. Folosindu-se ca date de intrare informatiile din fisierul LABIRINT.DAT folosit anterior la lucrarea cu backtracking, sa se scrie un program care ilustreaza pe ecran cautarea drumurilor de iesire cu metoda greedy prezentata si afisarea pe rand a tuturor drumurilor gasite.

  2. Sa se gaseasca drumul minim cu aceasta metoda.

  3. Sa se gaseasca drumul cu cele mai putine cotituri.