|
|
Molti dei problemi per i quali un algoritmo di tipo greedy fornisce una soluzione ottima, possono essere formulati come Matroidi. La teoria dei Matroidi è stata introdotta da Whitney per studiare le proprietà algebriche delle dipendenze lineari. Un matroide M è una coppia (S,F), dove S è un insieme finito di elementi ed F è una famiglia di sottoinsiemi indipendenti di S che soddisfa le seguenti proprietà:
Ereditarietà: l’insieme vuoto appartiene ad F e tutti i sottoinsiemi propri di un insieme di F appartengono anch’essi ad F, ovvero:
Scambio: se due insiemi di F non hanno la stessa cardinalità, allora un elemento che sta soltanto nel sottoinsieme più grande può essere aggiunto all’insieme più piccolo e l’insieme risultante appartiene
ancora ad F, ovvero:
Un insieme I appartenente a F per il quale non è possibile aggiungere elementi secondo la proprietà dello scambio è detto massimale. Un matroide è detto pesato se ad ogni elemento di S è associato un peso. La caratteristica rilevante dal punto di vista algoritmico dei matroidi pesati è che il metodo greedy verifica le proprietà della “scelta greedy” e della “sottostruttura ottima” e che pertanto trova sempre l’insieme massimale di peso massimo.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.