Choose your screen resolution: Auto adjust 800x600 1024x768


Aplicarea teoriei grafurilor pentru a gasi cai optime pentru problema de transport
Scris de mihaiela lazar   
Duminică, 08 Februarie 2015 19:33

APLICAREA TEORIEI GRAFURILOR PENTRU A GĂSI DRUMURI/CĂI OPTIME PENTRU PROBLEMA DE TRANSPORT

 

Prof. Diana Bărbat

C.N.I. “Gr. Moisil” Brașov

 

            Articolul a apărut în Intenational Journal of Current Engineering and Technology în 10 august în 2013 şi a fost scris de Rame Likaj, Ahmet Shala and Mirlind Bruqi, profesori de la Facultatea de Inginerie Mecanică a Universităţii din Prishtina, Prishtina, Kosovo.

Obiectiv general

-         modelarea numeroaselor situaţii din viaţă cotidiană cu ajutorul teoriei grafurilor.

Obiectiv specific

-          căutarea celui mai scurt drum între două puncte dintr-un graf  în vederea proiectării unei soluţii pentru o problemă practică: determinarea unui arbore parţial de cost minim utilizând algoritmul lui Kruskal și căutarea celui mai scurt drum între două puncte utilizând algoritmul lui Dijkstra.

Pentru atingerea obiectivului specific a fost elaborat un model de rețea de problemă a transportului care este analizată în detaliu pentru a minimiza costurile de transport.

Lucrarea este structurată în următoarele părţi:

1.       Introducere în teoria grafurilor

2.       Determinarea arborelui parţial de cost minim utilizând algoritmul lui Kruskal

3.       Drumul de cost minim

4.       Algoritmul lui Dijkstra

5.       Drumul minim dintre 2 puncte

6.       Concluzii

Metode de cercetare folosite: analiza grafică, analiza calitativă.

Vezi figuri - grafuri

            Algoritmul lui Dijkstra este capitolul în care aflăm utilizarea algoritmului şi modalitatea de a  determina un drum de cost minim de la un nod de start la fiecare din celelalte vârfuri ale grafului. Algoritmul este explicat pas cu pas pe un graf ponderat. La momentul iniţial singurul vârf pentru care drumul de cost minim este cunoscut este vârful iniţial. S-au utilizat următoarele structuri:

-         o mulţime care va reţine vârfurile pentru care drumul de cost minim este deja calculat;

-         un vector a cărui dimensiune este dată de numărul de noduri din graf şi care memorează costul drumului  de cost minim de la nosul de start la un nod oarecare, drum care trece doar prin vârfuri din mulşimea vărfurilor selectate;

-         un vector care reţine pentru fiecare vârf din graf vârful care îl precedă pe drumul de cost minim.

În Drumul minim dintre 2 puncte este reconstituit drumul între cele două puncte.

Concluzii

Algoritmul Dijkstra va găsi calea cea mai scurtă dintre două noduri.

Algoritmul lui Kruskal va determina un arbore parţial de cost minim conectând toate nodurile. Practic, Dijkastra va găsi o conexiune între cele două noduri, în timp ce Kruskal va găsi o conexiune între numărul de noduri. Rezultatele obţinute din exemplele prezentate arată că algoritmul lui Dijkstra este un mijloc eficient pentru a găsi calea cu costuri minime de la nodul A la nodul B. De asemenea, aceleaşi rezultate sunt obţinute şi în arborele parţial de cost minim folosind algoritmul Kruskal, dar în acest caz procedura este mult mai simplă cu un arbore de cost minim pentru a ajunge de la punctul B la punctul A cu cel mai mic cost total.

Autorii au calculat costul celui mai dezavantajos drum, ajungând la concluzia că, în această situaţie, ar fi cu 63% mai scump faţă de primul traseu.

 

Concluzii personale

Ipoteza cercetării de la care au plecat autorii a fost fundamentată iniţial pe aspectele teoretice ale grafurilor, şi s-a finalizat, prin cercetarea lor, cu proiectarea grafurilor în vederea modelării unei situaţii reale. Perspectiva analizării grafurilor a fost realizată prin două metode de lucru, ambele metode fiind mijloace eficiente de determinare a drumului minim şi a costului drumului minim.

 

Bibliografie

Likaj, R. (2009), The problem of transport in designing the production systems, pages 175-180, MITIP, Bergamo, Italy.

