in cautarea comorii ~comis voiajor~
DESCRIPTION
In cautarea comorii ~comis voiajor~. Mancu Oana. Vandra Steliana. abcdefghijk6. Mota Alin. Metoda backtracking este folosita de majoritatea programatorilor in cazul in care nu dispun de o metoda mai rapida de rezolvare pentru generarea tuturor solutiilor unei probleme. - PowerPoint PPT PresentationTRANSCRIPT
In cautarea comorii~comis voiajor~
Mancu Oana Vandra Steliana
Mota Alin
Metoda backtracking este folosita de majoritatea programatorilor in cazul in care nu dispun de o metoda mai rapida de rezolvare pentru generarea tuturor solutiilor unei probleme
Incercand sa rezolvam aceasta problema, ne dam seama cum sa aplicam metoda de
backtracking pentru a afla toate posibilitatile si apoi sa o alegem pe cea
mai buna pentru rezolvarea unei probleme
din viata de zi cu zi.
Ajuta-l pe pirat sa gaseasca toate bucatile de harta, care se afla in locuri diferite, pentru a
afla unde este comoara inaintea celorlalti pirati.
La inceput echipajul este odihnit si poate face drumurile lungi si grele. Insa, la sfarsit, el
oboseste si prefera sa parcurga drumurile mai
usoare.
In concluzie solutia gasita trebuie sa fie cea mai
convenabila pentru echipaj
In exemplul urmator vom lua 5 insule intre care exista 8 legaturi:
E(5)
A(1)
B(2)C(3)
D(4)
1(A)-2(B)
1(A)-3(C)
1(A)-4(D)
1(A)-5(E)
2(B)-3(C)
3(C)-4(D)
3(C)-5(E)
4(D)-5(E)
Cum rezolvam problema?
Mai intai generam toate variantele posibile folosind programul:
void init(int k){st[k]=0;
}int succesor(int k)
{if (st[k]<n) {st[k]++;
return 1; } else return 0;}int valid(int k)
{int i;for(i=1;i<=k-1;i++)
if(st[k]==st[i])return 0;if(k>1)if(a[st[k]][st[k-1]]==0)return 0;if(k==n && a[st[k]][st[1]]==0)return
0; return 1;}
int solutie(int k){return k==n+1;
}}
int solutie(int k){return k==n+1;}
void tipar(){int i;
for(i=1;i<=n;i++) cout<<st[i];
cout<<endl; }void back(int k)
{if (solutie(k))tipar(); else{init(k);
while(succesor(k)) if (valid(k)) back(k+1); }}
main(){int m,x,y,i;
clrscr();cout<<"nr orase";cin>>n;cout<<"legaturi";cin>>m;
for(i=1;i<=m;i++){cin>>x>>y; a[x][y]=1;
a[y][x]=1; }back(1);getch();Apasa pe timona
In urma inserarii datelor vom obtine urmatorul tabel sub forma de matrice, unde avem reprezentata cu 1 existenta
legaturilor dintre insulele de pe orizontala si cele de pe verticala
A B C D E
A
B
C
D
E
X1 X2 X3 X4 X5
0 1 1 1
0
0
1
1
0
1
1
1
1
11
1
1
0
0
0
0
0
0
1
0
Y1
Y2
Y3
Y4
Y5
Legaturile erau:
A-B, A-C, A-D, A-E, B-C, C-D, D-E
St[k]K
1
2
3
4
5
succesor
solutie
valid
Solutii
0
1
1
1
0
01
0
2
0123
01 342
0 1 32 45
1
12345 (ABCDE)
Pt aceasta solutie piratul va face
urmatorul drum:
BB
AA
EE
DD
CC
Dupa ce am generat toate Dupa ce am generat toate
drumurile cautam cea mai drumurile cautam cea mai buna solutie si o afisam, buna solutie si o afisam, sa vedem daca gasim sa vedem daca gasim
comoaracomoara
Apasa aici
Ce am invatat:
Prin lucrul in echipa, putem aprofunda informatica,intr-un mod placut.
Bibliografie
•Manual informatica
•http://garaj.xhost.ro
•http://worldit.info