Călător prin Europa

Echipa Visătoare: Maria şi Lidia

Vacanţa de vară era foarte aproape şi împreuna cu Lidia, buna mea prietenă, am hotărât să vizităm Europa, mai exact câteva oraşe pe care le consideram … interesante, deoarece le văzusem doar în poze prietenilor sau la televizor Am stabilit împreună cu Lidia oraşele pe care dorim să le vizităm : Viena, Roma, Venetia, urmând să stabilim şi harta traseul în funcţie de timp şi buget. Am luat o hartă a Europei şi am început să încercuim oraşele pe care dorim să le vizităm şi prin care vom trece: Haţeg, Deva, Arad, Nădlac, Szeged, Budapest, Viena, Firenze, Roma, Bologna, Venezia, Ljubljana, Zagreb, Novi Sad, Jimbolia, Timişoara, Lugoj şi din nou în Haţeg.

Ne-am dat seama de câteva lucruri: - harta era prea mare şi era destul de greu să te uiţi pe ea. - pentru a ajunge de la un oraş la altul existau mai multe drumuri şi nu ştiam pe care să-l alegem. - între oraşele alese de noi nu exista drum direct şi trebuia să alegem acele oraşe de legătură, astfel încât drumul să fie cel mai scurt.

Împreună cu Lidia am decis să desenăm pe o foaie harta traseului. Pentru a economisi timp şi bani am hotărât să trecem o singură dată prin fiecare oraş. Acum aveam harta desenată şi trebuie să găsim o soluție de parcurgere a ei, astfel încât să putem vizita toate oraşele, fiecare oraş o singură dată, traseul să fie parcurs cu cost minim, iar după ultimul oraş vizitat să ne întoarcem în oraşul de plecare (Haţeg)?

Maria: Harta pe care am desenat-o seamănă cu un graf, am învăţat la şcoală în semestrului al-II-lea. Putem identifica oraşele ca fiind vârfurile unui graf, iar drumurile dintre oraşe arcele grafului.

Lidia: Trebuie să găsim o modalitate de vizitare a oraşelor, astfel încât să rezolvăm ceea ce ne-am propus. Avem nevoie de o modalitate de reprezentare a grafurilor astfel încât să asociem fiecărei muchii un număr real care să corespundă distanţei dintre două vârfuri (oraşe).

Maria: Dacă alegem ca reprezentare matricea de adiacenţă, dar în loc să o completăm cu 1 în cazul în care există arc (legătură) şi 0 în caz contrar, facem următoarea modificare: a[i][j]=distanţa dintre oraşele i şi j

Lidia: Ar fi o soluţie şi ne putem alege mai uşor drumul cel mai scurt.

Maria: M-am uitat pe hartă şi cred că ar trebui să scoatem din calcul vama Turnu. Am auzit că este foarte aglomerată în această perioadă, fiind o vamă mică, iar cozile se întind pe câţiva km.

Lidia: Dacă scoatem din calcul această vamă ar fi bine să ştergem şi drumul de acces de la Arad spre Turnu, ca să nu ne încurce mai departe.

Maria: Desenez din nou mini-harta noastă.Pentru parcurgerea traseului, mai bine zis a circuitului, avem nevoie pe lângă noţiunile cunoscute de la grafuri şi de cunoaşterea tehnicii Backtracking care permite generarea tuturor drumurilor posibile, urmând ca din acestea să fie selectat cel mai scurt.

Lidia: Am învăţat la şcoală că putem reprezenta un graf şi prin matricea costurilor, pentru a determina drumul cu costul cel mai mic.

Maria: Haide să-ţi arăt cum este această matrice în cazul nostru.

Lidia: Până tu ai lucrat la marticea costurilor, eu am scris un program de determinare a drumului minim dintre 2 noduri X şi Y. Uite rezultatul…

#include<stdio.h>#include<conio.h>#define pinf 10000 //pentru plus infinit, o

valoare mare care nu existaint a[20][20],n,m;void citire_cost(){ FILE *f;int i,j,x,y,c;f= fopen("roy_in.txt","rt");if(f)printf("deschiderea a reusit");elseprintf("eroare la deschidere!");printf("\n");fscanf(f,"%d",&n);fscanf(f,"%d\n",&m);//initializare matricefor(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)a[i][j]=0;else

a[i][j]=pinf;for(i=1;i<=m;i++){fscanf(f,"%d %d %d\n",&x,&y,&c);a[x][y]=a[y][x]=c;}fclose(f);}void afisare_mat(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(a[i][j]==pinf)printf(" - ");elseprintf("%4d ",a[i][j]);printf("\n"); }}void RoyFloyd() // roy floyd{for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]>a[i][k]+a[k][j]){ a[i][j]=a[i][k]+a[k][j];}}

void descompun_drum(int i,int j)//realizeaza descompunerea portiunii de la

i la j prin k{int ok=0,k=1;while(k<=n&&!ok){if(i!=k&&j!=k)if(a[i][j]==a[i][k]+a[k][j]){descompun_drum(i,k);descompun_drum(k,j);ok=1;} //g marcheaza daca se poate

realiza descompunereak++;}if(!ok){printf(" %d ",j); }//cand "drumul" nu mai poate fi descompus

afisez extremitatea finala}

void scriu_drum(int nod_initial,int nod_final)

// functia primeste ca parametri cele doua noduri pt care se determina optimul

{if(a[nod_initial][nod_final]<pinf){printf("lantul de la %d la %d are lungimea

%d",nod_initial,nod_final,a[nod_initial][nod_final]);

printf("\n un drum optim este: %d ",nod_initial);

descompun_drum(nod_initial,nod_final);// apeleaza functia care afiseaza efectiv

lantul}elseprintf("nu exista lant de la %d la %d

",nod_initial,nod_final);}void main(){int x,y;citire_cost();

printf("\nmatricea ponderilor \n");afisare_mat();RoyFloyd();printf("\n matricea drumurilor optime \

n");afisare_mat();printf("\n Se determina drumul minim

intre varfurile x si y \n");printf("x=");scanf("%d",&x);printf("y=");scanf("%d",&y);scriu_drum(x,y);getch();}

Obs. Fisierul Roy_in.txt este de forma5 5 // numarul de noduri si numarul de muchi

1 2 2 // intre nodul 1 si 2 exista muchia de cost 2

2 3 3 // intre nodul 2 si 3 exista muchia de cost 3

3 4 13 5 84 1 10

Concluzii

Folosind corect noţiunile învăţate la grafuri şi combinate cu o metodă eficientă (de exemplu Backtracking) poţi să alegi drumul cel mai scurt dintre două puncte X şi Y, cu costul cel mai mic, fără a trece de 2 ori printr-un punct.

Grafurile rezolvă nu numai planificarea unei excursii, ci aproape orice problemă din viaţa reală.

Pe baza a ceea ce am învăţat la şcoală, am putut stabili traseul şi porni la drum … călător prin Europa …