Difference between revisions of "Clasa a XI-a lecția 2"

From Algopedia
Jump to: navigation, search
(Created page with "= Backtracking = === Prezentare Generala === Backtracking s-ar putea traduce “drum înapoi”, “cale întoarsă” sau “revenire” ceea ce sugerează faptul că orice...")
 
(Varianta Tudor Sorin usor modificata)
(4 intermediate revisions by the same user not shown)
Line 61: Line 61:
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 
+
==== -- ====
 
<syntaxhighlight>
 
<syntaxhighlight>
 
void back(){  
 
void back(){  
Line 69: Line 69:
 
   while ( k > 0 ){  
 
   while ( k > 0 ){  
 
     As = Am_Succesor();  
 
     As = Am_Succesor();  
    Ev = E_valid();
+
     if ( As ){            // Daca am completat cu o valoare noua
     if ( As )           // Daca am completat cu o valoare noua
+
      if ( E_valid() )    // Verific daca solutia construita e valida
    if ( Ev )           // Verific daca solutia construita e valida
+
        if (Solutie())    // verific daca am o solutie finala
      if (Solutie())    // verific daca am o solutie finala
+
          Tipar();         // daca da, tiparesc
        Tipar();       // daca da, tiparesc
+
        else {            // daca nu
      else {            // daca nu
+
          k++;            // urc in stiva
        k++;            // urc in stiva
+
          Init();          // pun o valoare initiala pe acest nivel
        Init();          // pun o valoare initiala pe acest nivel
+
      }
      }  
+
    }
 
     else  
 
     else  
 
       k--;  
 
       k--;  
Line 245: Line 245:
 
   fout << '\n';
 
   fout << '\n';
 
}
 
}
void back(){
+
void back(){  
   k = 1;                 // plecam de la nivelul 1 al stivei
+
  int As;
   st[1] = 0;             // initializam valoarea de pe prima pozitie a stivei
+
   k = 1;  
   while( k > 0){         // daca nu am iesit din stiva, adica mai am solutii de verificag
+
   Init();  
     if( st[k] < n ){     // daca am un succesor
+
   while ( k > 0 ){  
      st[k]++;            // punem o noua valoare pe stiva
+
    As = Am_Succesor();
       if( e_valid()){     // daca e valida
+
     if ( As ){             // Daca am completat cu o valoare noua
         if( k == n )     // daca e solutie finala, aici daca am completat toata stiva de dim n
+
       if ( E_valid() )    // Verific daca solutia construita e valida
           tipar();       // tiparesc solutia
+
         if (Solutie())     // verific daca am o solutie finala
         else{            // daca nu am solutie finala
+
           Tipar();         // daca da, tiparesc
           k ++;           // urc in stiva si pun o valoare initiala;
+
         else {            // daca nu
           st[k] = 0;     // val de pornire pe ac. nivel este 0
+
           k++;             // urc in stiva
        }
+
           Init();         // pun o valoare initiala pe acest nivel
      }
+
      }  
 
     }
 
     }
     else{                // daca nu mai am succesor pe pozitia k
+
     else  
       k--;               // cobor un nivel in stiva
+
       k--;  
                        // valoarea de pornire este valoarea deja existenta pe nivelul pe care am coborat
+
   }  
    }
 
   }
 
 
}
 
}
 
int main(){
 
int main(){

Revision as of 08:41, 13 September 2019

Backtracking

Prezentare Generala

Backtracking s-ar putea traduce “drum înapoi”, “cale întoarsă” sau “revenire” ceea ce sugerează faptul că orice vector soluţie este construit progresiv, începând cu prima componentă şi mergând spre ultima, cu eventuale reveniri asupra valorilor atribuite anterior (revenire care presupune un pas sau chiar mai mulţi paşi înapoi).

Această tehnică poate fi utilizată pentru rezolvarea problemelor de căutare. Căutarea efectuată este exhaustivă, putând fi folosită pentru generarea tuturor soluţiilor posibile.

Se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

  • Soluţia lor poate fi pusă sub forma unui vector V = x1x2x3 ……. xn, cu x1∈A1 …. xn ∈ An (sau sub forma unor alte structuri de date precum tablouri bidimensionale)
  • Mulţimile A1, A2, … An sunt mulţimi finite, iar elementele lor se află într-o ordine bine stabilită
  • Nu se dispune de o metodă de rezolvare mai rapidă

La întâlnirea unei astfel de probleme suntem tentaţi să generăm toate elementele produsului cartezian A1 × A2 × …. × An. Aceasta nu este totuşi o rezolvare foarte rezonabilă. Timpul de execuţie este atât de mare, încât poate fi considerat infinit.

Dacă de exemplu dorim să generăm toate permutările unei mulţimi, generând produsul cartezian, am putea obţine 1,1,1,….1, pentru ca apoi să constatăm că nu am obţinut o permutare (cifrele nu sunt distincte), deşi chiar de la a 2-a cifră se poate observa că cifrele nu sunt distincte.

Tehnica Backtracking are la bază un principiu extrem de simplu: se construieşte soluţia pas cu pas. Dacă se constată că pentru o anumită valoare nu se poate ajunge la soluţie, se renunţă la acea valoare şi se reia căutarea din punctul unde am rămas.

Prezentarea algoritmului

Pentru uşurarea înţelegerii metodei vom prezenta o rutină unică, aplicabilă oricărei probleme, rutină care utilizează noţiunea de stivă:

  • se alege primul element x1, ce aparţine lui A1;
  • presupunând generate elementele x1…xk, vom avea 2 posibilităţi:
    • nu s-a găsit un astfel de element, caz în care se reia căutarea, considerând generate elementele x1 … xk-1, iar aceasta se reia de la următorul element Ak, rămas netestat.
    • a fost găsit, caz în care se testează dacă acesta îndeplineşte anumite condiţii (răspunsul poate fi verificat de o funcţie Validare care returnează true sau false).
    • dacă le îndeplineşte, se testează dacă s-a ajuns la soluţie (se utilizează funcţia Soluţie, care returnează true dacă s-a ajuns la soluţie):
      • dacă s-a ajuns la soluţie, se tipăreşte şi se continuă algoritmul pentru găsirea unei alte soluţii, considerându-se generate x1…xk, iar elementul xk+1 se caută printre elementele mulţimii Ak+1 rămase netestate
      • dacă nu s-a ajuns la soluţie se reia algoritmul considerându-se generate elementele x1, … xk, xk+1
    • dacă nu le îndeplineşte se reia algoritmul considerând generate x1…xk, iar elementul xk+1 se caută printre elementele mulţimii Ak+1 rămase netestate

Pentru rezolvarea problemelor cu metoda backtracking se utilizează o stivă în care la fiecare nivel k se află un element xk in mulţimea Ak şi următoarele funcţii:

  • funcţia void Init(); - la urcarea în stivă, pe nivelul la care s-a ajuns pe pune o valoare care nu se află în mulţimea considerată, dar de la care, la pasul următor, se ajunge la primul element din acea mulţime
  • funcţia int Am_Succesor(); - pe un anumit nivel găsirea elementului următor celui considerat, element netestat; funcţia returnează 1, dacă există succesor acesta fiind pus în stivă şi 0 în caz contrar
  • funcţia int Valid(); - verifică dacă elementul ales îndeplineşte sau nu condiţiile de continuitate ale problemei, ea returnează 1 dacă le îndeplineşte şi 0 în caz contrar.
  • funcţia int Solutie(); - testează dacă s-a ajuns sau nu la soluţia finală, returnând 1, respectiv 0.
  • funcţia void Tipar(); - tipăreşte soluţia.


Cu aceste notaţii rutina backtracking este următoarea:

void back(){ 
  int As; 
  k=1; 
  Init(); 
  while (k>0){ 
    do { } while ((As=Am_Succesor()) && !Valid()); 
  if (As) 
    if (Solutie()) 
      Tipar(); 
    else { 
      k++; 
      Init(); 
    } 
  else 
    k--; 
  } 
}

--

void back(){ 
  int As; 
  k = 1; 
  Init(); 
  while ( k > 0 ){ 
    As = Am_Succesor(); 
    if ( As ){             // Daca am completat cu o valoare noua
      if ( E_valid() )     // Verific daca solutia construita e valida
        if (Solutie())     // verific daca am o solutie finala
          Tipar();         // daca da, tiparesc
        else {             // daca nu
          k++;             // urc in stiva
          Init();          // pun o valoare initiala pe acest nivel
       } 
    }
    else 
      k--; 
  } 
}

Permutari

Permutari PbinfoSe citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările mulţimii {1,2,..,n}.

Varianta Tudor Sorin

#include <fstream>

using namespace std;

int st[100], k, n;

ifstream cin("permutari.in");
ofstream cout("permutari.out");

void Init(){
  st[k] = 0;
}

int As(){
  st[k] ++;
  return st[k] <= n;
}

int Ev(){
  for ( int i = 0; i < k; i ++ )
    if( st[i] == st[k] )
      return 0;
  return 1;
}
int Sol(){
  return k == n - 1;
}
void Tipar(){
  for ( int i = 0; i < n; i ++ )
    cout << st[i];
  cout << "\n";
}
void back(){
  int AS, EV;
  k = 0;
  Init();
  while( k >= 0 ){
    do{
      AS = As();
      EV = Ev();
    } while ( AS && !EV );
    if( AS )
      if( Sol() )
        Tipar();
      else {
        k ++;
        Init();
      }
    else
      k--;
  }
}
int main(){
  cin >> n ;
  back();
  return 0;
}

Mai jos aveti si varianta originala a algoritmului, in care vectorul solutie era indexat de la 1;


#include <fstream>
using namespace std;

int st[10], n, k;

ifstream fin("permutari.in");
ofstream fout("permutari.out");

void Init (){
  st[k] = 0;
}

int Am_Succesor (){
    if ( st[k] < n ){
       st[k]++;
       return 1;
    }
   else return 0;
}

int E_Valid(){
  for ( int i = 1; i < k; i++ )
    if ( st [i] == st [k] )
      return 0;
  return 1;
}

int Solutie (){
  return k == n;
}

void Tipar ( ){
   for(int i = 1; i <= n; i++ )
     fout <<st [i];
   fout<<'\n';
}
void back( ){
  int AS, EV;
  k=1; Init( );
  while( k > 0 ){
    do {
      AS = Am_Succesor( );
      EV = E_Valid( );
    }while ( AS && !EV );
    if( AS )
      if (Solutie( ) )
        Tipar ( ) ;
      else {
        k++;
        Init( );
      }
  else
    k--;
  }
}
int main ( ){
  fin >> n;
  back( );
  return 0;
}

Varianta Tudor Sorin usor modificata

Modificam usor programul asa incat sa eliminam buclele imbricate while, do-while in care se incurca multi dintre voi; de altfel, ati invatatat cum o astfel de bucla dubla poate fi transformata foarte usor intr-o bucla while, if. Astfel, vom privi lucrurile astfel: cat timp suntem pe stiva, pe un nivel k>0, avem urmatoarele posibilitiati:

  • avem succesor valid - daca am completat o solutie, o tiparim daca nu vom urca in stiva resetand valoarea de pe nivelul urmator
  • avem un succesor nevalid, nu facem nimic( observam ca nu avem else la if (e_valid())
  • nu avem succesor - coboram in stiva.

Obs: Am eliminat functia "am succesor";

#include <iostream>
#include <fstream>
using namespace std;
int st[10], n, k;
ofstream fout("permutari.out");

int e_valid( ){
  int j;
  for( j = 1 ; j < k ; j++ )
    if( st[j] == st[k] )
      return 0;
  return 1;
}

void tipar(){
  for( int i = 1; i <= n; i++ )
    fout << st[i] << " ";
  fout << '\n';
}
void back(){ 
  int As; 
  k = 1; 
  Init(); 
  while ( k > 0 ){ 
    As = Am_Succesor(); 
    if ( As ){             // Daca am completat cu o valoare noua
      if ( E_valid() )     // Verific daca solutia construita e valida
        if (Solutie())     // verific daca am o solutie finala
          Tipar();         // daca da, tiparesc
        else {             // daca nu
          k++;             // urc in stiva
          Init();          // pun o valoare initiala pe acest nivel
       } 
    }
    else 
      k--; 
  } 
}
int main(){
  cin >> n;
  back();
  return 0;
}

Optimizare varanta1 - punem pe stiva si validam valoarea pusa

Modificam usor programul asa incat la validarea valorilor puse sa nu mai parcurgem toata stiva pentru a vedea daca o valoare a fost folosita sau nu. Ganditi-va ca aveți o singură caciulă cu bile numerotate de la 1 la n și din ea, trebuie să luați câte o bilă la fiecare pas. Având in vedere că pana la un pas k ați luat deja din căciulă un numar k-1 de bile, e clar ca pe o pozitie k pute sa punem doar din valorile ramase in caciulâ. Cum simulam continutul caciulii? Sigur ca ati ghicit, cel mai simplu, cu un vector de frecventa.

Obs. Avand in vedere ca validarea se reduce acum la a privi in vector pe o pozitie data, putem sa renuntam si la
apelul uni functii de validare.
De remarcat cand facem operatiile de modificare a vectorului folosit:
* fie cand am cazut pe un nivel inferior si trebuie sa inlocuiesc bila de pe nivelul curent
* fie cand am reusit sa gasesc o valoare buna pe nivelul curent si trebuie sa marchez in stiva ca am folosit inca un numar. Iata o implementare imbunatatita a algoritmului initial.
#include <fstream>

using namespace std;

int st[10], k, n;
int folosit[10];
ifstream cin( "permutari.in" );
ofstream cout( "permutari.out" );


void Tipar(){
  for ( int i = 0; i < n; i ++ )
    cout << st[i];
  cout << "\n";
}
void back(){
  k = 0;
  st[k] = 0;          // initializam val de pe niv 0
  while( k >= 0 ){    // cata vreme sunt pe stiva
    if( st[k] < n ){  // mai am valori netestate, adica mai am un succesor
      st[k]++;        // punem o noua val pe nivelul curent
      if ( !folosit[st[k]] ){   // daca val pusa nu a mai fost folosita, adica e valida
        if( k == n - 1 )        // daca am sol finala
          Tipar();              // o tiparesc
        else {
          folosit[st[k]] = 1;
          k ++;
          st[k] = 0;
        }
      }
    }
    else { // daca nu am succesor
      k--;
      folosit[st[k]] = 0;
    }
  }
}
int main(){
  cin >> n ;
  back();
  return 0;
}

Cu indexare de la 1 a vectorului de sol, algoritmul va arata ca mai jos:

#include <iostream>
#include <fstream>
using namespace std;
int st[10], n, k;
int folosit[10];
ofstream fout("permutari.out");
/*inutil de scris o astfel de functie
int e_valid( ){
  int j;
  if( folosit[st[k]] == 1 )
      return 0;
  return 1;
}
*/
void tipar(){
  for( int i = 1; i <= n; i++ )
    fout << st[i] << " ";
  fout << '\n';
}
void back(){
  k = 1;                      // plecam de la nivelul 1 al stivei
  while( k > 0){              // daca nu am iesit din stiva, adica mai am solutii de verificat
    if( st[k] < n ){          // daca am un succesor al valorii de pe nivelul curent
      st[k]++;                // punem o noua valoare
      if( !folosit[st[k]]){   // si acesta e valid, adica nu a fost anterior folosit
        if( k == n ) {        // daca e solutie finala, adica daca am completat toata stiva de dim n
          tipar();            // o tiparesc si nici nu ma mai preocup sa marchez valoarea ca folosita, caci e ultima
        }
        else{                 // daca nu sm solutie finala
          folosit[st[k]] = 1; // marchez ca folosita valoarea valida pe care tocmai am pus-o
          st[++k] = 0;        // urc in stiva si pun o valoare initiala;

        }
      }
    }
    else{                   // daca nu mai am succesor pe pozitia k
      k--;                  // cobor un nivel in stiva
      folosit[st[k]] = 0;   // valoarea de pe pozitia pe care am coborat, e o val folosita, noi o vom inlocui, deci o marchez ca nefolosit
    }
  }
}
int main(){
  cin>>n;
  back();
  return 0;
}

Optimizare varanta2 - punem pe stiva doar valori valide

Aceasta varianta nu este o optimizare a primei variante, ci un alt mod de implementare. In varianta precedenta modificam valorile de pe stiva, punand valori nevalide, ceea ce poate parea ciudat pentru unii dintre voi. Putem sa folosim o variabila ajutatoare, asa incat sa nu mai fim nevoiti sa modficam valoarea de pe o pozitie st[k] decat atunci cand am gasit o valoare care poate conduce la solutie finala. Iata o implementare a acestei idei:

#include <iostream>
#include <fstream>
using namespace std;
int st[10], n, k;
int folosit[10];
ofstream fout("permutari.out");

void tipar(){
  for( int i = 1; i <= n; i++ )
    fout << st[i] << " ";
  fout << '\n';
}
void back(){
  k = 1;                      // plecam de la nivelul 1 al stivei
  int i = 0;                  // valoarea de la care voi cauta succesori
  while( k > 0){              // daca nu am iesit din stiva, adica mai am solutii de verificat
    if( i < n ){              // daca am un succesor al valorii de pe nivelul curent
      i++;                    // trecem la urmatoarea valoare netestata
      if( !folosit[i]){       // daca nu a fost anterior folosita
        st[k] = i;            // pun in stiva valoarea
        if( k == n ) {        // daca e solutie finala
          tipar();            // o tiparesc si nici nu ma mai preocup sa marchez valoarea ca folosita, caci e ultima
        }
        else{                 // daca nu sm solutie finala
          folosit[st[k]] = 1; // marchez ca folosita valoarea valida pe care tocmai am pus-o
          k ++;               // urc pe urmatorul nivel
          i = 0;              // resetez la 0 contorul ce parcurge succesorii
        }
      }
    }
    else{                   // daca nu mai am succesor pe pozitia k
      k--;                  // cobor un nivel in stiva
      folosit[st[k]] = 0;   // valoarea de pe pozitia pe care am coborat, e o val folosita, noi o vom inlocui, deci o marchez ca nefolosit
      i = st[k];            // succesorii vor fi cautati pornind de la valoarea existenta
    }
  }
}
int main(){
  cin>>n;
  back();
  return 0;
}

Permutari cu functii de biblioteca

#include <iostream>
#include <algorithm>
 
using namespace std; 
const int MAXN = 10;
 
int v[MAXN];
 
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
      v[i] = i + 1;
    do {
      for (int i = 0; i < n; ++i)
        cout << v[i] << " ";
      cout << '\n';
    } while ( next_permutation(v, v + n) == true );
    return 0;
}

Aranjamente

Aranjamente varianta iterativa

#include <iostream>
#include <fstream>
using namespace std;
int st[10], n, k, p;
int folosit[10];

ifstream  fin("aranjamente.in");
ofstream fout("aranjamente.out");


void tipar(){
  for( int i = 1; i <= p; i++ )
    fout << st[i] << " ";
  fout << '\n';
}
void back(){
  k = 1;                      // plecam de la nivelul 1 al stivei
  st[k] = 0;                  // punem o val initiala
  while( k > 0){              // daca nu am iesit din stiva, adica mai am solutii de verificat
    if( st[k] < n ){          // daca am un succesor al valorii de pe nivelul curent
      st[k]++;                // punem o noua valoare
      if( !folosit[st[k]]){   // si acesta e valid, adica nu a fost anterior folosit
        if( k == p )          // daca e solutie finala
          tipar();            // o tiparesc si nici nu ma mai preocup sa marchez valoarea ca folosita, caci e ultima
        else{                 // daca nu sm solutie finala
          folosit[st[k]] = 1; // marchez ca folosita valoarea valida pe care tocmai am pus-o
          st[++k] = 0;        // urc in stiva si pun o valoare initiala;
        }
      }
    }
    else{                   // daca nu mai am succesor pe pozitia k
      k--;                  // cobor un nivel in stiva
      folosit[st[k]] = 0;   // valoarea de pe pozitia pe care am coborat, e o val folosita, noi o vom inlocui, deci o marchez ca nefolosit
    }
  }
}
int main(){
  fin>>n>>p;
  back();
  return 0;
}

Problema Damelor

Problema Damelor varianta iterativa

#include <fstream>
#include <math.h>
using namespace std;
int st[10], n, k;

int e_valid( ){
  int i;
  for( i = 1 ; i < k ; i++ )
    if( st[i] == st[k] || fabs(st[k]-st[i]) == fabs(k-i) )
      return 0;
  return 1;
}

void tipar(){
  int i, j;
  for ( i = 1; i <= n; i++ ){
    for ( j = 1; j <= n; j++ )
      if( st[i] == j )
        cout <<"* ";
      else
        cout <<"- ";
    cout<<endl;
  }
}
void back(){
  k = 1;                  // plecam de la nivelul 1 al stivei
  while( k > 0){          // daca nu am iesit din stiva, adica mai am solutii de verificag
    if( st[k] < n ){      // daca am un succesor
      st[k]++;            // punem o noua valoare
      if( e_valid()){     // il adaug pe stiva
        if( k == n ){     // daca e solutie finala, aici daca am completat toata stiva de dim n
          tipar();
          // k = 0;          // daca dorim sa tiparim doar o solutie, intrerupem generarea solutiilor
        }
        else{             // daca nu sm solutie finala
          k ++;           // urc in stiva si pun o valoare initiala;
          st[k] = 0;      // val de pornire pe ac. nivel este 0
        }
      }
    }
    else                // daca nu mai am succesor pe pozitia k
      k--;               // cobor un nivel in stiva
  }
}
int main(){
  cin>>n;
  back();
  return 0;
}

Aplicatii

Extindere

Alte probleme cu permutari

  • Determinarea numarului de inversiuni ale unei permutari ( de adaugat pe varena)
  • Afisarea permutarilor in ordine crescatoare dupa numarul de inversiuni. Permutarile cu acelasi numar de inversiuni vor fi afisate in ordine crescatoare.
  • 2 Afisarea permutarilor impare ( Permutarile pare sunt cele care au numar par de inversiuni )

Ex: Pentru n = 4, vom alege doar permutarile cu numar par de inversiuni. Putem observa ca numarul de permutari cu numar par de inversiuni este egal cu numarul de permutari cu numar impar de inversiuni.

1 2 3 4  nrinv = 0
1 2 4 3  nrinv = 1
1 3 2 4  nrinv = 1
1 3 4 2  nrinv = 2
1 4 2 3  nrinv = 2
1 4 3 2  nrinv = 3
2 1 3 4  nrinv = 1
2 1 4 3  nrinv = 2
2 3 1 4  nrinv = 2
2 3 4 1  nrinv = 3
2 4 1 3  nrinv = 3
2 4 3 1  nrinv = 4
3 1 2 4  nrinv = 2
3 1 4 2  nrinv = 3
3 2 1 4  nrinv = 3
3 2 4 1  nrinv = 4
3 4 1 2  nrinv = 4
3 4 2 1  nrinv = 5
4 1 2 3  nrinv = 3
4 1 3 2  nrinv = 4
4 2 1 3  nrinv = 4
4 2 3 1  nrinv = 5
4 3 1 2  nrinv = 5
4 3 2 1  nrinv = 6 n(n-1)/2

Nr de permutari cu numar de inversiuni pare = n!/2

  • Afisarea permutarii a n elemente cu exact m inversiuni, cea mai mica lexicografic.
  • 3 Determinarea numarului de cicluri ale unei permutari Problema Loc

Articole

Tema

Tema usoara

Tema nivel oji / oni

Avioane