Cuprins
Exemplu. Pentru problema generării permutărilor mulțimii A={1,2,3,…,n}A={1,2,3,
…,n}, condițiile de mai sus sunt:
1. Vectorul soluție conține o permutare a mulțimii AA;
2. Condiții externe: x[k]∈{1,2,3,…,n}x[k]∈{1,2,3,
…,n} sau x[k]=1,n¯¯¯¯¯¯¯¯x[k]=1,n¯, pentru k=1,n¯¯¯¯¯¯¯¯k=1,n¯
3. Condiții interne: x[k]≠x[i]x[k]≠x[i], pentru i=1,k−1¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯i=1,k−1¯
4. Condiții de existență a soluției: k=n
De cele mai multe ori, rezolvarea unei probleme folosind metoda backtracking constă
în următoarele:
1. stabilirea semnificației vectorului soluție;
2. stabilirea condițiilor externe;
3. stabilirea condițiilor interne;
4. stabilirea condițiilor de existența a soluției finale;
5. completarea adecvată a șablonului de mai sus!
Algoritmul general
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ă!
dacă parcurgem elementele lui AA în ordine crescătoare vom obține soluții în ordine
lexicografică;
dacă parcurgem elementele lui AA în ordine descrescătoare vom obține soluții în
ordine invers lexicografică
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
┌ daca OK(k) atunci
│ ┌ daca Solutie(k) atunci
│ │ Afisare(k)
│ └■ │ BACK(k+1)
Un șablon C++
#include <fstream>
using namespace std;
int x[10] ,n;
int Solutie(int k){
// x[k] verifică condițiile interne
// verificare dacă x[] reprezintă o soluție finală
return 1; // sau 0}
int OK(int k){ // verificare conditii interne
return 1; // sau 0}
void Afisare(int k)
{ // afișare/prelucrare soluția finală curentă}
void Back(int k){
for(int i = A ; i <= B ; ++i)
{
x[k]=i;
if( OK(k) )
if(Solutie(k))
Afisare(k);
else
Back(k+1);
}}
int main(){
//citire date de intrare
Back(1); return 0;}
Generarea-permutarilor
#include <iostream> using namespace std;
int x[10] ,n;
void Afis() { for( int j=1;j<=n;j++) cout<<x[j]<<" "; cout<<endl;}
bool OK(int k){
for(int i=1;i<k;++i)
if(x[k]==x[i])
return false;
return true;}
bool Solutie(int k) { return k == n;}
void back(int k){
for(int i=1 ; i<=n ; ++i)
{ x[k]=i;
if( OK(k) )
if(Solutie(k))
Afis();
else
back(k+1);
}
}
int main(){ cin>>n; back(1); return 0;}
void Afis(); afișează soluția curentă. Când se apelează, vectorul
soluție x are n elemente, reprezentând o permutare completă;
bool OK(int k); verifică condițiile interne. La apel, x[k] tocmai a primit o valoare
conform condițiilor externe. Prin funcția OK() se va verifica dacă această valoare este
validă;
bool Solutie(int k); verifică dacă avem o soluție completă. Acest lucru se
întâmplă când permutarea este completă – am dat o valoare corectă ultimului
element al tabloului, x[n], adică atunci când k=n;
void back(int k); – apelul acestei funcții dă valori posibile elementului x[x] al
vectorului soluție și le verifică:
o se parcurg valorile pe care le pot lua elementele vectorului, conform condițiilor
externe (în acest caz, 1..n);
se memorează în x[k] valoarea curentă;
dacă valoarea lui x[k] este corectă, conform condițiilor interne, se
verifică dacă avem o soluție completă. În caz afirmativ se afișează
această soluție, în caz contrar se trece la următorul element, prin
apelul recursiv;
o la finalul parcurgerii, se revine la elementul anterior al vectorului x, prin
revenirea din apelul recursiv.
algoritmul este exponențial și poate fi folosit numai pentru valori mici ale lui n. O
soluție ceva mai bună se poate obține dacă, pentru a stabili corectitudinea condițiilor
interne, evităm parcurgerea elementelor deja memorate în vectorul soluție. Acest
lucru poate fi realizat prin intermediul unui vector caracteristic, cu semnificația: v[p]
= 1 dacă valoarea p face deja parte din permutare, și v[p]=0 dacă p nu face parte
din permutare
Varianta mai optima
#include <iostream>
using namespace std;
int x[10] , n , p, uz[10];
void Afis(int k)
{ for(int j = 1 ; j <= k ; j ++)
cout << x[j] << " ";
cout << endl;}
void back(int k){
for(int i = 1 ; i <= n ; ++ i)
if(uz[i] == 0)
{
x[k] = i;
uz[i] = 1;
if(k == n)
Afis(k);
else
back(k + 1);
uz[i] = 0;
}}
int main(){ cin >> n; back(1); return 0;}