Pag 1 Brebenel George – Colegiul Tehnic ”Iuliu Maniu” - 2012

Profesor Coordonator: Brebenel George

CAPITOLUL 1

Pag 2 Brebenel George – Colegiul Tehnic ”Iuliu Maniu” - 2012

Enunţ general : “Se consideră o mulţime A. Se cere o submulţime a sa

astfel încât să fie îndeplinite anumite condiţii (acestea diferă de la o

problemă la alta)”.

Structura generală a unei aplicaţii Greedy (lacom) :

Sol:=0;Repetă

Alege x€A;Dacă este posibil Atunci SolSol+x;

Până când am obţinut soluţiaAfişează Sol;

Metoda Greedy se aplică în două cazuri :

a)Atunci când ştim sigur că se ajunge la soluţia dorită (avem la bază o demonstraţie)

b)Atunci când nu dispunem de o soluţie în timp polinomial.

GENERALITĂŢI

Pag 3 Brebenel George – Colegiul Tehnic ”Iuliu Maniu” - 2012

Problema comis-voiajorului

Enunţ : ”Un comis-voiajor pleacă dintr-un oraş, trebuie să viziteze un

număr de oraşe şi să se întoarcă în oraşul de unde a plecat cu efort minim.

Orice oraş i este legat printr-o şosea de orice alt oraş j printr-un drum de

A[i,j] kilometri. Se cere traseul pe care trebuie să-l urmeze comis-voiajorul,

astfel încât să parcurgă un număr minim de kilometri.”

Fie oraşele de mai jos şi matricea care reţine distanţele dintre ele :

1

5

4 3

2

1

2

6

9

3

155

4

1

Pag 4 Brebenel George – Colegiul Tehnic ”Iuliu Maniu” - 2012

Problema comis-voiajorului

Rezolvare : se alege un oraş de pornire. La fiecare pas se selectează un

alt oraş, prin care nu s-a mai trecut şi aflat la distanţa minimă faţă de oraşul

de pornire. Algoritmul se încheie atunci când am selectat toate oraşele.

Obs: vectorul S va reţine oraşele deja selectate.

De exemplu, dacă se porneşte cu oraşul 1, se va obţine un drum de

lungime 14 care trece prin oraşele : 1, 2, 5, 3, 4, şi 1.

Pag 5 Brebenel George – Colegiul Tehnic ”Iuliu Maniu” - 2012

Problema comis-voiajorului

#include <iostream.h>Int S[10], A[10][10], n, i, j, v, vs, vs1, min, cost;int main(){ cout<<”Numar de noduri=”; cin>>n; //citesc matricea for (i=1;i<=n;i++) for (j=1;j<=n;j++){ cin>>A[i][j]; A[j][i]= A[i][j] } //pentru fiecare nod cout<<”Nod de pornire”; cin>>v; S[v]=1; vs1=v; cout<<”Drumul trece prin “; for (i=1;i<=n-1;i++){ min=30000; for (j=1;j<=n;j++) if (A[v][j]!=0 && S[j]==0 && min>A[v][j]){

min=A[v][j];vs=j;

} cost+=A[v][vs]; cout<<vs<<” “ S[vs]=1; v=vs; } cost+=A[vs1][v]; cout<<”Cost= <<cost“;return 0;}