Bactracking recursiv

  1. Funcţia back are un parametru întreg k şi funcţionează astfel:

- dacă s-a ajuns la o soluţie, se tipăreşte şi se revine la nivelul anterior

void back(int k)

{

  if(solutie(k)) afis(x,k);

- dacă nu s-a ajuns la o soluţie

else

- se iniţializează nivelul

{

  x[k]=0;

- atâta timp cât este succesor pe acest nivel

while(succ(x,k))

    {

- dacă este valid, funcţia back se autoapelează pentru k+1

valid(x,k,ev)

  if(ev)

  back(k+1);

- dacă nu este succesor, se trece pe nivelul k-1 prin ieşirea din funcţia back.

2. Funcţia succ verifică dacă mai sunt elemente în Sk.

3. Funcţia valid verifică dacă sunt satisfăcute condiţiile de continuare

4. Funcţia afiş afişează o soluţie rezultat

5. Funcţia soluţie returnează  

  1 dacă pe nivelul k s-a ajuns la soluţie

    0 dacă pe nivelul k nu s-a ajuns la soluţie

În general funcţia soluţie se defineşte astfel:

int soluţie(int k)

{

  return(k==n+1)

}

Problema colorării hărţilor

Fiind dată o hartă cu n tări, se cer toate modalităţile de colorare a hărţii, utilizând cel mult m culori, astfel încât două ţări cu frontieră comună să fie colorare diferit. Este demonstrat faptul că sunt suficiente numai 4 culori ca orice hartă să poată fi colorată.

Pentru rezolvare se vor folosi:

k: variabilă întreagă, care reprezintă o ţară

x: vector cu componente întregi cu proprietatea xk reprezintă culoarea ţării cu numărul k

deoarece sunt n ţări şi m culori, k={1,...,n} şi xk={1,...,m}

x=(x1,x2,...,xn) unde xkÎ{1,...,n}.

Concluzie:

Ţara k şi ţara i sunt vecine, dacă (ai,k=1) sau (ak,i=1)

Ţara k şi ţara i au aceeaşi culoare dacă xk=xi

Comentarii la funcţia valid:

Trebuie verificat dacă ţara k şi ţara i ce sunt ţări vecine au culori diferite, adică dacă

ak,i=1 pentru xk¹xi, pentru i=1...k-1.

#include<iostream.h>

#include<math.h>

typedef int sir[100];

sir x;

int m,i,k,n,j;

int as,ev;

int a[100][100];

void succ(sir x, int k, int &as)

{

if(x[k]<n)

  {

  as=1;

  x[k]=x[k]+1;

  }

else as=0;

}

void valid(sir x, int k, int &ev)

{

ev =1;

for(i=1;i<=k-1;i++)

  if((a[k][i]==1)&&(x[k]==x[i]))

  ev=0;

}

void afis(sir x,int k)

{

int i;

for(i=1;i<=k;i++)

  cout<<x[i]<<" ";

cout<<endl;

}

Se verifică dacă ai,k=1 atunci

xk¹xi, unde i=1,...k-1

int main(void)

{

cout<<"Dati numarul de tari:";

cin>>n;

for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

  cin>>a[i][j];

  a[j][i]=a[i][j];

  }

k=1;

x[k]=0;

while(k>0)

  {

    do

      {

        succ(x,k,as);

        if(as) valid(x,k,ev);

      }

    while(as&&!ev);

    if(as)

        if(k==n) afis(x,k);

        else

  {

    k=k+1; x[k]=0;

  }

    else k=k-1;

    }

}

Combinari

Fiind dată o mulţime A cu n elemente, a combina elementele mulţimii în grupe de câte p<n elemente înseamnă a determina toţi vectorii cu p elemente ale căror componente aparţin mulţimii A şi sunt sortate crescător.

Ne gândim la generarea combinărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma unui vector cu p<n elemente, astfel încât să nu aibă importanţă ordinea pe care o au în cadrul şirului. Componentele sunt sortate crescător şi aparţin mulţimii date.

Fie A={1,2,3}. Combinările mulţimii A în grupe de câte două elemente sunt (1,2), (1,3), (2,3).

#include<iostream.h>

#include<stdio.h>

typedef int sir[100];

sir x;

int i,k,m,p;

int as,ev;

sir a;

void succ(sir x, int k, int &as)

{

if(x[k]<m)

  {

  as=1;

  x[k]=x[k]+1;

  }

else as=0;

}

void valid(sir x, int k, int &as)

{

int i;

ev =1;

for(i=1;i<=k-1;i++)

if((k>=2)&&!(a[x[k]]>a[x[k-1]]))     ev=0;

}

void afis(sir x, int k)

{

int i;

for(i=1;i<=k;i++)

  cout<<a[x[i]]<<" ";  cout<<endl; 

}

int main(void)

{

cout<<"m=";

cin>>m;

for(i=1;i<=m;i++)

  cin>>a[i];

cout<<"p=";

cin>>p;

k=1;

x[k]=0;

while(k>0)

  {

  do

    {

  succ(x,k,as);

  if(as) valid(x,k,ev);

  }

  while(as&&!ev);

  if(as)

  if(k==p) afis(x,k);  else

  {

  k=k+1;

  x[k]=0;

  }

  else k=k-1;

  }

}

Aranjamente

Se dau două mulţimi A={1,2,…,p} şi B={1,2,…,m} se cer toate funcţiile injective definite pe A cu valori în B. O astfel de problemă este una de generare a aranjamentelor de n luate cate p (Anp).

Exemplu: p=2, n=3. Avem (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). De exemplu (2,1) este funcţia f:A→B dată astfel f(1)=2, f(2)=1. Avem relaţiile: =m(m-1)...(m-p+1).

Se citesc m şi p. Să se genereze toate aranjamentele de m luate câte p.

Se observă că dacă se cunoaşte fiecare submulţime de p elemente a mulţimii de m elemente, atunci aranjamentele se pot obţine permutând în toate modurile posibile elementele unei astfel de mulţimi.

O soluţie este de forma: x1,x2,...xp  unde x1,x2,...xpÎB. În plus x1,x2,...xp trebuie să fie distincte. O soluţie are p numere din mulţimea B şi numerele trebuie să fie distincte.

De aici rezultă că algoritmul este acelaşi ca la permutări, diferenţa fiind dată de faptul că soluţia are p numere, nu m ca în cazul permutărilor.

#include<iostream.h>

#include<stdio.h>

typedef int sir[100];

sir x;

int i,k,m,p;

int as,ev;

sir a;

void succ(sir x, int k, int &as)

{

if(x[k]<m)

  {

  as=1;

  x[k]=x[k]+1;

  }

else as=0;

}

void valid(sir x, int k, int &as)

{

int i;

ev =1;

for(i=1;i<=k-1;i++)

  if(x[k]==x[i])    ev=0;

}

void afis(sir x, int k)

{

int i;

for(i=1;i<=k;i++)

  cout<<a[x[i]]<<" ";  cout<<endl; 

}

int main(void)

{

cout<<"m=";

cin>>m;

for(i=1;i<=m;i++)

  cin>>a[i];

cout<<"p=";

cin>>p;

k=1;

x[k]=0;

while(k>0)

  {

  do

    {

  succ(x,k,as);

  if(as) valid(x,k,ev);

  }

  while(as&&!ev);

  if(as)

  if(k==p) afis(x,k);  else

  {

  k=k+1;

  x[k]=0;

  }

  else k=k-1;

  }

} 

Limbajul de programare logic Prolog bazat pe backtracking

Prolog este un limbaj specific inteligenței artificiale ( Prolog - Programming in Logic ) .Originea lui aparține lui Alain Calmaureur de la Universitatea din Marsilia, Franța. Inițial a fost conceput pentru analiza lexicală. Azi in mod curent exista mai multe implementări atât open source cât și proprietare. Printre cele mai bune implementari open source existente azi se numara swi-prolog.

problema rezolvata metoda backtracking

Pe o tabla de sah nXn sunt plasate m piese marcate prin valoarea -1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie (i0,j0) se afla un cal. Sa se determine traseul format din numar minim de pasi pe care calul poate sa manance toate piesele de pe tabla fara a trece de 2 ori prin aceeasi pozitie. Se citesc mai intai n si m, iar apoi m perechi reprezentand coordonatele pieselor. Ultimele se citesc coordonatele calului. Traseul va fi marcat intr-o matrice care se va afisa.

#include<fstream.h>
  fstream f("date.in", ios::in);
  fstream g("date.out",ios::out);

  int a[100][100],n,io,jo,i1,j1,b[100][3],m;
  int min=1000, bsol[100][3], bmat[100][100];
  di[8]={-2,-2,-1,1,2,2,1,-1};
  dj[8]={-1,1,2,2,1,-1,-2,-2};

  int inside(int i,int j)
      { return i>=1 && j>=1 && i<=n && j<=n;
      }
  void citire()
     { f>>n;
       for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
    { f>>a[i][j];
      if(a[i][j]==-1) m++;
    }
  f>>io>>jo;
     }

  void alege(int k)
  {if(k<min)
    { min=k;
      int i,j;
      for(i=0;i<=min;i++){ bsol[i][1]=b[i][1]; bsol[i][2]=b[i][2];
    }
      for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
   bmat[i][j]=a[i][j];
    }
  }

  void afis()
    { for(int i=1;i<=n;i++)
 {  g<<endl;
    for(int j=1;j<=n;j++)
    g<<bmat[i][j]<<" ";
 }
     g<<endl;
     for(i=0;i<=min; i++)
     g<<bsol[i][1]<<","<<bsol[i][2]<<"  ";
     g<<endl;
   }

 void back(int i,int j,int k, int l)
   { if(l==m) alege(k-1);
 else for(int p=0;p<=7;p++)
  {int inou,jnou;
   inou=i+di[p];
   jnou=j+dj[p];
   if(inside(inou,jnou)&& a[inou][jnou]<=0)
       {
         b[k][1]=inou;
         b[k][2]=jnou;
         if(a[inou][jnou]==0){ a[inou][jnou]=k+1;
          back(inou,jnou,k+1,l);
          a[inou][jnou]=0;
        }
         else{ a[inou][jnou]=k+1;
        back(inou,jnou,k+1,l+1);
        a[inou][jnou]=-1;
      }
       }
  }
   }
 void main()
   { citire();
     a[io][jo]=1;
     b[0][1]=io;
     b[0][2]=jo;
     back(io,jo,1,0);
     afis();
   }

Probleme rezolvate

-Probleme rezolvate-
1. Generarea tuturor permutarilor.

#include <iostream>

using namespace std;

int st[50],n,k; // declaratiile pentru ce este necesar la global


void tipar()                 //functie pentru afisarea solutiei
{int i;
  for(i=1;i<=n;i++)          // un for pentru parcurgere
    cout<<st[i]<<' ';        // si afisarea elementului asezat in stiva
    cout<<endl;

}

int valid(int k)            // functie de verificare
{int i;
  for(i=1;i<=k;i++)
      if(st[k]==i)
        return 0;

        else

        return 1;
}

void back(int k)
{int i;
    if(k==n+1)        // daca s-a ajuns la nivelul n+1 apelam functia de tipar si se va afisa solutia gasita
     tipar();
     else
     for(i=1;i<=n;i++)  // daca nu din multimea de alegere se ia elementul
      {st[k]=i;
    if(valid(k))       // si se verifica daca poate poate fii adaugat la solutie
       back(k+1);        //daca se poate adauga se reia functia cu elementul fixat
      }
}

int main()
{cin>>n; //se citeste n-ul

back(1); // si se apeleaza functia back cu 1;



    return 0;
}