Download - Metoda backtracking
![Page 1: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/1.jpg)
ELABORAT DE ELEVUL CLASEI XI-A”B” COȘERU
SERGIU
Metoda Backtracking
![Page 2: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/2.jpg)
Această tehnică poate fi utilizată pentru rezolvarea problemelor de căutare, putând fi folosită pentru generarea tuturor soluţiilor posibile.
![Page 3: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/3.jpg)
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ă
![Page 4: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/4.jpg)
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;
![Page 5: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/5.jpg)
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.
![Page 6: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/6.jpg)
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:
![Page 7: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/7.jpg)
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.
![Page 8: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/8.jpg)
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.
![Page 9: Metoda backtracking](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888d93d8b42ab7558b45cd/html5/thumbnails/9.jpg)
Link-uri utile
http://software.ucv.ro/~cstoica/TP/backtracking.pdfhttp://info.mcip.ro/?t=back