Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 23:36, 25 dic 2018

Versione delle 23:41, 25 dic 2018

Riga 22:

QPBO produce una soluzione nella quale le variabili possono assumere tre diversi valori, ''vero'', ''falso'', e ''indefinito'', nel seguito notati rispettivamente con 1, 0, e <math>\emptyset</math>. La soluzione prodotta da QPBO gode di due proprietà, note come ''ottimalità parziale'' e ''persistenza''.

* ''Ottimalità parziale'': se <math>f</math> è submodulare, QPBO calcola il minimo globale esatto in maniera equivalente a graph cut e tutte le variabili nella soluzione assumono un valore non indefinito, mentre se la condizione di submodularità non è soddisfatta il risultato sarà una soluzione parziale <math>\mathbf{\hat{x}^*}</math> nella quale solo per un sottinsieme <math>\hat{V} \subseteq V</math> delle varibili assume un valore non indefinito. Tale soluzione parziale è sempre parte di una soluzione ottimale, ovvero esiste un punto di minimo globale <math>\mathbf{x^*}</math> di <math>f</math> tale che <math>x_i = x_i^*</math> per ogni <math>i \in \hat{V}</math>.

* ''Persistenza'': dati una soluzione <math>\mathbf{x}</math> prodotta da QPBO e un qualsiasi assegnamento di valori <math>\mathbf{y}</math> alle variabili del problema, se si costruisce una nuova soluzione <math>\hat{\mathbf{y}}</math> sostituendo <math>y_i</math> con <math>x_i</math> per ogni <math>i \in \hat{V}</math>, si ha <math>f(\hat{\mathbf{y}}) \le f(\mathbf{y})</math>.<ref name="review" />