Tehnici de programare (Backtracking)

Backtracking = eng,,cautare cu revenire''.

             Ce este tehnica căutării cu revenire?

• Este unu algoritm general de descoperire a tuturor soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă.

• Se utilizează în special pentru rezolvarea problemelor a căror cerință este de a determina configurații care satisfac anumite restricții cum ar fi cuvintele încrucișate, jocuri de sudoku și alte probleme similare.

• Algoritmul generează un set de candidați parțiali care, în principiu, pot fi completați în diverse moduri pentru a defini soluțiile posibile la problema dată. Completarea se face incremental. Ne putem imagina candidații parțiali ca fiind ramurile  unui arbore cu soluții potențiale. Frunzele acestui arbore sunt candidații parțiali ce nu mai pot fi completați. Algoritmul traversează recursiv acest arbore, pornind de la rădăcină, și pentru fiecare ramură se verifică dacă acesta poate fi completată pentru a obține o soluție validă. Dacă acest lucru nu este posibil, întreaga ramură cu toate subramurile sale este eliminată. Altfel, algoritmul verifică dacă ramura este o soluție validă și dacă da este raportată ca atare utilizatorului, iar dacă nu, vor fi enumerate recursiv toate subramurile acesteia.

Problema:

Turnuri  de cuburi

Se dau n cuburi numerotate 1,2,...,n, de laturi Li si culori Ci, i=1,2,...,n (fiecare culoare este codificata printr-un caracter). Sa se afiseze toate turnurile care se pot forma luând k cuburi din cele n disponibile, astfel încât:

      -laturile cuburilor din turn sa fie in ordine crescatoare;

      -culorile a oricare doua cuburi alaturate din turn sa fie diferite.

program cuburi;

type stiva=array [1..100] of integer;

var st:stiva;

       i,n,p,k:integer;

       as,ev:boolean;

       L:array [1..10] of integer;

       C:array [1..10] of char;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end;

procedure succesor(var as:boolean;var st:stiva;k:integer);

begin

if st[k]<n then

                 begin

                 st[k]:=st[k]+1;

                 as:=true;

                 end

                 else as:=false;

end;

procedure valid(var ev:boolean;st:stiva;k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1 do if L[st[k]]<=L[st[i]] then ev:=false;

if C[st[k]]=C[st[k-1]] then ev:=false;

end;

function solutie(k:integer):boolean;

begin

solutie:=(k=p);

end;

procedure tipar;

var i:integer;

begin

for i:=1 to p do write(st[i],' ');

writeln;

end;

begin

write('n= ');read(n);

write('p= ');read(p);

for i:=1 to n do

begin

write('L[',i,']=');readln(L[i]);

write('C[',i,']=');readln(C[i]);

end;

k:=1;init(k,st);

while k>0 

begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or (as and ev);

if as then if solutie(k) then tipar

else begin 

init(k,st);

end

else k:=k-1;

end;

end.

Link:http://tehnicideprogramare.weebly.com/backtracking.html

        http://www.scritub.com/stiinta/informatica/METODA-BACKTRACKING1055131414.php