Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload




























Metoda Backtracking

Informatica




Metoda Backtracking

Prezentare generala




Se foloseste īn rezolvarea problemelor care īndeplinesc conditiile:

au solutia de forma S=(x1, x2,., xn) cu xi Ai , i=1..n;

A1, A2, ., An 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 x1, x2,., xn ;

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 x1 A1

Se presupun generate x1, x2,., xk apartinānd multimilor A1, A2, ., respectiv Ak. Se alege (daca exista) xk+1, primul element disponibil din Ak+1:

Nu s-a gasit xk+1. Avānd generate elementele x1, x2,., xk-1, se reia cautarea considerānd urmatorul element al multimii Ak, netestat īnca.

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

Daca xk+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 x1, x2,., xk cautāndu-se īn

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

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

generate elementele x1, x2,., xk+1 si se cauta un prim element

xk+2 Ak+2

Daca xk+1 nu īndeplineste conditiile, se reia algoritmul considerānd generate elementele x1, x2,., xk si se cauta un alt element xk+1 printre elementele multimii Ak+1 netestate īnca.

Algoritmul se termina atunci cānd nu mai exista nici un element x1 A1 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. (Apn)

Indicatie

La fel ca problema generarii permutarilor, numai ca solutia este de dimensiune p x1, x2,., xp

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. (Cpn)

Indicatie

La fel ca problema generarii permutarilor, dar

solutia este de dimensiune p x1, x2,., xp

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 An,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 An,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 A1, A2, ., Ak 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 a1, a2, ., an 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();










Document Info


Accesari: 3173
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate




Copyright © Contact (SCRIGROUP Int. 2021 )