Algoritmo greedy: differenze tra le versioni

Versione delle 23:58, 17 nov 2005

Versione attuale delle 18:10, 13 dic 2024

(82 versioni intermedie di 62 utenti non mostrate)

Riga 1:

{{F|algoritmi|ottobre 2015}}

{{da tradurre|inglese}}

Un '''algoritmo ''greedy''''' o '''algoritmo goloso'''<ref>{{cita libro|citazione=È opportuno sottolineare che [[Algoritmo di Kruskal|quello di Kruskal]] è un algoritmo che appartiene alla famiglia degli algoritmi "golosi", in gergo ''greedy''.|url=https://www.google.it/books/edition/Programmare_in_C_Guida_al_linguaggio_att/BybdDwAAQBAJ?hl=it&gbpv=1&dq=algoritmi+golosi&pg=PA279&printsec=frontcover|isbn=9788835807896|cognome=Liverani|nome=Marco|titolo=Programmare in C. Guida al linguaggio attraverso esercizi svolti e commentati|editore=Società Editrice Esculapio|anno=2020|p=279}}</ref><ref>{{cita libro|cognome1=Berardi|nome1=Luigia|cognome2=Beutelspacher|nome2=Albrecht|titolo=Matematica discreta. Dai fondamenti alle applicazioni|editore=Franco Angeli|anno=2003|lingua=it|p=62|url=https://www.google.it/books/edition/Matematica_discreta_Dai_fondamenti_alle/JrFOKxhi1DQC?hl=it&gbpv=1&dq=algoritmo+goloso&pg=PA62&printsec=frontcover|isbn=9788846449207}}</ref><ref>{{cita libro|cognome=Cerasoli|nome=Mauro|titolo=Elementi di matematica discreta|editore=Zanichelli|anno=1988|lingua=it|p=244|url=https://www.google.it/books/edition/Elementi_di_matematica_discreta/N-3uAAAAMAAJ?hl=it&gbpv=1&bsq=algoritmo+goloso&dq=algoritmo+goloso&printsec=frontcover|isbn=9788808038586}}</ref> è un [[paradigma algoritmico]] in base al quale la ricerca di una soluzione ottimale avviene seguendo una strategia euristica di problem-solving in cui l'[[algoritmo]], a ogni passaggio, opta per la soluzione ottimale a livello locale (come definita in precedenza dal programmatore). Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un [[tempo polinomiale]]; in molti casi, non si può garantire la convergenza verso un ottimo globale. In particolare, questi algoritmi cercano di mantenere una proprietà di ''sottostruttura ottima'', quindi cercano di risolvere i sottoproblemi in maniera "avida" (da cui la traduzione letterale ''algoritmi avidi'' in italiano) considerando una parte definita migliore nell'input per risolvere tutti i problemi.

In [[combinatorica]] 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.

Per fare ciò, di solito, viene applicata una tecnica ''cut and paste'' (quindi scelgo l'input migliore per poter risolvere il sottoproblema).

Un tipo di strategia greedy può essere applicata al [[problema del commesso viaggiatore]] (che è un problema ad alta [[Teoria della complessità computazionale|complessità computazionale]]): essa può essere, ad esempio, quella che , a ogni passaggio, obbedisce alla seguente regola euristica: "A ogni passo del tragitto, vai alla più vicina tra le città non ancora visitate". L'adozione di questo semplice approccio [[Euristica|euristico]] non è in grado di garantire la soluzione ottima a questo problema complesso, ma ha il pregio che l'esecuzione termina dopo un ragionevole numero di passi; trovare una soluzione ottimale a un problema così complesso richiede, tipicamente, un numero altissimo di passaggi, circostanza che lo rende un problema praticamente non affrontabile.

== 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 cosiddetto [[problema 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]].

Il primo esempio è risolvibile grazie ad un algoritmo greedy solo per opportuni insiemi di valori di monete: infatti se ci fossero ad esempio 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).

Un altro esempio noto e ampiamente conosciuto è l'algoritmo di ''selezione delle attività'', il cui [[pseudocodice]] è presentato dal Cormen<ref>{{Cita libro|nome=Thomas H.|cognome=Cormen|nome2=Charles E.|cognome2=Leiserson|nome3=Ronald L.|cognome3=Rivest|titolo=Introduction to Algorithms|url=https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition|accesso=2022-01-08|edizione=4|data=2022-03-22|editore=MIT Press|lingua=en|ISBN=978-0-262-04630-5}}</ref>.

<math>\text{greedy-activity-selector}(s,f)</math>

<math>A = A_1</math>

<math>k=1 </math>

<math>for \ m=2 \ to \ n</math>

<math>if \ s[m] \geq f(k)</math>

<math>A = A \bigcup a_m</math>

<math>k=m</math>

<math>return \ A</math>

Tale algoritmo seleziona le attività che sono compatibili da un punto di vista temporale, evitando che si sovrappongano. Piuttosto che selezionare tutte le attività, seleziona il maggior numero di attività tali che non siano sovrapponibili l'una con l'altra, quindi con inizio/fine distinti le une dalle altre. Un altro esempio noto di algoritmo greedy è la [[codifica di Huffman]], normalmente utilizzato nella compressione dei file e che utilizza il medesimo principio, quindi l'ottimizzazione dei dati presenti selezionando le frequenze in maniera ottimale alla posizione e numero dei singoli caratteri.

== Definizione formale ==

In [[combinatoricacombinatoria]] e in [[Ottimizzazione (matematica)|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 (<math> F \subseteq 2^E</math>) che forma un [[Ideale (matematica)|ideale]] d'ordine rispetto alla relazione di inclusione:

<math>A \in F \land 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 unaun [[matroide]] degli indipendenti]] ''M'' = (''E'',''I''). L'algoritmo si serve di un insieme variabile ''X'' che viene progressivamente ampliato fino a individuare una base.

L'algoritmo si serve di un insieme variabile ''X'' che viene progressivamnete ampliato fino a individuare una base.

* Inizialmente assegnamosi assegna l'insieme vuoto all'insieme variabile ''X''.

* ProcediamoSi aprocede considerareconsiderando successivi elementi ''x'' in ''E'' non contenuti in ''X'';

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

Il risultato è chiaramente un insieme indipendente. EssoInoltre inoltreesso è un [[insieme indipendente massimale,]] in quanto se B U {x} non èfosse indipendente per qualche sottoinsieme B di ''X'', allora ''<math>X'' U\cup \{x\}</math> non èsarebbe indipendente: (in caso contrario si andrebbe contro la proprietà di ereditarietà). Quindi se trascuriamosi trascura un elemento, non avremosi avrà l'opportunità di utilizzarlo più tardi.

== Matroidi pesatepesati e algoritmi greedy ==

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

Una ''funzione peso'' ''w'' : ''E'' &rarr;→ '''R'''⁺ per un matroide ''M''=(''E'', ''I'') assegna un peso strettamente positivo a ciascun elemento di ''E''. EstendiamoEstendendo 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 thela [[maximummassima spanningforesta forestdi copertura]] di un graph[[grafo]]. That isOvvero, dato aun graphgrafo e un peso per ogni edgearco, trovare auna forestforesta contenente ogni vertexvertice e massimizzandoche massimizzi il peso totale degli edgesarchi nell'albero. Questo problema si presenta in alcune applicazioni di clustering. Se guardiamo alla definizione ofdel thematroide forestforesta matroid abovesopra, vediamo che thela maximummassima spanningforesta forestdi copertura è semplicemente l'insiemeil sottoinsieme indipendente con largest peso totale &mdash;massimo un— tale insiemeda devericoprire span theil graphgrafo, forpoiché in caso otherwisecontrario possiamopotremmo aggiungere edgesarchi senza creare cyclescicli. Ma come lo troviamo?

Un insieme indipendente ofdi largestmassimo peso totale è chiamato insieme ''ottimale''. Gli insiemi ottimali sono sempre basi, perché se può essere aggiunto un edgearco, itdovrebbe shouldessere befatto; ciò aumenta solo il peso totale. AsSi itpuò turnsdimostrare out,che c'èesiste aun trivialbanale [[algoritmo greedy]] forper computingcalcolare un insieme ottimale di una matroide pesata. Procede come segue:

* Sia A l'insieme vuoto.

* Per ogni ''x'' in ''E'', takenpreso in ordine (monotonicallymonotonicamente) decreasing orderdecrescente bydi weightpeso

** se A U {x} è indipendente, allora set A todiventi A U {x}.

Tale algoritmo trova una base, sincepoiché itsi istratta di un caso speciale ofdel the aboveprecedente algoritmo. Sceglie sempre l'elemento ofdi largestmassimo peso thatpossibile it can while preservingpreservando l'indipendenza (thusda 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 putmesso intoin <math>O_1</math> conmantenendo the result stillil beingrisultato independentindipendente. Tuttavia <math>e_k</math> è un elemento di peso massimale che può essere aggiunto a <math>O_1</math> per mantenere l'indipendenza. ThusPer cui <math>e_k</math> è ofdi nopeso smallernon pesoinferiore di qualche elemento di <math>O_2</math>, e hencequindi <math>e_k</math> è of almeno adi largepeso apari weight asa <math>f_k</math>. AsPoiché thisquesto is truevale per ogni <math>k</math>, <math>A</math> è weightierpiù pesante di <math>B</math>.

Il modo più facile per traversetraversare i membri di ''E'' nell'ordine desiderato è di sort themordinarli. Ciò richiede tempo O(|E|log|E|) time usingutilizzando a comparisonun [[sorting algoritmo di ordinamento]]. Abbiamo anche bisogno di test per ogni ''x'' whetherper determinare se A U {x} è indipendente; assumingassumendo independenceche testsil test di indipendenza richieda requiretempo O(f(|E|)) time, il totaltempo timecomplessivo per l'algoritmo è O(|E|log|E| + |E|f(|E|)).

Se vogliamo trovare aun minimumalbero spanningdi treecopertura instead,minimo weinvece, simplysemplicemente "invertinvertiamo" la funzione peso sottraendola da auna largegrande costante. Più precisamente, letsia ''w''_min(''x'') = ''W'' - ''w''(''x''), dove ''W'' exceedssuperi theil totalpeso totale attraverso weighttutti overgli allarchi graphdel edgesgrafo. ManyMolti morealtri problemi di ottimizzazione aboutsu allvari sortstipi ofdi matroidsmatroidi e funzioni peso possono essere risolti in thisquesto trivialmodo waybanale, sebbene in molti casi possono essere trovati algoritmi più efficienti che exploitsfruttano moreproprietà specializedpiù proprietàspecifiche.

NoteNotare anche che se prendiamo un insieme <math>I</math> di insiemi "indipendenti" che è aun down-set ma non una matroide, allora l'algoritmo greedy non funzionerà sempre. ForPoiché in tal thencaso ci sono insiemi indipendenti <math>I_1</math> e <math>I_2</math> con <math>|I_1|<|I_2|</math>, ma tali che forper nonessun <math>e\in I_2\setminus I_1</math> è <math>I_1\cup e</math> indipendente.

Pick an <math>\epsilon>0</math> e <math>\tau>0</math> tali che <math>(1+2\epsilon)|I_1|+\tau|E|<|I_2|</math>. Weight gli elementi di <math>I_1\cup I_2</math> in the range <math>2</math> to <math>2+2\epsilon</math>, gli elementi di <math>I_1\setminus I_2</math> in the range <math>1+\epsilon</math> to <math>1+2\epsilon</math>, gli elementi di <math>I_2\setminus I_1</math> in the range <math>1</math> to <math>1+\epsilon</math>, e il resto in the range <math>0</math> to <math>\tau</math>. L'algoritmo greedy sceglierà gli elementi di <math>I_1</math>, e then cannot pick any elements di <math>I_2\setminus I_1</math>. Therefore l'insieme indipendente che costruisce sarà di peso at most <math>(1+2\epsilon)|I_1|+\tau|E|+|I_1\cup I_2|</math>, che è più piccolo del peso di <math>I_2</math>.

PickPrendiamo anun <math>\epsilonvarepsilon>0</math> e <math>\tau>0</math> tali che <math>(1+2\epsilonvarepsilon)|I_1|+\tau|E|<|I_2|</math>. WeightPesiamo gli elementi di <math>I_1\cup I_2</math> in thenell'intervallo rangeda <math>2</math> toa <math>2+2\epsilonvarepsilon</math>, gli elementi di <math>I_1\setminus I_2</math> in thenell'intervallo rangeda <math>1+\epsilonvarepsilon</math> toa <math>1+2\epsilonvarepsilon</math>, gli elementi di <math>I_2\setminus I_1</math> in thenell'intervallo rangeda <math>1</math> toa <math>1+\epsilonvarepsilon</math>, e il resto in thenell'intervallo rangeda <math>0</math> toa <math>\tau</math>. L'algoritmo greedy sceglierà gli elementi di <math>I_1</math>, e thenin seguito non cannotpotrà pickscegliere anynessun elementselemento di <math>I_2\setminus I_1</math>. ThereforeDi conseguenza l'insieme indipendente che costruisce sarà di peso atnon superiore mosta <math>(1+2\epsilonvarepsilon)|I_1|+\tau|E|+|I_1\cup I_2|</math>, che è più piccolo del peso di <math>I_2</math>.

== Note ==

<references/>

== Voci correlate ==

* [[GreedoideColorazione golosa]]

* [[Greedoide]]

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Algoritmi di ottimizzazione|Greedy]]

[[Categoria:Teoria delle matroidi]]

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