Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim

Proiect
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 84 în total
Cuvinte : 15490
Mărime: 1.76MB (arhivat)
Cost: 11 puncte
Profesor îndrumător / Prezentat Profesorului: Laura Ciupala, Eleonor Ciurea
UNIVERSITATEA „TRANSILVANIA” BRAŞOV FACULTATEA DE MATEMATICĂ-INFORMATICĂ MASTERAT: ALGORITMI ŞI PRODUSE SOFTWARE

Cuprins

Cuvânt înainte

Capitolul I – Noțiuni introductive 7

1.1. Vocabularul de bază în teoria grafurilor 7

1.2. Clase de grafuri 10

1.3. Structuri de date utilizate în reprezentarea grafurilor 12

Capitolul II – Parcurgeri de grafuri 17

2.1. Parcurgerea generică a grafurilor 17

2.2. Parcurgerea BF a grafurilor 18

2.3. Parcurgerea DF a grafurilor 21

Capitolul III – Distanțe și drumuri minime. 26

3.1. Principalele probleme de drum minim 26

3.2. Ecuațiile lui Bellman 27

3.3. Algoritmi pentru distanțe și drumuri minime. Algoritmul Dijkstra 28

Capitolul IV – Fluxuri de cost minim 32

4.1. Noțiuni introductive 32

4.2. Ipoteze asupra problemei fluxului de cost minim 32

4.3. Condiții de optimalitate 35

4.3.1. Condițiile de optimalitate cu circuite de cost negativ 35

4.3.2. Condițiile de optimalitate cu costuri reduse 35

4.3.3. Condițiile de optimalitate cu ecarturi complementare 37

4.4. Dualitatea pentru fluxul de cost minim 38

4.5. Legătura dintre fluxurile de cost minim și potențialele optime 41

4.6. Algoritmi pseudopolinomiali 42

4.6.1. Algoritmul Klein de eliminare a circuitelor de cost negativ 42

4.6.2. Algoritmul Busaker –Gowen al drumurilor minime succesive 45

4.6.3. Algoritmul primal – dual Ford-Fulkerson 49

4.6.4. Algoritmul nonconform Minty-Fulkerson 54

4.7. Aplicații 58

Capitolul V – Implementarea algoritmilor 60

5.1. Algoritmul Busaker –Gowen al drumurilor minime succesive 60

5.1.1. BGDS.java 60

5.1.2. Fișierul de intrare 65

5.1.3. Rezultatul execuției BGDS.java 65

5.2. Algoritmul primal – dual Ford-Fulkerson 67

5.2.1. PDFF.java 67

5.2.2. Fișierul de intrare 75

5.2.2. Rezultatul execuției PDFF.java 76

Bibliografie 79

Extras din document

“Diferența dintre școală și viață?

În școală, înveți o lecție, apoi dai un test.

În viață, ai de dat un test care te învață o lecție.”

(Tom Bodett)

CUVÂNT ÎNAINTE

Scopul acestei lucrări este cercetarea și programarea algoritmilor pseudopolinomiali referitoare la problemele de flux de cost minim. Aceste probleme sunt unele din problemele bazice combinatorice de optimizare, care au o implementare largă pentru multe probleme practice. Modelele de fluxuri optime se aplică la cercetarea şi soluţionarea problemelor din economie, tehnică, biologie, medicină şi altele.

Primul capitol, intitulat Noțiuni introductive, conține noțiuni generale referitoare la grafuri sub formă de definiții și exemple. În programarea algoritmilor pseudopolinomiali pentru fluxuri de cost minim s-a folosit reprezentarea fluxurilor sub formă matricială: matricea de adiacență, matricea costurilor, matricea fluxurilor, datele fiind citite dintr-un fișier text.

Capitolul II – Parcurgeri de grafuri, prezintă două metode de “vizitare” a nodurilor grafurilor orientate, cea folosită în rezolvarea algoritmilor vizați fiind metoda de parcurgere în lățime (BF).

Capitolul III – Distanțe și drumuri minime detaliază problemele de drum minim, referindu-se în principal la Algoritmul Dijkstra, deoarece acest algoritm s-a inclus în implementarea algoritmilor pentru fluxuri de cost minim.

Capitolul IV, intitulat Fluxuri de cost minim, reprezintă capitolul principal al lucrării, deoarece conține algoritmii pseudopolinomiali cercetați din cadrul problemelor de flux de cost minim.

Ultimul capitol conține, în cazul fiecărui algoritm implementat, fișierul sursă al algoritmului, un exemplu de fișier de intrare, precum și rezultatul execuției softului.

