Metoda Backtracking
Prezentare generala
Se foloseste în rezolvarea problemelor care îndeplinesc conditiile:
au solutia de forma S=(x1, x2,., xn) cu xi Ai , i=1..n;
A1, A2, ., An sunt multimi finite, ia 646q161g r elementele lor se afla într-o relatie de ordine bine stabilita;
nu se dispune de alta metoda de rezolvare mai rapida;
Principiul care sta la baza acestei metode este simplu:
se construieste solutia pasa cu pas x1, x2,., xn ;
daca se constata ca pentru o valoare aleasa nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul în care am ramas.
Metoda Backtracking genereaza toate solutiile problemei.
Algoritmul Backtracking
Se alege cu x1 A1
Se presupun generate x1, x2,., xk apartinând multimilor A1, A2, ., respectiv Ak. Se alege (daca exista) xk+1, primul element disponibil din Ak+1:
Nu s-a gasit xk+1. Având generate elementele x1, x2,., xk-1, se reia cautarea considerând urmatorul element al multimii Ak, netestat înca.
S-a gasit xk+1. Se testeaza daca acesta îndeplineste conditiile
Daca xk+1 îndeplineste conditiile, se testeaza daca s-a ajuns la solutie.
2.2.1.1. daca s-a ajuns la solutie, se tipareste solutia si se reia algoritmul
considerând generate elementele x1, x2,., xk cautându-se în
continuare un alt element al multimii Ak+1 ramas netestat.
2.2.1.2. daca nu s-a ajuns la solutie, se reia algoritmul considerând
generate elementele x1, x2,., xk+1 si se cauta un prim element
xk+2 Ak+2
Daca xk+1 nu îndeplineste conditiile, se reia algoritmul considerând generate elementele x1, x2,., xk si se cauta un alt element xk+1 printre elementele multimii Ak+1 netestate înca.
Algoritmul se termina atunci când nu mai exista nici un element x1 A1 netestat.
Probleme propuse
Sa se genereze toate permutarile de ordinul n.
Se da o tabla de sah de dimensiune n x n . Se cer toate solutiile de aranjare a n dame astfel încât sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala.
Sa citesc n si p numere naturale. Sa se genereze toate submultimile multimii de p elemente. Doua submultimi care au aceleasi elemente dar în ordine diferita, sunt considerate distincte. (Apn)
Indicatie
La fel ca problema generarii permutarilor, numai ca solutia este de dimensiune p x1, x2,., xp
Sa citesc n si p numere naturale. Sa se genereze toate submultimile multimii de p elemente. Doua submultimi care au aceleasi elemente dar în ordine diferita, sunt considerate egale. (Cpn)
Indicatie
La fel ca problema generarii permutarilor, dar
solutia este de dimensiune p x1, x2,., xp
nivelul k al stivei ia valori între 1 si n-p+k
pe nivelul k trebuie sa fie o valoare mai mare decât pe nivelul k-1 al stivei.
Se citesc n litere mici distincte. Sa se genereze toate cuvintele care
contin exact m litere din cele n citite
literele din care sunt formate apar în ordine lexicografica crescatoare
Se da o harta cu n tari. Se cer toate solutiile de colorare a hartii utilizând cel mult 4 culori, astfel încât doua tari cu frontiera comuna sa fie colorate diferit.
Indicatie
Harta este furnizata de o matrice An,n.
A(i,j)=1, daca tara i se învecineaza cu tara j
0, în caz contrar
Un comis-voiajor trebuie sa viziteze un numar de n orase. Initial, acesta se afla într-unul din ele, notat cu 1. Comis-voiajorul doreste sa nu treaca de 2 ori prin acelasi oras, iar la întoarcere sa revina în orasul 1. Cunoscând legaturile existente între orase, sa se afle toate drumurile posibile pe care le poate efectua comis-voiajorul.
Indicatie
Legaturile existente între orase sunt date de o matrice An,n.
A(i,j)=1, daca exista drum între orasul i si orasul j
0, în caz contrar
Se considera multimea A . Se cer toate partitiile acestei multimi.
(submultimile A1, A2, ., Ak formeaza o partitie a multimii A daca sunt disjuncte doua câte doua si reuniunea lor este A).
Indicatie
o partitie a multimii A se poate reprezenta sub forma unui vector stiva cu n componente. stiva[i]=k - elementul i al multimii A apartine submultimii k a partitiei.
pentru a se evita repetitia partitiilor se face conventia stiva[k] ia valori cuprinse ntre 1 si k; unde k =1..n
oricare i sa existe j astfe încât |stiva[i]-stiva[j]|<=1
Se dau suma s si n tipuri de monede având valori de a1, a2, ., an lei. Se cer toate modalitatile de plata a sumei s utilizând cele n tipuri de monede.
Se da un numar natural par n. Sa se determine toate sirurile de n paranteze care se închid corect.
Solutii
#include <stdio.h>
#include <conio.h>
int st
int n,as,ev;
void succesor(int k)
else as=0;
void valid(int k)
void tipar(void)
void main(void)
do
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
else
}
else k--;
}
printf("\n Gata!");
getche();
#include <stdio.h>
#include <conio.h>
#include <math.h>
int st[100];
int n,as,ev;
void succesor(int k)
else as=0;
void valid(int k)
void tipar(void)
void main(void)
do
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
else
}
else k--;
}
printf("\n Gata!");
getche();
#include <stdio.h>
#include <conio.h>
int st[100];
int n,as,ev,m;
void succesor(int k)
else as=0;
void valid(int k)
void tipar(void)
void main(void)
do
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
else
}
else k--;
}
printf("\n Gata!");
getche();
#include <stdio.h>
#include <conio.h>
int stiva[100];
int n,as,ev,p;
void main(void)
else as=0;
}
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
\t");getch();
}
else
}
else k--;
}
printf("\n Gata!");
getche();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int m,n;
int stiva[100];
char litere[100];
int as,ev;
void succesor(int k)
else as=0;
void valid(int k)
void main ()
printf("\n Solutiile sunt: \n");
k=1;stiva[k]=0;
while (k>0)
while (! ((as==0) || (as>0 && ev>0)) );
if (as>0)
else
}
else k--;
getch();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int n;
int stiva[100],a[100][100];
int as,ev;
void succesor(int k)
else as=0;
void valid(int k)
void main ()
k=1;stiva[k]=0;
while (k>0)
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
else
}
else k--;
printf("\n Gata!");
getch();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int n;
int stiva[100],a[100][100];
int as,ev;
void succesor(int k)
else as=0;
void valid(int k)
void main ()
stiva[1]=1;
k=2;stiva[k]=0;
while (k>1)
while (!((as==0) || (as>0 && ev>0)));
if (as>0)
else
}
else k--;
printf("\n Gata!");
getch();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int n;
int stiva[100];
int as,ev;
void succesor(int k)
if ( stiva[k]<max+1 && stiva[k]<k)
else as=0;
void tipar(void)
");
}
void main ()
else
}
else k--;
getch();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int n,suma,as,ev;
int stiva[100],a[100],m[100];
void succesor(int k)
else as=0;
}
else as=0;
}
int solutie(int k)
return 0;
void main ()
k=1;stiva[k]=-1;
while (k>0)
else
}
else k--;
printf("Gata!");
getch();
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int n,as,ev;
int stiva[100];
char simbol[3];
void succesor(int k)
else as=0;
void valid(int k)
if (nr2>nr1) ev=0;
if (nr1>(n/2) || nr2>n/2) ev=0;
if (stiva[1]==2) ev=0;
if (stiva[n]==1) ev=0;
}
void main (){
int k,i;
clrscr();
printf("dati n par:"); scanf("%d",&n);
simbol[1]='('; simbol[2]=')';
k=1;stiva[k]=0;
while (k>0)
while (!( (as==0) || (as>0 && ev>0) ));
if (as>0)
else
}
else k--;
getch();
|
