Jfyhkgu

Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Un algoritmo greedy è un algoritmo che cerca una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) a ogni passo locale. Quando applicabili questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale, mentre negli altri non è garantita la convergenza all'ottimo globale.

Esempi esplicativi |

Il problema "Dai il minor numero di monete di resto utilizzando monete da 100, 10, 1 eurocent" è un problema risolubile tramite un algoritmo di tipo greedy: ad ogni passo viene controllato il resto ancora da dare e si aggiunge la moneta con il maggior valore possibile. Quindi per dare un resto di 112 eurocent la macchina farà cadere in sequenza una moneta da 100, poi 10, poi 1, e infine ancora 1 eurocent per un totale di 4 monete.

Il problema comunemente detto "del Commesso Viaggiatore", cioè "dato un numero di consegne e di ritiri con un mezzo che ha una portata massima P, si organizzi il viaggio che consente di viaggiare il minor numero di km con il maggior carico possibile per ottenere il massimo guadagno", non è un problema risolvibile tramite un algoritmo di tipo greedy, ma solo tramite algoritmi per problemi NP-Completi.

Il primo esempio è risolvibile grazie ad un algoritmo greedy solo per quell'insieme di valori di monete: infatti se ci fossero anche monete da 105 eurocent (valori monete: 105, 100, 10, 1), l'algoritmo greedy darebbe un totale di 8 monete (una da 105 e 7 da 1), mentre la soluzione ottima è quella con 4 monete (100+10+1+1).

Definizione formale |

In combinatoria e in ottimizzazione per algoritmo greedy si intende un algoritmo che consente di individuare una base di una matroide finita procedendo in modo notevolmente semplice ed efficiente.

Si consideri l'insieme E e una famiglia F di sottoinsiemi di E (F⊆2E{displaystyle Fsubseteq 2^{E}}) che forma un ideale d'ordine rispetto alla relazione di inclusione:

A∈F∧B⊆A→B∈F{displaystyle Ain Fland Bsubseteq Ato Bin F}

La coppia E,F forma un sistema di indipendenza. Viene definita inoltre la funzione peso w.

Dato un sistema di indipendenza E,F e una funzione peso w, si ricava un insieme M tale che w(M) sia il massimo.

Descrizione dell'algoritmo |

Si consideri un matroide degli indipendenti M = (E,I). L'algoritmo si serve di un insieme variabile X che viene progressivamente ampliato fino a individuare una base.

• Inizialmente si assegna l'insieme vuoto all'insieme variabile X.


• Si procede considerando successivi elementi x in E non contenuti in X;
  
  • Se X∪{x}{displaystyle Xcup {x}} è indipendente, allora si trasforma il precedente X aggiungendogli x, cioè X:=X∪{x}{displaystyle X:=Xcup {x}}. In caso contrario il processo si conclude.
  
  

Il risultato è un insieme indipendente. Inoltre esso è un insieme indipendente massimale in quanto se B U {x} non fosse indipendente per qualche sottoinsieme B di X, allora X∪{x}{displaystyle Xcup {x}} non sarebbe indipendente: in caso contrario si andrebbe contro la proprietà di ereditarietà. Quindi se si trascura un elemento non si avrà l'opportunità di utilizzarlo più tardi.

Matroidi pesati e algoritmi greedy |

Generalizzazione di questo algoritmo per risolvere un problema più difficile.

Una funzione peso w : E → R⁺ per un matroide M=(E, I) assegna un peso strettamente positivo a ciascun elemento di E. Estendendo la funzione ai sottoinsiemi di E attraverso la somma; w(A) è la somma dei w(x) sugli x in A. Un matroide con una funzione peso associata è detto un matroide pesato.

Come semplice esempio, diciamo di voler trovare la massima foresta di copertura di un grafo. Ovvero, dato un grafo e un peso per ogni arco, trovare una foresta contenente ogni vertice e che massimizzi il peso totale degli archi nell'albero. Questo problema si presenta in alcune applicazioni di clustering. Se guardiamo alla definizione del matroide foresta sopra, vediamo che la massima foresta di copertura è semplicemente il sottoinsieme indipendente con peso totale massimo — tale da ricoprire il grafo, poiché in caso contrario potremmo aggiungere archi senza creare cicli. Ma come lo troviamo?

Un insieme indipendente di massimo peso totale è chiamato insieme ottimale. Gli insiemi ottimali sono sempre basi, perché se può essere aggiunto un arco, dovrebbe essere fatto; ciò aumenta solo il peso totale. Si può dimostrare che esiste un banale algoritmo greedy per calcolare un insieme ottimale di una matroide pesata. Procede come segue:

• Sia A l'insieme vuoto.


• Per ogni x in E, preso in ordine (monotonicamente) decrescente di peso
  
  • se A U {x} è indipendente, allora A diventi A U {x}.
  
  

