Algoritmo greedy: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
correzione di "non so" in "non si" |
Funzionalità collegamenti suggeriti: 2 collegamenti inseriti. |
||
Riga 4:
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 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 ==
Riga 60:
Una ''funzione peso'' ''w'' : ''E'' → '''R'''<sup>+</sup> 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:
| |||