Backtraking prezentare

7/30/2019 Backtraking prezentare

1/23

ELEV: BALMUS IONUT

PROFESOR COORDONATOR:

DIMITRIEVICI LUCIAN TRAIAN


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


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)}


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.


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).


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/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


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--;

}}

}


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


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


11/23

void back(){

int k, i, s;k = 1;s = n;for (i = 1; i


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},


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


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


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.


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


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;}


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


19/23

Implementarea codului

#include#includeint st[20],n;

void tipar(){ for(int i=1;i


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


21/23

# include int sol[10],a[10],b[10],n,i,s;void tipar ( int k ){

cout


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


23/23

( ){ int val;for(val=1;val>n;st[1][1]=1;st[1][2]=1;bkt(2);

return 0;

Backtraking prezentare

Documents

Transcript of Backtraking prezentare