Proiect la Informatic Teoria grafurilor n probleme si aplicaii

Conductor tiinific Realizat de ctre Prof. Filonela BlaaAlexandru Andrei Badea

Bucuresti2015

The Trip Manager

Prezentarea Aplicaiei

Organizeaz acum planul tu de cltorii in funcie de nevoile i timpul tu.The Trip Manager v ofer cel mai scurt i economic traseu pe care s l folosii ca s trecei prin toate locurile pe care dorii s le vizitai cu masina personal alaturi de familie,prieteni sau pentru a petrece timp singur.Acest program ia in calcul i drumul spre cas iar traseul este conceput pentru a trece o singur dat prin fiecare locaie. Chiar dac nu avei destui bani sau destul timp The Trip Manager adaptez drumul astfel nct s nu renuntai la excursia dumneavoastr binemeritat. Prezentarea Problemei din Spatele Aplicaiei

Se d un graf orientat cuNvrfuri iMmuchii, fiecare arc avnd asociat un cost. Un ciclu al acestui graf se numete hamiltonian dac conine fiecare nod din graf exact o singur dat. Un graf care conine un astfel de ciclu se numete graf hamiltonian. Costul unui ciclu este egal cu suma arcelor aflate pe ciclu.Sa se determine ciclul Hamiltonian de cost minim i costul parcurgerii ciclului.

Ce Date Trebuie Introduse n Program?

Dup ce ai introdus numrul de persoane,vei introduce suma de bani(n RONI) , numrul de ore,consumul masinii (litru/km) i locaiile.nainte trebuie introduse numrul de locaii i numrul de drumuri.n ceea ce privete locaiile, aplicaia noastra trebuie s tie drumurile dintre aceste locaii.Ceea ce nseamn c vei introduce locaiile ca numere dou cate dou pentru a tii care locaii sunt n legatur.De asemenea va trebui sa menionai, dup fiecare drum pe care l-ai declarat (adic la fiecare dou locaii introduse), lungimea drumului n kilometri.Spre exemplu dac ai introdus 1 2 4 nseamn c exist un drum ntre locaiile 1 i 2 de 4 kilometri.Drumurile vor fi considerate cu sens unic.Deci trebuie s introducei 1 2 4 i apoi 2 1 4 pentru a arta c este un drum cu dublu sens.

Cum Functioneaz The Trip Manager ?

Dupa ce datele de intrare au fost introduse , cu excepia locaiilor utilizatorul va avea de ales dintre o hart deja creat sau s creeze el una.Dupa ce au fost oferite toate locaiile acestea vor fi introduse ntr-o matrice de costuri. Folosind algoritmul parcurgerii n adncime care genereaz toate lanurile din graf; n cazul n care se determin un lan cu N noduri este verificat condiia de nchidere a ciclului (adic dac exist arcul dintre ultimul nod din lan i nodul de start). n caz afirmativ, se verific dac ciclul gsit are un cost mai mic dect soluia curent si retin lanul curent ntr-un vector.Dac utilizatorul nu deine suma de bani sau numrul de ore necesar pentru a trece prin toate nodurile , numrul de noduri ale ciclului va scdea treptat pn cnd utilizatorul i permite.Asfel nct la sfaritul parcurgerii va rmne n vector lanul cel mai bun din punct de vedere al costului monetar si din punct de vedere al timpului.

(n imagine se observ un graf Hamiltonian.Pentru acest graf traseul ar fi0 3 2 4 1 0 cu un cost de 26 ) Parcurgnd acest vector, programul scade din suma de bani i din numrul de ore,afiseaz nodurile prin care trece i ntreab utilizatorul daca exist cheltuieli suplimentare sau timp pierdut la fiecare nod.Se scade din suma de bani folosind preul unui litru de benzin i consumul mainii.Se scade din numarul de ore considernd timpul parcurgerii unui kilometru cu o viteza de 80 km/or.Dac exist cheltuieli suplimentare sau timp pierdut, utilizatorul va introduce valoarea corespunztoare care va fi scazut din suma monetar sau din timpul rmas, continuand parcurgerea vectorului. La sfrit, programul va afia utilizatorului cu ce sum a rmas, numrul de ore rmas, costul total , costul per participant la excursie(dac au existat mai multe persoane) si traseul final(adic vectorul).Cum Functioneaz The Trip Manager ?(ntr-un limbaj mai simplu de neles pentru oricine) Dup ce au fost procurate toate informaiile necesare, programul analizeaz fiecare traseu care include toate locaiile i l alege pe cel mai bun din punct de vedere al costului monetar dar i din punct de vedere al timpului.Daca utilizatorul tot nu i permite cel mai bun drum ales de catre program, acesta va scurta traseul treptat pan cnd utilizatorul i permite.Odat ales traseul , programul l va mai parcurge nca odat pentru a arat utilizatorului cum se modifac suma de bani i timpul i pentru a i arta locaia curent i urmatoare.De asemenea i va oferi alegerea de a introduce cheltuielile suplimentare si timpul pierdut. La sfrsit programul va afia pe ecran resursele rmase, costul total, costul per persoan ,traseul si alte informaii legate de traseu.

Secvene de Cod Semnificative

Cerinte tehniceProcesor: Intel x86, AMD64/x86-64, PowerPC, PowerPC64, SPARC,ARM.Sisteme de operare: Linux, Windows(32 / 64 Bit),Mac OS XMemorie RAM: 256 MB sau mai mult.