Implementarea algoritmilor pseudopolinomiali pentru problemele de flux de cost minim, în limbajul de programare Java a fost o adevărată lecție de viață, o provocare, datorită faptului că, pornind de la zero (la începutul anului universitar), am ajuns să programez corect algoritmii propuși. După zeci și zeci de rulări, ciclări infinite, rezultate eronate afișate, calcule și fluxuri desenate pe hârtie, metode refăcute de câteva ori, s-au “născut” și algoritmii corecți. Implementările sunt structurate pe metode bine puse la punct, gândite și formulate simplu și clar.

Am convingerea că acești primi pași în limbajul Java vor continua pentru implementarea altor algoritmilor, mai ales datorită vocației mele de dascăl.

CAPITOLUL I

NOȚIUNI INTRODUCTIVE

1.1. VOCABULARUL DE BAZĂ ÎN TEORIA GRAFURILOR

Definiția 1.1. Se numește graf orientat un triplet G=(N,A,g) format dintr-o mulțime de N elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite arce și dintr-o aplicație numită funcție de incidență, prin care fiecărui element din a i se asociază o pereche ordonată (x,y) cu x y; dacă eliminăm condiția x y atunci arcul de forma (x,x) se numește buclă, iar G se numește graf general orientat.

În continuare vom presupune că graful orientat G este finit, adică mulțimea nodurilor N={ , x, } este finită și familia arcelor A={ , a, } este un șir finit. Cardinalul mulțimii N notat |N|=n, se numește ordinul grafului orientat G.

Un graf orientat G=(N,A,g) se reprezintă grafic în modul următor:

 Fiecare nod x se reprezintă printr-un punc sau cerculeț în plac;

 Fiecare arc a , a=(x,y) se reprezintă printr-o linie care unește cele două noduri și pe care se află o săgeată cu sensul de la x la y.

Exemplul 1.1. Graful din figura 1.1. este de ordinul 8.

Definiția 1.2. Două grafuri orientate G1=(N1,A1,g1) și G2=(N2,A2,g2) se numesc izomorfe, dacă există o bijecție cu proprietatea că aplicația , definită prin , este o bijecție.

Definiția 1.3. Dacă oricare pereche ordonată (x,y) este imaginea a cel mult q, q>1, elemente din A, atunci G=(N,A,g) se numește multigraf orientat. În paragrafele următoare ne vom ocupa de grafuri orientate cu q=1. În acest caz funcția g este injectivă și familia A este o mulțime. Un astfel de graf se numește digraf și se notează G=(N,A).

Definiția 1.4. Se numește graf neotientat un triplet G=(N,A,g) format dintr-o mulțime N de elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite muchii și dintr-aplicație numită funcție de incidență, prin care fiecărui element a i se asociază o pereche ; dacă considerăm , unde aplicație , atunci aplicația g asociază fiecărui element a , fie o pereche de noduri care se notează sau , fie un nod care se notează și se numește buclă, iar G se numește graf general neorientat.

În continuare presupunem că graful neorientat G este finit, adică mulțimea nodurilor N este finită și familia muchiilor A este un șir finit.

Un graf neorientat G=(N, A, g) se reprezintă grafic la fel ca în cazul grafurilor orientate cu deosebirea că o muchie se reprezintă printr-o linie care unește cele două noduri fără săgeata care precizează sensul în cazul arcului. De asemenea, la fel ca în cazul grafurilor orientate se definește izomorfismul a două grafuri neorientate.

Preview document

Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 1
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 2
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 3
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 4
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 5
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 6
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 7
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 8
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 9
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 10
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 11
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 12
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 13
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 14
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 15
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 16
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 17
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 18
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 19
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 20
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 21
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 22
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 23
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 24
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 25
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 26
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 27
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 28
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 29
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 30
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 31
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 32
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 33
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 34
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 35
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 36
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 37
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 38
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 39
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 40
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 41
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 42
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 43
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 44
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 45
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 46
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 47
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 48
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 49
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 50
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 51
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 52
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 53
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 54
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 55
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 56
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 57
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 58
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 59
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 60
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 61
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 62
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 63
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 64
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 65
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 66
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 67
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 68
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 69
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 70
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 71
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 72
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 73
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 74
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 75
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 76
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 77
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 78
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 79
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 80
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 81
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 82
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 83
Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim - Pagina 84

Conținut arhivă zip

  • Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim.doc

Alții au mai descărcat și

Arhitectura calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Sistem de Prognosticare a Unei Avarii

Acest sistem calculeaza gradul de avariere a unei cladiri în cazul unui cutremur, precum si posibila necesitate a reconstructiei cladirii (partiala...

Ai nevoie de altceva?