Likaj, R. (2010), Sensitivity analysis in designing the production systems and economic interpretation, MOTSTP, International Scientific Conference Management of Technology, Zagreb Croatia.

Chamero, Juan. (2006), Dijkstra’s Algorithm As a Dynamic Programming strategy, www.intag.org

Rutter, Sh., (2009), Dijkstra Algorithm final project EDUC 528 from http://shawnrutter.com/pdf/Dijkstra_Algo.pdf

Lee, D.C. (2006), Proof of a modified Dijkstra's algorithm for computing shortest bundle delay in networks with deterministically time-varying links, pages 734 – 736, Communications Letters, IEEE

Wen-Chih Chang, Yan-Da Chiu, Mao-Fan Li, (2008), Learning Kruskal's Algorithm, Prim's Algorithm and Dijkstra's Algorithm by Board Game, Pages 275 – 284, Springer-Verlag Berlin, Heidelberg

 

Adaugă comentariu


Codul de securitate
Actualizează

Revista cu ISSN

Colaborarea scoala familie cheia spre su…

COLABORAREA ŞCOALĂ-FAMILIE - CHEIA SPRE SUCCES Prof. înv. primar: Tica Ionela Georgiana Scoala Gimnaziala ”Iosif Catrinescu” Rezumat: Părinţii trebuie să cunoască, să devină conştienţi de influenţa pe care o exercită...

Read more

Repere in socializarea elevilor cu ADHD …

REPERE ÎN SOCIALIZAREA ELEVILOR CU ADHD INCLUŞI ÎN ÎNVĂŢĂMÂNTUL SPECIAL                                                                                                                                     Mureşan-Chira Gabriel          Prof. Educator CRDEII, Cluj-Napoca   Aria curriculară, terapie educaţională complexă şi integrată, completează programul centrat pe predare-învăţare-evaluare, desfăşurat de...

Read more

Dualismul poetic Grigore Alexandrescu

DUALISMUL POETIC. GRIGORE ALEXANDRESCU   Prof. Becheru Ramona Florentina Grup Şcolar Ferdinand I Rm.Vâlcea     Grigore Alexandrescu a creat în două registre estetice, aparent distincte, exprimând contradicţiile conştiinţei sale, ireductibile, interogative, greu de conciliat. Acest...

Read more

Raport incheiat in urma inspectiei temat…

ANEXA Nr. 6   la regulament   INSPECTORATUL SCOLAR AL JUDETULUI ................./INSPECTORATUL SCOLAR AL MUNICIPIULUI BUCURESTI Nr. de inregistrare: ............................................   RAPORT INCHEIAT IN URMA INSPECTIEI TEMATICE   - model -   Unitatea de invatamant/institutia...

Read more

Comunicarea didactica si manageriala in …

Comunicarea didactica si manageriala in scoala Studiu de caz

COMUNICAREA DIDACTICĂ ŞI MANAGERIALĂ ÎN ŞCOALĂ. STUDIU DE CAZ ÎN UNITATEA ŞCOLARĂ ALEXANDRU MACEDONSKI, MELINEŞTI, DOLJ       Prof. Drd. Miron Costina Violeta Absolventă a Masteratului Management Educaţional Preuniversitar Facultatea de Ştiinţe ale Educaţiei, Universitatea...

Read more

DESPRE SARBATOAREA MUZICII

DESPRE SÃRBÃTOAREA MUZICII   Profesor Maria Dinu C.N.E. “Gh.Chitu”, Craiova     Începând din anul 1982, în Franta, a fost organizatã, în prima zi a verii, 21 iunie, Sãrbãtoarea Muzicii. Astãzi, Sãrbãtoarea Muzicii este prezentã...

Read more

Horoscop 2013 cariera si bani

Horoscop 2013 cariera si bani

Horoscop 2013 - cariera si bani   Afla acum ce iti prezic astrele in ceea ce priveste cariera si banii pentru 2013 in functie de semnul tau zodiacal: Horoscop cariera si bani...

Read more

Relatia de independenta dintre educatia …

RELAŢIA DE INDEPENDENŢĂ DINTRE EDUCAŢIA FIZICĂ ŞI CELELALTE LATURI ALE EDUCAŢIEI   Prof. Antonie Iustin-Marius Școala Gimnazială „Mihail Sadoveanu” Bacău   Rezumat: O societate sănătoasă nu se poate construi fără a înţelege rolul educaţiei fizice în...

Read more