Post on 14-Apr-2018
7/30/2019 Backtraking prezentare
1/23
ELEV: BALMUS IONUT
PROFESOR COORDONATOR:
DIMITRIEVICI LUCIAN TRAIAN
7/30/2019 Backtraking prezentare
2/23
Cuprins Backtracking iterativ
1) Definiie
2) Probleme prototip3) Tipul de probleme la care se aplic metoda4) Mecanism general5) Rutina6) Problema permutarilor7) Submultimile unei multimi8) Problema permutarilor literelor unui cuvant
Backtracking recursiv
1) Rutina2) Implementarea codului3) Plata unei sume de bani4) Problema calului
7/30/2019 Backtraking prezentare
3/23
DEFINIIE
Metoda Backtracking este o metod sau o tehnic de programare care coprogresiv soluia final ncepnd de la soluia nul sau vid i alegnd pentru fiecaresa o valoare din mulimea soluiilor posibile.
Metoda se traduce prinrevenire sau cale ntoars sau drum napoideoarececnd nu se poate nainta ne ntoarcem cu un pas sau mai muli napoi.
Problema 1 prototip:
Se dau dou mulimi: S1={A, B, C} i S2={M, N}. Determinai toi vectorii formai din doux1 , x2 aparinnd mulimii S1S2 astfel nct dac x1 este A sau B, x2 nu poate fi M.
Soluii:soluii rezultat: x{(A, M), (A, N), (B, M), (B, N), (C, M), (C, N)}soluii rezultat: x{(A, N), (B, N), (C, M), (C, N)}
7/30/2019 Backtraking prezentare
4/23
Tipul de probleme la care se aplic metoda
Aceast tehnic se folosete n rezolvarea problemelor care ndeplinesc simultacondiii:soluia lor poate fi pus sub forma unui vector S=x1, x2, , xn, cu x1A1, x2A2, , mulimile A1, A2, , An sunt mulimi finite, iar elementele lor se consider c se afl
ordine bine stabilit;nu se dispune o alt metod de rezolvare mai rapid.
Lantlnirea unei astfel de probleme, dac nu cunoatem aceast tehnic, sungenerm toate elementele produsului cartezian A1A2An i fiecare element seste soluie. Rezolvnd problema n acest mod, timpul de execuie este att de marconsiderat infinit, algoritmul neavnd nici o valoare practic.
Pentru fiecare problem sunt date anumite condiii sau relaii ntre componentesunt numite condiii interne (de continuare). Pentru a determina toate soluiile rezultatoate soluiile posibile este folosit tehnica ntoarcerii cu revenire.
7/30/2019 Backtraking prezentare
5/23
Mecanismul general
Metoda urmrete s evite generarea tuturor soluiilor posibile. n acest scop elevectorului x=(x1, x2, , xn) primesc pe rnd valori n sensul c lui xk i se atribuie o valoau fost deja atribuite valori pentru componentele x1, x2, , xk-1. Odat stabilit o vanu se trece direct la atribuirea unei valori pentru xk; nti se verific condiia de contin
componentele x1, x2, , xk-1.
Dac au fost ndeplinite condiiile de continuare atunci se alege o valoare pentnendeplinirea lor exprim faptul c oricum am alege componentele xk, xk+1, , xn najunge la o soluie de tip rezultat. Asta nseamn c acele condiii de continuare sunpentru obinerea unei soluii. n cazul nendeplinirii condiiilor de continuare va trebui salegere pentru xk sau dac mulimea Sk a fost epuizat se va ncerca o nou alegercomponenta xk-1 dup care se face o nou alegere pentru xk. Aceast revenire la c
anterioar prin micorarea lui k d numele metodei.
n unele probleme vom ntlni att condiii de continuare ct i condiii interne nstrns legtur. n alte tipuri de probleme condiiile interne vor fi aceleai cu condiiiatunci cnd pasul k va atinge valoarea n condiiile de continuare sunt chiar condiiilePrin aceast metod orice vector este construit progresiv ncepnd cu prima compoctre ultima cu eventualele reveniri asupra valorilor atribuite anterior (cu unul sau maatt timp ct este posibil revenirea).
7/30/2019 Backtraking prezentare
6/23
Prin atribuiri sau ncercri de atribuiri euate din cauza nerespectrii condiiilor danumite valori sunt consumate sau testate i vom nota cu Ck mulimea valorilor consufiecare mulime Ck fiind inclus cu posibilitate de egal n Sk.
v1, v2, , vk sunt valorile curente pentru componentele x1, x2, ,xk
O configuraie oarecare pentru aceast metod este reprezentat astfel:
Pn la xk toate componentele au primit valorile v1, v2, , vk-1 n ncercarea devector soluie. Aceste valori satisfac condiiile de continuare pentru componenta xk. Uo atribuire din Sk-Ck, unde Ci reprezint mulimea valorilor consumate (testate). Aplica
Backtracking ncepe n situaia n care nici o valoare nu a fost consumat i se ncearcprimei componente (acest lucru presupune c mulimile Ck sunt vide).
v1, v2, , vk-1 xk, xk+1, , xnc1, c2, , ck-1 Ck, vid, ,
vid
7/30/2019 Backtraking prezentare
7/23
Rutina
Atunci cnd mulimile de valori posibile sunt distincte S1SSSn
se citesc mulimile S1,S2,,Snse iniializeaz C1, C2, , Cn cu mulimea vid
k = 1; //se iniializeaz pasul de lucru cu 1while (k > 0) do //configuraia nu e finalif (k == n+1 ) atunci //s-a depit dimensiunea vectorului
se tiprete soluiase scade cu o unitate pasul de lucru
elsedac CkSk atunci //mai exist valori netestate nc
se alege o valoare vk Sk-Ck
se verific pentru vectorul (v1, v2, , vk) condiiile de continuaredac acestea sunt ndeplinite atunci
xk = vk i k = k+1else
Ckk = k - 1
At i d li il d l i ibil i id S1 SS S
7/30/2019 Backtraking prezentare
8/23
Atunci cnd mulimile de valori posibile coincid S1=SS==Sn
void back(){
int k, i, s;s = 3;k = 1;for (i = 1; i 0){if (k == n + 1){
retsol();k--;
}else if (x[k] < s){
x[k]++;if (continuare(k))
k++;}else{
x[k] = 0;k--;
}}
}
7/30/2019 Backtraking prezentare
9/23
PROBLEMA PERMUTRILOR
S se genereze toate permutrile unei mulimi de n numere (1, 2, , n).
Explicaii: Funciaretsol este funcia de afiare a soluiilor. Cu o variabilnr consoluiiloriar cu ajutorul contorului i de la 1 la n afimsoluiile.
n funcia continuare nu avem dect o singur condiie, ca x[i] s fie diferit de xcombinrilor) pentru a nu se repeta soluiile.
Funcia care stabilete soluiile rezultat i le reine n vectorul x[i] este back. Att alege soluii posibile se verific dac nu s-a depit dimensiunea vectorului x[i] i se tipscznd i pasul de lucru cu o unitate. n caz contrar se verific dac mai sunt valori npentru acestea se verific condiiile problemei, apelnd funcia continuare. Dac crespectate valoarea devine soluie a problemei i se tiprete folosind apelul funciei
n funcia principal se citete n care reprezint numrul de elemente ale mulimapeleaz funcia back pentru a tipri soluiile.
Exemplu: Fie n=3 adicmulimea {1, 2, 3}. Vor exista 6 variante de permutri : 123, 132
7/30/2019 Backtraking prezentare
10/23
#include#include#includeint x[10],n,nr = 1;void retsol(){
int i ;printf("\nSolutia cu nr. %d este:", nr);
for (i = 1; i
7/30/2019 Backtraking prezentare
11/23
void back(){
int k, i, s;k = 1;s = n;for (i = 1; i
7/30/2019 Backtraking prezentare
12/23
SUBMULIMILE UNEI MULTIMI
Se citesc n i m numere naturale. S se genereze toate submulimile de ctre munei mulimi de n elemente (1, 2, , n), inclusiv mulimea vid.
Explicaii: Funciaretsol este funcia de afiare a soluiilor. Vom contoriza solu
nr. Vom mai avea un contorm care dac este 0 se va afiasoluiavid iar n cazconstruite.
n funciacont avem condiiacombinrilorpentru a nu se repeta soluiile.Funcia care stabilete soluiile rezultat i le reine n vectorul x[i] este back. Att timalege soluii posibile se verific dac nu s-a depit dimensiunea vectorului x[i] i se tiscznd i pasul de lucru cu o unitate. n caz contrar se verific dac mai sunt valori pentru acestea se verific condiiile problemei, apelnd funcia continuare. Dac
respectate valoarea devine soluie a problemei i se tiprete folosind apelul funciei
n funciaprincipal citim n - numrul de elemente ale mulimii. Cu ajutorul variapornete de la 0 la n, vom apela funciaback pentru a tiprisoluiile rezultat.
Exemplu: Pentru mulimea {1, 2, 3} avem 8 submulimi: , {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3},
7/30/2019 Backtraking prezentare
13/23
#include#include#includeint x[100],n,m,nr = 1;void retsol(){
printf("\nSolutia cu nr %d : ", nr);
if (m == 0)printf("0");
for (int i = 1; i
7/30/2019 Backtraking prezentare
14/23
void back(){
int i, k, s;k = 1;s = n;while (k != 0)
if (k == m + 1){
retsol();k--;
}else if (x[k] < s){
x[k]++;if (cont(k) == 1) k++;
}else{
x[k] = 0;k--;
}}
int main(){
printf("n=");scanf("%d", &n);
for (m = 0; m
7/30/2019 Backtraking prezentare
15/23
PROBLEMA PERMUTRILOR LITERELOR UNUI CUVNT
Explicaii: Funciaretsol este funcia de afiare a soluiilor. Cu un contori decte o liter a cuvntului pe acelai rnd. Contorizarea soluiilorse va face cu ajutorun funciacontinuare nu avem dect o singurcondiie, ca x[i] s fie diferit de x[k] (caranjamentelor) pentru a se verifica toate soluiile posibile.
Funcia care stabilete soluiile rezultat i le reine n vectorul x[i] este back. Atpot alege soluii posibile se verific dac nu s-a depit dimensiunea vectorului x[i] i sescznd i pasul de lucru cu o unitate. n caz contrar se verific dac mai sunt valori npentru acestea se verific condiiile problemei, apelnd funcia continuare. Dac crespectate valoarea devine soluie a problemei i se tiprete folosind apelul funciei
n funcia principal se citete cuvntul, se reine n variabila n numrul de litefiecare liter se va pstra n vectorul cuv[i]. La sfrit se apeleaz back pentru a tip
Exemplu: Vom considera un cuvnt format din patru litere: ALEX. n acest caz vosoluii: ALEX, ALXE, AELX, AEXL, AXLE, AXEL, LAEX, LAXE, LEAX, LEXA, LXAE, LXEA, EALX, EAEXAL, EXLA, XALE, XAEL, XLAE, XLEA, XEAL, XELA.
7/30/2019 Backtraking prezentare
16/23
#include#include#include#includeint n,x[15],nr = 1;char cuv[15];
void retsol(){
printf("Solutia cu nr %d : ", nr);for (int i = 1; i
7/30/2019 Backtraking prezentare
17/23
(){
int k;k = 1;while (k > 0)
if (k == n + 1){
retsol();k--;
}else if (x[k] < n){
x[k]++;if (cont(k) == 1)
k++;}else{
x[k] = 0;k--;
}}int main(){
printf("Cuvantul : "); scanf("%s", &cuv);n = strlen(cuv);back();
return 0;}
7/30/2019 Backtraking prezentare
18/23
Rutina
n cazul variantei recursive rutina back se definete ca o funcierecursiv cu parametrul k (nivelul curent din stiv). Urcarea in stiv se faceprin autoapelul funciei back cu o nou valoare pentru k. Generareapotenialilor candidai la soluie se face print-o instruciune for careparcurge valorile posibile de la limita inferioar la limita superioar. Iatsoluia pentru problema permutarilor:
Implementarea codului
7/30/2019 Backtraking prezentare
19/23
Implementarea codului
#include#includeint st[20],n;
void tipar(){ for(int i=1;i
7/30/2019 Backtraking prezentare
20/23
Plata unei sume de bani
Se dau suma Sce trebuie pltit i n tipuri de monede avnd valori de a1, a2, ... , anlei. Se cer toate modalitile de plaaceste monede.
Observaii :
valorile celor n monede se rein n vectorul a;
se presupune c dispunem de attea monede din fiecare tip, cte sunt necesare ( acest numr se obine n ipotezpltit numai cu monede de acel tip i se reine n vectorul b );
o soluie este sub forma unui vector cu n componente ( sol ) n care componenta ireine numrul de monede de tiplata sumei S; acest numr poate fi i zero;
toate componentele vectorului sol sunt iniializate cu1( valoare aflat naintea valorilor posibile ); iniializarea uneatunci cnd se revine la componenta de indice imediat inferior;
funcia plata ( ) are doi parametrii : indicele componentei din sol care urmeaz a fi completat ( k )i suma pltit);
apelul funciei plata ( )( din cadrul programului principal ) se face pentru prima component i suma 0;
Fiind dat un nivel oarecare k, se procedeaz astfel :
atta timp ct este posibil s uti lizm n plat nc o moned din tipul respectiv ( nu se depete suma care trebui
se incrementeaz nivelul ( se folosete o nou moned de tipul k);
suma pltit se majoreaz cu valoarea acelei monede;
n cazul cnd a fost obinut o soluie ( s0 = S), aceasta se tiprete, contrar se apeleaz funcia pentru nivelul urm
# include # include
7/30/2019 Backtraking prezentare
21/23
# include int sol[10],a[10],b[10],n,i,s;void tipar ( int k ){
cout
7/30/2019 Backtraking prezentare
22/23
Problema calului
Fiind dat o tabl de ah de dimensiunea nxn i un cal n colul stnga sus ase afieze toate posibilitile de mutare a calului astfel nct s treac o singur dattablei.
#include#includelong st[100][100],vec[20][20],i,n;int valid(int k){ if((st[k][1]n) || (st[k][2]n))return 0;
for(i=1;i
7/30/2019 Backtraking prezentare
23/23
( ){ int val;for(val=1;val>n;st[1][1]=1;st[1][2]=1;bkt(2);
return 0;