in cautarea comorii ~comis voiajor~

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