Post on 23-Jun-2015
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