Metoda Backtracking

Metoda Backtracking

Prezentare generala

Se foloseste īn rezolvarea problemelor care īndeplinesc conditiile:

au solutia de forma S=(x₁, x₂,., x_n) cu x_i A_i , i=1..n;

A₁, A₂, ., A_n sunt multimi finite, iar elementele lor se afla īntr-o relatie de ordine bine stabilita;

nu se dispune de alta metoda de rezolvare mai rapida;

Principiul care sta la baza acestei metode este simplu:

se construieste solutia pasa cu pas x₁, x₂,., x_n ;

daca se constata ca pentru o valoare aleasa nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul īn care am ramas.

Metoda Backtracking genereaza toate solutiile problemei.

Algoritmul Backtracking

Se alege cu x₁ A₁

Se presupun generate x₁, x₂,., x_k apartinānd multimilor A₁, A₂, ., respectiv A_k. Se alege (daca exista) x_k+1, primul element disponibil din A_k+1:

Nu s-a gasit x_k+1. Avānd generate elementele x₁, x₂,., x_k-1, se reia cautarea considerānd urmatorul element al multimii A_k, netestat īnca.

S-a gasit x_k+1. Se testeaza daca acesta īndeplineste conditiile

Daca x_k+1 īndeplineste conditiile, se testeaza daca s-a ajuns la solutie.

2.2.1.1. daca s-a ajuns la solutie, se tipareste solutia si se reia algoritmul

considerānd generate elementele x₁, x₂,., x_k cautāndu-se īn

continuare un alt element al multimii A_k+1 ramas netestat.

2.2.1.2. daca nu s-a ajuns la solutie, se reia algoritmul considerānd

generate elementele x₁, x₂,., x_k+1 si se cauta un prim element

x_k+2 A_k+2

Daca x_k+1 nu īndeplineste conditiile, se reia algoritmul considerānd generate elementele x₁, x₂,., x_k si se cauta un alt element x_k+1 printre elementele multimii A_k+1 netestate īnca.

Algoritmul se termina atunci cānd nu mai exista nici un element x₁ A₁ netestat.

Probleme propuse

Sa se genereze toate permutarile de ordinul n.

Se da o tabla de sah de dimensiune n x n . Se cer toate solutiile de aranjare a n dame astfel īncāt sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala.

Sa citesc n si p numere naturale. Sa se genereze toate submultimile multimii  de p elemente. Doua submultimi care au aceleasi elemente dar īn ordine diferita, sunt considerate distincte. (A^p_n)

Indicatie

La fel ca problema generarii permutarilor, numai ca solutia este de dimensiune p x₁, x₂,., x_p

Sa citesc n si p numere naturale. Sa se genereze toate submultimile multimii de p elemente. Doua submultimi care au aceleasi elemente dar īn ordine diferita, sunt considerate egale. (C^p_n)

Indicatie

La fel ca problema generarii permutarilor, dar

solutia este de dimensiune p x₁, x₂,., x_p

nivelul k al stivei ia valori īntre 1 si n-p+k

pe nivelul k trebuie sa fie o valoare mai mare decāt pe nivelul k-1 al stivei.

Se citesc n litere mici distincte. Sa se genereze toate cuvintele care

contin exact m litere din cele n citite

literele din care sunt formate apar īn ordine lexicografica crescatoare

Se da o harta cu n tari. Se cer toate solutiile de colorare a hartii utilizānd cel mult 4 culori, astfel īncāt doua tari cu frontiera comuna sa fie colorate diferit.

Indicatie

Harta este furnizata de o matrice A_n,n.

A(i,j)=1, daca tara i se īnvecineaza cu tara j

0, īn caz contrar

Un comis-voiajor trebuie sa viziteze un numar de n orase. Initial, acesta se afla īntr-unul din ele, notat cu 1. Comis-voiajorul doreste sa nu treaca de 2 ori prin acelasi oras, iar la īntoarcere sa revina īn orasul 1. Cunoscānd legaturile existente īntre orase, sa se afle toate drumurile posibile pe care le poate efectua comis-voiajorul.

Indicatie

Legaturile existente īntre orase sunt date de o matrice A_n,n.

