Ce Ce

stim stim

despredespre

aceasta aceasta

metoda??metoda??

Deseori în practică trebuie să rezolvăm probleme care Deseori în practică trebuie să rezolvăm probleme care au un număr foarte mare de soluţii posibile. De cele mai au un număr foarte mare de soluţii posibile. De cele mai multe ori însă, nu ne interesează toate soluţiile, ci numai o multe ori însă, nu ne interesează toate soluţiile, ci numai o parte dintre ele, care îndeplinesc anumite condiţii specifice parte dintre ele, care îndeplinesc anumite condiţii specifice problemei. Pentru astfel de probleme este indicată folosirea problemei. Pentru astfel de probleme este indicată folosirea metodei backtrackingmetodei backtracking care evită generarea soluţilor inutile. care evită generarea soluţilor inutile.

DesigurDesigur,, o persoană cu o gândire simplistă ar putea o persoană cu o gândire simplistă ar putea spune: „generăm toate soluţiile, apoi le alegem pe cele care spune: „generăm toate soluţiile, apoi le alegem pe cele care îndeplinesc condiţiile cerute”. Foarte simplu, dar... oare şi îndeplinesc condiţiile cerute”. Foarte simplu, dar... oare şi eficient? Ce rost ar avea să se genereze nişte soluţii care eficient? Ce rost ar avea să se genereze nişte soluţii care oricum nu convin? Din punctul de vedere al timpului necesar oricum nu convin? Din punctul de vedere al timpului necesar calculatorului pentru a obţine toate soluţiile, cât de realistă calculatorului pentru a obţine toate soluţiile, cât de realistă este o astfel de abordare? este o astfel de abordare?

Prima ideePrima idee,, pe care trebuie să o reţinem ar pe care trebuie să o reţinem ar fi: nu se generează toate soluţiile posibile, ci fi: nu se generează toate soluţiile posibile, ci numai acelea care îndeplinesc anumite condiţii numai acelea care îndeplinesc anumite condiţii specifice problemei, numite specifice problemei, numite condiţii de validarecondiţii de validare . .

Soluţiile problemei vor fi generate succesiv Soluţiile problemei vor fi generate succesiv într-o stivă implementată sub forma unui vector într-o stivă implementată sub forma unui vector pe care îl vom nota pe care îl vom nota stst..

De De cece

ne-am ne-am propuspropus sa sa

rezolvam rezolvam aceastaaceasta problema??problema??

Deci, (n-ar trebui sa incepem cu deci) dar…ce ni s-a Deci, (n-ar trebui sa incepem cu deci) dar…ce ni s-a parut interesant a fost cat de simplu ti se poate arata in parut interesant a fost cat de simplu ti se poate arata in cateva secunde un lucru ce manual ar fi durat cateva ore cateva secunde un lucru ce manual ar fi durat cateva ore cel putin, adica: jocul de sah este unul de strategie, ce cel putin, adica: jocul de sah este unul de strategie, ce implica rabdare si concentrare maxima. Scopul este acela implica rabdare si concentrare maxima. Scopul este acela de a-ti detrona adversarul prin sah mat( ii ciordesti de a-ti detrona adversarul prin sah mat( ii ciordesti regeleregele). Calul, care, in cazul nostru, cam sare, este o ). Calul, care, in cazul nostru, cam sare, este o piesa foarte importanta. Nu stiu exact de ce, dar vrea sa se piesa foarte importanta. Nu stiu exact de ce, dar vrea sa se mute doar in L. Sincer, n-am stiut niciodata cate posibilitati mute doar in L. Sincer, n-am stiut niciodata cate posibilitati de mutare exista. Ce-i drept, nici nu ne-a preocupat. Cand de mutare exista. Ce-i drept, nici nu ne-a preocupat. Cand am auzit prima data de aceasta problema, am evitat-o, am auzit prima data de aceasta problema, am evitat-o, alegand colorarea hartii. Soarta a decis pentru noi si uite alegand colorarea hartii. Soarta a decis pentru noi si uite cum am ajuns sa explicam de ce calul sare si de cate ori. cum am ajuns sa explicam de ce calul sare si de cate ori.

Ce vrem

sa stim??

Nu stim exact cum sa raspundem la aceasta intrebare. Ce cred ca am vrut sa stim este, din curiozitate, cam cate solutii ar fi. Cand am vazut, de fapt, cate mutari include o solutie, in care tabla de sah are 5 linii si 5 coloane, am incercat si pentru n=6 si asa mai departe.

