Quadratic pseudo-Boolean optimisation: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
ortografia |
|||
Riga 15:
allora la funzione può essere ottimizzata tramite [[graph cut]]. È infatti possibile rappresentarla tramite un grafo a pesi non negativi, e il minimo globale può essere determinato in tempo polinomiale tramite un taglio minimo del grafo, che può essere calcolato efficientemente con algoritmi come quelli di [[algoritmo di Ford-Fulkerson|Ford-Fulkerson]], [[algoritmo di Edmonds-Karp|Edmonds-Karp]], e [[algoritmo di Boykov-Kolmogorov|Boykov-Kolmogorov]].
Se la condizione di submodularità non è soddisfatta, il problema nel caso generale è [[NP-hard]] e non può sempre essere risolto esattamente in tempo polinomiale con un semplice graph cut. È possibile approssimare la [[funzione obiettivo]] con una funzione simile, ma submodulare, ad esempio eliminando i termini non submodulari o sostituendoli con un'approssimazione submodulare, ma tale approccio produce generalmente risultati sub-ottimali la cui qualità è accettabile solo se il numero di termini non submodulari è relativamente piccolo.<ref name="review" />
QPBO costruisce un grafo esteso, introducendo un insieme di variabili ausiliarie idealmente equivalenti alla negazione delle variabili del problema. La funzione associata a tale grafo è submodulare e può essere ottimizzata tramite graph cut: se i nodi del grafo associati a una variabile vengono separati dal taglio minimo in componenti connesse diverse il valore della variabile è definito, mentre se i nodi sono nella stessa componente non è possibile inferire il valore ottimale della variabile corrispondente. Tale metodo produce risultati generalmente superiori rispetto alla soluzione tramite graph cut di approssimazioni submodulari di funzioni non submodulari.<ref name="review" />
| |||