Tale algoritmo trova una base, poiché si tratta di un caso speciale del precedente algoritmo. Sceglie sempre l'elemento di massimo peso possibile preservando l'indipendenza (da cui il termine "greedy"). Ciò produce sempre un insieme ottimale: supponiamo che produca A={e1,e2,…,er}{displaystyle A={e_{1},e_{2},ldots ,e_{r}}} e che B={f1,f2,…,fr}{displaystyle B={f_{1},f_{2},ldots ,f_{r}}}. Ora per ogni k{displaystyle k} con 1≤k≤r{displaystyle 1leq kleq r}, consideriamo gli insiemi aperti O1={e1,…,ek−1}{displaystyle O_{1}={e_{1},ldots ,e_{k-1}}} e O2={f1,…,fk}{displaystyle O_{2}={f_{1},ldots ,f_{k}}}. Visto che O1{displaystyle O_{1}} è più piccolo di O2{displaystyle O_{2}}, c'è qualche elemento di O2{displaystyle O_{2}} che può essere messo in O1{displaystyle O_{1}} mantenendo il risultato indipendente. Tuttavia ek{displaystyle e_{k}} è un elemento di peso massimale che può essere aggiunto a O1{displaystyle O_{1}} per mantenere l'indipendenza. Per cui ek{displaystyle e_{k}} è di peso non inferiore di qualche elemento di O2{displaystyle O_{2}}, e quindi ek{displaystyle e_{k}} è of almeno di peso pari a fk{displaystyle f_{k}}. Poiché questo vale per ogni k{displaystyle k}, A{displaystyle A} è più pesante di B{displaystyle B}.

Il modo più facile per traversare i membri di E nell'ordine desiderato è di ordinarli. Ciò richiede tempo O(|E|log|E|) utilizzando un algoritmo di ordinamento. Abbiamo anche bisogno di test per ogni x per determinare se A U {x} è indipendente; assumendo che il test di indipendenza richieda tempo O(f(|E|)) time, il tempo complessivo per l'algoritmo è O(|E|log|E| + |E|f(|E|)).

Se vogliamo trovare un albero di copertura minimo invece, semplicemente "invertiamo" la funzione peso sottraendola da una grande costante. Più precisamente, sia w_min(x) = W - w(x), dove W superi il peso totale attraverso tutti gli archi del grafo. Molti altri problemi di ottimizzazione su vari tipi di matroidi e funzioni peso possono essere risolti in questo modo banale, sebbene in molti casi possono essere trovati algoritmi più efficienti che sfruttano proprietà più specifiche.

Notare anche che se prendiamo un insieme I{displaystyle I} di insiemi "indipendenti" che è un down-set ma non una matroide, allora l'algoritmo greedy non funzionerà sempre. Poiché in tal caso ci sono insiemi indipendenti I1{displaystyle I_{1}} e I2{displaystyle I_{2}} con |I1|<|I2|{displaystyle |I_{1}|<|I_{2}|}, ma tali che per nessun e∈I2∖I1{displaystyle ein I_{2}setminus I_{1}} è I1∪e{displaystyle I_{1}cup e} indipendente.

Prendiamo un ε>0{displaystyle varepsilon >0} e τ>0{displaystyle tau >0} tali che (1+2ε)|I1|+τ|E|<|I2|{displaystyle (1+2varepsilon )|I_{1}|+tau |E|<|I_{2}|}. Pesiamo gli elementi di I1∪I2{displaystyle I_{1}cup I_{2}} nell'intervallo da 2{displaystyle 2} a 2+2ε{displaystyle 2+2varepsilon }, gli elementi di I1∖I2{displaystyle I_{1}setminus I_{2}} nell'intervallo da 1+ε{displaystyle 1+varepsilon } a 1+2ε{displaystyle 1+2varepsilon }, gli elementi di I2∖I1{displaystyle I_{2}setminus I_{1}} nell'intervallo da 1{displaystyle 1} a 1+ε{displaystyle 1+varepsilon }, e il resto nell'intervallo da 0{displaystyle 0} a τ{displaystyle tau }. L'algoritmo greedy sceglierà gli elementi di I1{displaystyle I_{1}}, e in seguito non potrà scegliere nessun elemento di I2∖I1{displaystyle I_{2}setminus I_{1}}. Di conseguenza l'insieme indipendente che costruisce sarà di peso non superiore a (1+2ε)|I1|+τ|E|+|I1∪I2|{displaystyle (1+2varepsilon )|I_{1}|+tau |E|+|I_{1}cup I_{2}|}, che è più piccolo del peso di I2{displaystyle I_{2}}.

Voci correlate |

• Colorazione golosa


• Greedoide

Altri progetti |

• 
  Wikimedia Commons contiene immagini o altri file su algoritmo greedy
  

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica