Algoritmo greedy e Wikipedia:Pagine da cancellare/Conta/2019 giugno 30: differenze tra le pagine

Versione delle 10:37, 12 feb 2013

Versione delle 19:41, 7 lug 2019

Riga 1:

{{Conteggio cancellazioni}}

Un '''algoritmo greedy''' è un [[algoritmo]] che cerca di ottenere 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) ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale (cfr. [[NP-Completo|Problemi NP-Completi]], cioè problemi di soluzione non deterministica polinomiale).

{{Conteggio cancellazioni/In corso/Start|19:41, 7 lug 2019 (CEST)}}

{{Conteggio cancellazioni/In corso/Voce|i = 1 |voce = Wagner Lamounier |turno = |tipo = consensuale prorogata |data = 2019 giugno 30 |multipla = |argomenti = musica |temperatura = 33 }}

== Esempi esplicativi ==

{{Conteggio cancellazioni/In corso/Voce|i = 2 |voce = Giuseppe Di Bianco |turno = |tipo = consensuale |data = 2019 giugno 30 |multipla = |argomenti = musica classica |temperatura = 40 }}

Il problema "Dai il minor numero di monete di resto utilizzando monete da 100, 10, 1 eurocent" è un problema risolvibile tramite un algoritmo di tipo greedy: ad ogni passo viene controllato il resto ancora da dare e si aggiunge la moneta con valore maggiore 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).

{{Conteggio cancellazioni/In corso/Voce|i = 3 |voce = Gaetano Nespro |turno = |tipo = consensuale |data = 2019 giugno 30 |multipla = |argomenti = sport |temperatura = 45 }}

{{Conteggio cancellazioni/In corso/Voce|i = 4 |voce = Voci su numeri allo stato tautologico |turno = |tipo = consensuale |data = 2019 giugno 30 |multipla = 1 |argomenti = |temperatura = 25 }}

Il problema comunemente detto [[Problema del commesso viaggiatore|"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 [[NP-Completo|problemi NP-Completi]].

{{Conteggio cancellazioni/In corso/Voce|i = 5 |voce = Tsilaisite |turno = |tipo = consensuale |data = 2019 giugno 30 |multipla = |argomenti = mineralogia |temperatura = 16 }}

{{Conteggio cancellazioni/In corso/Voce|i = 6 |voce = Informatica applicata |turno = |tipo = semplificata |data = 2019 giugno 30 |multipla = |argomenti = informatica |temperatura = 0 }}

Facciamo notare che il problema del primo esempio, che possiamo chiamare "Minor monete di resto", è risolvibile grazie ad un algoritmo greedy solo per quell'insieme di valori di monete: se infatti avessimo anche monete da 105 eurocent, l'algoritmo greedy darebbe un totale di 8 monete (una da 105 e 7 da 1), quando posso trovare una soluzione ottima con 4 monete (100+10+1+1).

{{Conteggio cancellazioni/In corso/Voce|i = 7 |voce = Democrazia islamica |turno = |tipo = semplificata |data = 2019 giugno 30 |multipla = |argomenti = politica, religione |temperatura = 23 }}

{{Conteggio cancellazioni/In corso/Voce|i = 8 |voce = Carlo Napoleone Bonaparte |turno = |tipo = semplificata |data = 2019 giugno 30 |multipla = |argomenti = politica |temperatura = 18 }}

== Definizione formale ==

{{Conteggio cancellazioni/In corso/Voce|i = 9 |voce = Paperino, sei forte! |turno = |tipo = semplificata |data = 2019 giugno 30 |multipla = |argomenti = animazione |temperatura = 8 }}

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.

{{Conteggio cancellazioni/In corso/Stop}}

Consideriamo l'insieme E e una famiglia F di sottoinsiemi di E (<math> F \in 2^E</math>) che forma un [[ideale d'ordine]] rispetto alla relazione di inclusione:

<math>A \in F \and B \subseteq A \to B \in F</math>

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 assegniamo l'insieme vuoto all'insieme variabile ''X''.

* Procediamo a considerare successivi elementi ''x'' in ''E'' non contenuti in ''X'';

** Se <math>X \cup \{x\}</math> è indipendente, allora trasformiamo il precedente ''X'' aggiungendogli x, cioè applichiamo l'istruzione <math>X := X \cup \{x\}</math>. In caso contrario il processo si conclude.

Il risultato è chiaramente un insieme indipendente. Esso inoltre è un insieme indipendente massimale, in quanto se B U {x} non è indipendente per qualche sottoinsieme B di ''X'', allora <math>X \cup \{x\}</math> non è indipendente (in caso contrario si andrebbe contro la proprietà di ereditarietà). Quindi se trascuriamo un elemento non avremo l'opportunità di utilizzarlo più tardi.

== Matroidi pesati e algoritmi greedy ==

Generalizziamo 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''. Estendiamo 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 <math>A=\{e_1,e_2,\ldots,e_r\}</math> e che <math>B=\{f_1,f_2,\ldots,f_r\}</math>. Ora per ogni <math>k</math> con <math>1\le k\le r</math>, consideriamo gli insiemi aperti <math>O_1=\{e_1,\ldots,e_{k-1}\}</math> e <math>O_2=\{f_1,\ldots,f_k\}</math>. Visto che <math>O_1</math> è più piccolo di <math>O_2</math>, c'è qualche elemento di <math>O_2</math> che può essere messo in <math>O_1</math> mantenendo il risultato indipendente. Tuttavia <math>e_k</math> è un elemento di peso massimale che può essere aggiunto a <math>O_1</math> per mantenere l'indipendenza. Per cui <math>e_k</math> è di peso non inferiore di qualche elemento di <math>O_2</math>, e quindi <math>e_k</math> è of almeno di peso pari a <math>f_k</math>. Poiché questo vale per ogni <math>k</math>, <math>A</math> è più pesante di <math>B</math>.

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 <math>I</math> 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 <math>I_1</math> e <math>I_2</math> con <math>|I_1|<|I_2|</math>, ma tali che per nessun <math>e\in I_2\setminus I_1</math> è <math>I_1\cup e</math> indipendente.

Prendiamo un <math>\varepsilon>0</math> e <math>\tau>0</math> tali che <math>(1+2\varepsilon)|I_1|+\tau|E|<|I_2|</math>. Pesiamo gli elementi di <math>I_1\cup I_2</math> nell'intervallo da <math>2</math> a <math>2+2\varepsilon</math>, gli elementi di <math>I_1\setminus I_2</math> nell'intervallo da <math>1+\varepsilon</math> a <math>1+2\varepsilon</math>, gli elementi di <math>I_2\setminus I_1</math> nell'intervallo da <math>1</math> a <math>1+\varepsilon</math>, e il resto nell'intervallo da <math>0</math> a <math>\tau</math>. L'algoritmo greedy sceglierà gli elementi di <math>I_1</math>, e in seguito non potrà scegliere nessun elemento di <math>I_2\setminus I_1</math>. Di conseguenza l'insieme indipendente che costruisce sarà di peso non superiore a <math>(1+2\varepsilon)|I_1|+\tau|E|+|I_1\cup I_2|</math>, che è più piccolo del peso di <math>I_2</math>.

== Voci correlate ==

*[[Greedoide]]

[[Categoria:Algoritmi di ottimizzazione]]

[[Categoria:Teoria delle matroidi]]

<!--[[Categoria:Ottimizzazione combinatoria]]-->

{{Portale|matematica}}