Backtracking – generare permutari si combinari

Cu totii stim ca Backtracking este una din cele mai cunoscute tehnici de programare. Ideea din spatele acestui algoritm este de a genera toate solutiile posibile si a le abandona in cazul in care observa ca nu indeplinesc conditiile necesare. Datorita generarii tuturor solutiilor, complexitatea algoritmului este foarte mare, dar duce sigur la generarea tuturor posibilitatilor valide. Din aceasta cauza, e o tehnica foarte cunoscuta in randul programatorilor (in special a celor care participa la concursuri si olimpiade de informatica) deoarece este considerata solutia ce trebuie abordata in cazul in care nu ai nici o idee.

Structura unei functii backtracking

  void back(int k)
  {
     if(reject_sol(k)) return;
     if(accept_sol(k)) show_sol(k);
     for(i=0;i<n;i++)
     {
        v[k]=set();
        back(k+1);
        v[k]=unset();
     }
  }

Generarea tuturor permutarilor

Problema : Sa se genereze toate permutarile multimii {1, 2, …N}, in ordine lexicografica.
Solutie : Din moment ce problema ne cere generarea tuturor solutiilor, este evident ca vom avea nevoie de o abordare backtracking.

#include<cstdio> 
int a[10],b[10];

void back(int k,int len)
{
     if(k-1 == len)   //afisam solutia
     {
         for(int i = 1; i <= len;i++)
           printf("%d ",a[i]);
         printf("\n");
     }     
     else
     {
         for(int  i = 1; i <= len; i++)
            if(!b[i])  //daca valoarea nu-i folosita
           {
                 a[k] = i; 
                 b[i] = 1; //o folosim
                 back(k+1,len); //trecem la pasul urmator
                 b[i] = 0; //o eliberam
           } 
     }
}

int main()  
{   
    freopen("permutari.in","r",stdin);
    freopen("permutari.out","w",stdout); 
    int n;
    scanf("%d",&n);
    back(1,n);  
    fclose(stdin); fclose(stdout);  
    return 0;
}  

Generarea tuturor combinarilor de n luate cate k

Problema : Sa se genereze toate combinarile de N luate cate K in ordine lexicografica.
Solutie : Din moment ce si aceasta problema ne cere generarea tuturor posibilitatilor este evident ca solutia este una ce are nevoie de o abordare backtracking.

#include<cstdio> 
int a[19],b[19];

void back(int k,int len,int max)
{
     if(k-1 == max) //afisam solutia
     {
         for(int i = 1; i <= max;i++)
           printf("%d ",a[i]);
         printf("\n");
     }     
     else
     {
         for(int  i = 1; i <= len; i++)
            if(!b[i] && a[k-1] < i)  //ne asiguram ca generam solutiile crescatoare si unice
           {
                 a[k] = i;
                 b[i] = 1; //o folosim
                 back(k+1,len,max); //trecem la pasul urmator
                 b[i] = 0;   //o eliberam
           }
     }
}

int main()  
{   
    freopen("combinari.in","r",stdin);
    freopen("combinari.out","w",stdout); 
    int n,k;
    scanf("%d %d",&n,&k);
    back(1,n,k);  
    fclose(stdin); fclose(stdout);  
    return 0;
}  

Aplicatii Backtracking

1. Generarea aranjamentelor
2. Problema damelor
3. Problema turelor
4. Generarea produsului cartezian a n multimi
5. Sa se genereze n perechi de parantezari care se inchid corect
6. Cel mai lung prefix

Concluzie

Aceasta metoda este extrem de raspandita si de utila in cazul problemelor in care generarea tuturor solutiilor este necesara. De asemenea, in cazul concursurilor este una din cele mai populare modalitati de „furare” a catorva puncte.

Referinte

http://infoscience.3x.ro/c++/pbbacktracking.html
http://infoarena.ro/problema/combinari
http://infoarena.ro/problema/permutari
http://en.wikipedia.org/wiki/Backtracking
http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html