Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 10:32, 29 dic 2018

Versione delle 10:46, 29 dic 2018

Riga 30:

L'algoritmo può essere diviso in tre parti principali: la costruzione del grafo, il calcolo di un taglio minimo, e l'assegnazione dei valori risultanti alle variabili.

Nella costruzione del grafo, l'insieme dei nodi <math>V</math> è costituito dai nodi sorgente <math>s</math> e pozzo <math>t</math>, più una coppia di nodi <math>p</math> e <math>p'</math> per ogni variabile. Dopo aver trasformato la funzione obiettivo <math>f</math> in [[graph cut#Forma normale|forma normale]], per ogni termine <math>w</math> si aggiunge una coppia di verticiarchi nel grafo:

* ad ogni termine <math>w_p(0)</math> corrispondono igli verticiarchi <math>p \rightarrow t</math> e <math>s \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_p(0)</math>;

* ad ogni termine <math>w_p(1)</math> corrispondono igli verticiarchi <math>s \rightarrow p</math> e <math>p' \rightarrow t</math>, con pesi <math>\frac{1}{2} w_p(1)</math>;

* ad ogni termine <math>w_{pq}(0, 1)</math> corrispondono igli verticiarchi <math>p \rightarrow q</math> e <math>q' \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_{pq}(0, 1)</math>;

* ad ogni termine <math>w_{pq}(1, 0)</math> corrispondono igli verticiarchi <math>q \rightarrow p</math> e <math>p' \rightarrow q'</math>, con pesi <math>\frac{1}{2} w_{pq}(1, 0)</math>;

* ad ogni termine <math>w_{pq}(0, 0)</math> corrispondono igli verticiarchi <math>p \rightarrow q'</math> e <math>q \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_{pq}(0, 0)</math>;

* ad ogni termine <math>w_{pq}(1, 1)</math> corrispondono igli verticiarchi <math>q' \rightarrow p</math> e <math>p' \rightarrow q</math>, con pesi <math>\frac{1}{2} w_{pq}(1, 1)</math>.

Il taglio minimo del grafo può essere calcolato con un [[teorema del flusso massimo e taglio minimo|algoritmo di flusso massimo]]. In generale, il grafo può ammettere più tagli minimi, che corrispondono a diverse soluzioni parziali, tuttavia è possibile costruire un taglio che lasci il minor numero possibile di variabili indefinite. Una volta calcolato il taglio minimo, ogni variabile riceve un valore dipendente dalla posizione dei rispettivi nodi <math>p</math> e <math>p'</math>: se <math>p</math> appartiene alla componente connessa contenente la sorgente e <math>p'</math> appartiene alla componente contenente il pozzo, il valore di <math>p</math> sarà 0, viceversa se <math>p</math> appartiene alla componente contenente il pozzo e <math>p'</math> a quella contenente la sorgente, il valore di <math>p</math> sarà 1. Se entrambi i nodi <math>p</math> e <math>p'</math> appartengono alla stessa componente connessa, il valore sarà indefinito.<ref name="rother" />