ELABORAT DE ELEVUL CLASEI XI-A”B” COȘERU

SERGIU

Metoda Backtracking

Această tehnică poate fi utilizată pentru rezolvarea problemelor de căutare, putând fi folosită pentru generarea tuturor soluţiilor posibile.

Se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

Soluţia lor poate fi pusă sub forma unui vector V = x1x2x3 ……. xn, cu x1∈A1 …. Xn ∈ An

Mulţimile A1, A2, … An sunt mulţimi finite, iar elementele lor se află într-o ordine bine stabilită

Nu se dispune de o metodă de rezolvare mai rapidă

Algoritmul General

Procedure Reluare(k:integer);begin if k<=n then begin X[k]:=primulelement(k); if Continuare(k) then Reluare(k+1); while ExistaSuccesor(k) do Begin X[k]:=Succesor(k); If Continuare(k) then Reluare(k+1) End; End Else PrelucrareaSolutiei;End;

Metoda poate fi folosită la rezolvarea urmatoarelor probleme:generarea permutărilor unei mulţimigenerarea aranjamentelor unei mulţimigenerarea submulţimilor unei mulţimigenerarea submulţimilor cu m elemente ale unei mulţimi

(combinări)generarea produsului cartezian a n mulţimigenerarea tuturor secvenţelor de n (par) paranteze care se

închid corect.colorarea ţărilor de pe o hartă astfel încât oricare două ţări

vecine să aibă culori diferitearanjarea a n regine pe o tablă de şah de dimensiune n fără

ca ele să se atace.

Partiţiile unui număr natural. Fie n>0, natural. Să se scrie un program care să afişeze toate partiţiile unui număr natural n.Numim partiţie a unui număr natural nenul n o mulţime de numere naturale nenule {p1, p2, …, pk} care îndeplinesc condiţia p1+p2+ …+pk = n.Ex: pt n = 4 programul va afişa:

Partițiile unui număr natural:

program Partitii_nr_natural; var n, ns: byte;sol: array[1..20] of byte; procedure afis(l: byte);var i: byte;begininc(ns); write 'Solutia ', ns, ' : ');for i:=1 to l do write(sol[i]:3);writeln;end;

procedure back(i, sp: byte);var j: byte;beginif sp = n then afis(i-1) else for j:=1 to n-sp doif (j>=sol[i-1]; then beginsol[i]:=j;back(i+1, sp+j)                 end; end;

beginread(n); ns:=0;back(1,0); writeln(ns,'solutii');

end.

Concluzie

În conlcuzie metoda reluării este o metodă ce necesită mult timp de aceea trebuie să fie folosită ca o ultimă soluție a problemei .Avantajul metodei este că nu se generează toate soluțiile dar doar cele ce sunt convenabile rezolvării problemei date.

Link-uri utile

http://software.ucv.ro/~cstoica/TP/backtracking.pdfhttp://info.mcip.ro/?t=back