Resúmenes

La tecnica golosa è utilizzata generalmente per risolvere problemi di ottimizzazione cioè problemi in cui bisogna ricercare una soluzione che soddisfi alcuni vincoli e che massimizzi/minimizzi il valore di una funzione obiettivo.

max F = Σ xᵢ * Vᵢ (x₁ ... xₙ) vincoli:

• c(x₁ ... xₙ) ≤ cₘₐₓ
• 0 ≤ xᵢ ≤ qᵢ | i = 1, ..., n

La tecnica golosa, invece di effettuare una scelta globale degli oggetti più convenienti, determina la soluzione in stadi in ciascuno dei quali effettua una scelta parziale di ottimo (scelta golosa) che successivamente aggiunge alla soluzione.

Si determina al primo stadio l'oggetto che "sembra" più conveniente attraverso il suo valore specifico (vᵢ/cᵢ). Al secondo e i successivi si reitera questa scelta fino a che non vengono violati i vincoli o non ci sono più oggetti.

Un grande difetto di questa tecnica è che non si ha una visione d'insieme dell'intero problema ma bensì limitata allo stadio corrente. Questo potrebbe inficiare la soluzione stessa, da qui GREEDY, perchè vado a escludere potenziali soluzioni migliori.

Un aspetto importante nell'utilizzo di un algoritmo goloso è dimostrare che la soluzione è ottima e, nel caso non sia verificare, se essa sia comunque sub-ottima cioè vicina alla ottima. Nel primo caso (soluzione ottima) si parla di algoritmo esatto; nel secondo caso si parla di algoritmo euristico/approssimato.

ESEMPIO:

Tcambio cambio(const vector<float>& tagli, float valoreAssegno) {
  int n = tagli.size();
  Tcambio sol(n);
  for(int i = 0; i < n && sol.valore < valoreAssegno; ++i) {
      sol.nMonete[i] = (valoreAssegno - sol.valore)/tagli[i];
      sol.valore += sol.nMonete[i]*tagli[i];
  }
  if(sol.valore < valoreAssegno) {
      sol.nMonete[n-1]++;
      sol.valore += tagli[n-1];
  }
} // complessita' O(n), n = numero dei tagli

Questo algoritmo ha complessità di O(n) perché diamo per scontato che i tagli siano già ordinati in senso decrescente del valore specifico.

Più in generale la complessità di un algoritmo goloso dipende dal valore specifico il quale può essere:

• STATICO: se già ordinato O(n), altrimenti O(n log n) + x + complessità dy;
• DIPENDENTE DALLE SCELTE: ricalcolare il valore specifico per ogni scelta O(n²);

L'algoritmo proposto sopra potrebbe non generare la soluzione ottima. Infatti è strettamente influenzata dai "tagli" ed anche per la natura "greedy" dell'algoritmo stesso.

ESEMPIO: cambiare 8 euro con:

	Risposta	Ottima
5	1	0
4	0	2
2	1	0
1	1	0