Am crezut ca ne-am terminat treaba, dar nu. Am inteles apoi ca prima solutie nu este, nicidecum,ultima. Fiecare solutie are schema ei. Daca o modifici, se modifica si coordonatele fiecarei mutari si, uite asa, ai cu totul alte mutari si,evident, alta solutie. Ni s-a parut amuzant

Fiind dată o tablă de şah de dimensiunea n x n şi un cal în colţul stânga

sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a acestei

piese de şah astfel încât să treacă o singură dată prin fiecare pătrat altablei. O soluţie va fi afişată ca o matrice n x n în care sunt

numerotatesăriturile calului.

Exemplu, pentru n=5, o soluţie este

1 14  9 20 2310 19 22 15  8 5  2 13 24 2118 11   4  7 16 3  6 17 12 25

Pentru rezolvarea acestei probleme vom codifica direcţiile de deplasare

pentru că ar fi ineficient să scriem două cicluri for de la 2 la 2 cu cele 25 de

variante de deplasare din care valide sunt doar opt. De asemenea aici spre

deosebire de celelalte probleme tratate la aplicarea metodei backtracking în

plan nu vom folosi un vector soluţie, ci vom scrie săriturile  în tablouurmărind ca la revenire să refacem poziţiile ocupate pentru a nu se luablocaje.

Sursaexecutabil

#include<iostream.h>#include<stdlib.h>#include<iomanip.h>#include<conio.h>

const int x[8]={-1,1,2,2,1,-1,-2,-2};const int y[8]={ 2,2,1,-1,-2,-2,-1,1};int n, sol[1000][2],t[25][25],c, tabla[10][10];;Void back( int k,int lin,int col){ int linie,coloana,i,j;

if(k==n*n) { sol[k][0]=lin; sol[k][1]=col; for(i=1;i<=k;i++) { cout<<"mutarea nr."<<i<<" este la coordonatele"<<"("<<sol[i][0]<<","<<sol[i][1]<<")"<<endl; tabla[sol[i][0]][sol[i][1]]=i; }

c++; //numara solutiile

cout<<endl<<"varianta "<<c<<" este"<<endl<<endl;

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

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

cout<<setw(4)<<tabla[i][j];

cout<<endl;

}

cout<<endl;

getch();

if(c==3)

exit(EXIT_SUCCESS);

}

else sol[k][0]=lin; sol[k][1]=col; for(i=0;i<=7;i++) { linie=lin+x[i];

coloana=col+y[i]; if(linie<=n &&

linie>=1 && coloana<=n && coloana>=1 && t[linie][coloana]==0)

{ t[linie]

[coloana]=1;

back(k+1,linie,coloana); t[linie]

[coloana]=0; } } }}

void main(){ clrscr(); cout<<"n="; cin>>n; t[1][1]=1; //ocup prima pozitie back(1,1,1);

}

Ce am invatat??

Sa vedem…in primul rand…cum sa lucram in echipa, desi, la inceput am lucrat pe cont propriu, apoi cate doua, si, in final, toate. Amuzant, nu? A fost greu sa ne impartim sarcinile,mai ales ca Simonei nu ii functiona Power Point-ul si lui Armine C++, Ioanei ii functionau amandoua, dar nu aveam cum sa mergem la ea, asa ca a fost cam complicat. Pana la urma,ne-am decis. Simona cu Armine au cautat pozele si s-au chinuit cu executabilul ala, iar Ioana s-a ocupat cu artificiile din Power Point si de animatii. De text, in schimb, ne-am ocupat toate trei. Am invatat mai multe despre metoda backtracking, evident, si am inteles cum sare calul pe 2 picioruse. A fost greu, dar, ne amagim singure ca am dus la capat misiunea

Cu

ce

ramanem??

Sincer, putem spune ca ne-am imbunatatit cunostintile in domeniul Power Point-ului si, cat de cat, in cel al C++. Totodata, ne-am bucurat de orele frumoase petrecute impreuna, lucru care nu s-a mai intamplat de cand am terminat filmul, cunoscut deja de majoritatea colegilor .

In concluzie, proiectele la info, pentru noi acesta fiind al doilea, leaga prietenii !!!

Referate.educativ.ro/referatat-Metoda-Backtracking.html,

Manualul si cam atat