Liceul Teoretic “Dunărea” Galați
Lucrare pentru atestarea competențelor
profesionale la informatică
Tema: Backtracking recursiv
Profesor coordonator: Elev:
Tudor Veronica Vatamaniuc Daniel
Clasa a XII-a C
2022
Cuprins
-Coperta
-Algoritmul Backtracking
-Argument
-Varianta recursiva a algoritmului de backtracking
-Notiuni introductive
-Probleme
-Concluzii
-Bibliografie
Algoritmul Backtracking
-Algoritm pentru gasirea solutiilor la unele probleme de calcul.
-Tehnica pentru listarea tuturor soluiilor posibile pentru un algoritm combinator.
Argument
Din cand in cand suntem pusi in situatia de a gasi o solutie optima la o problema, cu toate ca nu
exista nici o teorie aplicabila pentru rezolvarea acesteia, cu exceptia verificarii tuturor solutiilor.
Acest tip de probleme care necesita generarea tuturor solutiilor si, eventual, alegerea unei solutii
optime se rezolva cu ajutorul metodei backtracking. Funcția este recursivă, dacă definiția ei
folosește o referire la ea însăși, creând la prima vedere un cerc vicios, care însă este numai aparent,
nu și real.
Varianta recursiva a algoritmului de backtracking
Metoda backtracking poate fi implementată iterativ sau recursiv. În ambele situații se se folosește o
structură de deate de tip stivă. În cazul implementării iterative, stiva trebuie gestionată intern în algoritm –
ceea ce poate duce la dificulăți în implementăre. În cazul implementării recursive se folosește spațiu de
memorie de tip stivă – STACK alocat programului; implementarea recursivă este de regulă mai scurtă și mai
ușor de înțeles. Acest articol prezintă implementări recursive ale metodei. Procedurile si functiile folosite
sunt in general aceleasi,cu doua mici exceptii:
-SUCCESOR nu mai este procedura ci functie booleana ;
-Rutina backtracking se transforma in procedura,care se apeleaza prin BACK;
Următorul subprogram recursiv prezintă algoritmul la modul general:
la fiecare apel BACK(k) se generează valori pentru elementul x[k] al vectorului soluție;
instrucțiunea Pentru modelează condițiile externe;
subprogramul OK(k) verifică condițiile interne
subprogramul Solutie(k) verifică dacă configurația curentă a vectorului soluție reprezintă o soluție
finală
subprogramul Afisare(k) tratează soluția curentă a problemei – de exemplu o afișează!
subprogram BACK(k)
┌ pentru fiecare element i din A[k] executa
│ x[k] ← i
│ ┌ daca OK(k) atunci
│ │ ┌ daca Solutie(k) atunci
│ │ │ Afisare(k)
│ │ │ altfel
│ │ │ BACK(k+1)
│ │ └■
│ └■
└■
sfarsit_subprogram
Observații:
de cele mai multe ori mulțimile AA sunt de forma A={1,2,3,….,n}A={1,2,3,
….,n} sau A={1,2,3,….,m}A={1,2,3,….,m} sau A={a,a+1,a+2,….,b}A={a,a+1,a+2,….,b} sa
u o altă formă astfel încât să putem scrie instrucțiunea Pentru conform specificului
limbajului de programare folosit – eventual folosind o structură repetitivă de alt tip! Dacă este
necesar, trebuie realizate unele transformări încât mulțimile să ajungă la această formă!
elementele mulțimii AA pot fi in orice ordine. Contează însă ordinea în care le vom parcurge
în instrucțiunea Pentru, deoarece în probleme este precizată de obicei o anumită ordine în
care trebuie generate soluțiile:
o dacă parcurgem elementele lui AA în ordine crescătoare vom obține soluții în ordine
lexicografică;
o dacă parcurgem elementele lui AA în ordine descrescătoare vom obține soluții în
ordine invers lexicografică.
în anumite probleme determinarea unei soluții finale nu conduce la întreruperea apelurilor
recursive. Un exemplu este generarea submulțimilor unei mulțimi. În acest caz algoritmul de
mai sus poate fi modificat astfel:
┌ daca OK(k) atunci
│ ┌ daca Solutie(k) atunci
│ │ Afisare(k)
│ └■
│ BACK(k+1)
└■
Aplicatii
[Link] permutarilor
ENUNT : Fie n numar natural nenul. Scrieti un program de generare a
permutarilor de ordin n a elementelor multimii {1, 2, 3,..., n}.
EXEMPLU: Pentru n=3 programul va genera
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
SOLUTIE: Permutarile de ordin n reprezinta toate posibilitatile de a
aranja elementele unei multimi de n elemente.
I. Solutia x[1]......x[n] - x[i] va avea ca valoare un element al
multimii
II. x[k] poate avea ca valoare orice valoare din intervalul [1,n]
III. Valid - elementele trebuie sa fie distincte
x[k] trebuie sa fie diferit de x[1]...x[k-1]
Implementare
#include<iostream>
using namespace std;
char sp[]=" ";
int x[10], n, nrsol=0;
void Afisare()
{ int i;
cout<<sp;
for(i=1;i<=n;i++)
cout<<x[i]<<" ";
cout<<endl;
nrsol++;
if (nrsol%23==0) [Link]();
}
int Valid(int k)
{ int i;
for(i=1;i<=k-1;i++)
if (x[k]==x[i]) return 0;
return 1;
}
void BackRec(int k)
{ int i;
for(i=1;i<=n;i++)
{ x[k]=i;
if (Valid(k))
if (k==n) Afisare();
else BackRec(k+1);
}
}
int main()
{ cout<<endl<<endl<<sp<<"Permutarile primelor n numere naturale (n<10)"<<endl;
cout<<endl<<sp<<" Dati valoarea lui n: "; cin>>n;
cout<<endl;
BackRec(1);
cout<<endl<<sp<<"Numar solutii: "<<nrsol;
return 0;
}
[Link] submultimilor unei multimi
ENUNT : Fie n numar natural nenul. Scrieti un program de generare a
tuturor submultimilor multimii {1, 2, 3,..., n}.
EXEMPLU: Pentru n=3 programul va genera
{}
{1} {2} {3}
{1,2} {1,3} {2,3}
{1,2,3}
SOLUTIE:
I. Solutia x[1]......x[n]
- x[i] poate fi 0 (i nu apartine submultii) sau 1 (i apartine
submultimii)
Solutia Codificare
{} 0 0 0
{3} 0 0 1
{2} 0 1 0
{2,3} 0 1 1
{1} 1 0 0
{1,3} 1 0 1
{1,2} 1 1 0
{1,2,3} 1 1 1
II. x[k] poate fi 0 sau 1
III. Valid - nu este necesar
Implementare
#include<iostream>
using namespace std;
char sp[]=" ";
int x[20], n, nrsol=0;
void Afisare()
{ int i;
cout<<sp<<"{ ";
for(i=1;i<=n;i++)
if (x[i]==1) cout<<i<<" ";
cout<<char(8)<<"}"<<endl;
nrsol++;
if (nrsol%22==0) [Link]();
}
void BackRec(int k)
{ int i;
for(i=0;i<=1;i++)
{ x[k]=i;
if (k==n) Afisare();
else BackRec(k+1);
}
}
int main()
{ cout<<endl<<endl<<sp<<"Submultimile multimii {1,2,3.....,n}"<<endl;
cout<<endl<<sp<<" Dati valoarea lui n: "; cin>>n;
cout<<endl;
BackRec(1);
cout<<endl<<sp<<"Numar solutii: "<<nrsol;
return 0;
}
In cazul variantei recursive rutina back se defineste ca o functie recursiva cu parametrul k (nivelul
curent din stiva). Urcarea in stiva se face prin autoapelul functiei back cu o noua valoare pentru
k. Generarea potentialilor candidati la solutie se face print-o instructiune for care parcurge valorile posibile
de la limita inferioara la limita superioara. Iata solutia pentru problema permutarilor.
#include<iostream.h>
#include<conio.h>
int st[20],n;
void tipar()
{for(int i=1;i<=n;i++)
cout<<st[i]<<' ';
cout<<endl;}
int valid(int k)
{ for(int i=1;i<=k-1;i++)
if (st[i]==st[k])
return 0;
return 1;}
void back(int k)
{for(int i=1;i<=n;i++)
{st[k]=i;
if (valid(k))
if(k==n)
tipar();
else
back(k+1);
}
}
void main()
{clrscr();
cout<<"n=";
cin>>n;
back(1);
getch();
}