A(i,j)=1, daca exista drum īntre orasul i si orasul j

0, īn caz contrar

Se considera multimea A . Se cer toate partitiile acestei multimi.

(submultimile A₁, A₂, ., A_k formeaza o partitie a multimii A daca sunt disjuncte doua cāte doua si reuniunea lor este A).

Indicatie

o partitie a multimii A se poate reprezenta sub forma unui vector stiva cu n componente. stiva[i]=k - elementul i al multimii A apartine submultimii k a partitiei.

pentru a se evita repetitia partitiilor se face conventia stiva[k] ia valori cuprinse ntre 1 si k; unde k =1..n

oricare i sa existe j astfe īncāt |stiva[i]-stiva[j]|<=1

Se dau suma s si n tipuri de monede avānd valori de a₁, a₂, ., a_n lei. Se cer toate modalitatile de plata a sumei s utilizānd cele n tipuri de monede.

Se da un numar natural par n. Sa se determine toate sirurile de n paranteze care se īnchid corect.

Solutii

#include <stdio.h>

#include <conio.h>

int st

int n,as,ev;

void succesor(int k)

else as=0;

void valid(int k)

void tipar(void)

void main(void)

do

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

else

}

else k--;

}

printf("\n Gata!");

getche();

#include <stdio.h>

#include <conio.h>

#include <math.h>

int st[100];

int n,as,ev;

void succesor(int k)

else as=0;

void valid(int k)

void tipar(void)

void main(void)

do

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

else

}

else k--;

}

printf("\n Gata!");

getche();

#include <stdio.h>

#include <conio.h>

int st[100];

int n,as,ev,m;

void succesor(int k)

else as=0;

void valid(int k)

void tipar(void)

void main(void)

do

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

else

}

else k--;

}

printf("\n Gata!");

getche();

#include <stdio.h>

#include <conio.h>

int stiva[100];

int n,as,ev,p;

void main(void)

else as=0;

}

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

\t");getch();

}

else

}

else k--;

}

printf("\n Gata!");

getche();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int m,n;

int stiva[100];

char litere[100];

int as,ev;

void succesor(int k)

else as=0;

void valid(int k)

void main ()

printf("\n Solutiile sunt: \n");

k=1;stiva[k]=0;

while (k>0)

while (! ((as==0) || (as>0 && ev>0)) );

if (as>0)

else

}

else k--;

getch();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int n;

int stiva[100],a[100][100];

int as,ev;

void succesor(int k)

else as=0;

void valid(int k)

void main ()

k=1;stiva[k]=0;

while (k>0)

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

else

}

else k--;

printf("\n Gata!");

getch();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int n;

int stiva[100],a[100][100];

int as,ev;

void succesor(int k)

else as=0;

void valid(int k)

void main ()

stiva[1]=1;

k=2;stiva[k]=0;

while (k>1)

while (!((as==0) || (as>0 && ev>0)));

if (as>0)

else

}

else k--;

printf("\n Gata!");

getch();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int n;

int stiva[100];

int as,ev;

void succesor(int k)

if ( stiva[k]<max+1 && stiva[k]<k)

else as=0;

void tipar(void)

");

}

void main ()

else

}

else k--;

getch();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int n,suma,as,ev;

int stiva[100],a[100],m[100];

void succesor(int k)

else as=0;

}

else as=0;

}

int solutie(int k)

return 0;

void main ()

k=1;stiva[k]=-1;

while (k>0)

else

}

else k--;

printf("Gata!");

getch();

#include <stdio.h>

#include <dos.h>

#include <conio.h>

int n,as,ev;

int stiva[100];

char simbol[3];

void succesor(int k)

else as=0;

void valid(int k)

if (nr2>nr1) ev=0;

if (nr1>(n/2) || nr2>n/2) ev=0;

if (stiva[1]==2) ev=0;

if (stiva[n]==1) ev=0;

}

void main (){

int k,i;

clrscr();

printf("dati n par:"); scanf("%d",&n);

simbol[1]='('; simbol[2]=')';

k=1;stiva[k]=0;

while (k>0)

while (!( (as==0) || (as>0 && ev>0) ));

if (as>0)

else

}

else k--;

getch();