Quadratic pseudo-Boolean optimisation: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
wl, fix |
forma normale |
||
Riga 31:
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
* ad ogni termine <math>w_p(0)</math> corrispondono gli archi <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 gli archi <math>s \rightarrow p</math> e <math>p' \rightarrow t</math>, con pesi <math>\frac{1}{2} w_p(1)</math>;
Riga 54:
<ref name="billionnet">{{cita|Billionnet e Jaumard|pp. 161-163|billionnet}}.</ref>
<ref name="rother">{{cita|Rother et al.|pp. 1-8|rother}}.</ref>
<ref name="normal form">La rappresentazione di una funzione pseudo-booleana tramite coefficienti <math>\mathbf{w} = (w_0, w_1, \dots, w_{nn})</math> non è unica, e se due vettori di coefficienti <math>\mathbf{w}</math> e <math>\mathbf{w}'</math> possono rappresentare la stessa funzione allora <math>\mathbf{w}'</math> è detta una riparametrizzazione di <math>\mathbf{w}</math> e viceversa. In alcune costruzioni è utile assicurare che la funzione abbia una forma particolare, detta forma normale, che è sempre definita per ogni funzione e non è unica. Una funzione <math>f</math> è detta in forma normale se le due seguenti condizioni sono soddisfatte ({{cita|Kolmogorov e Rother|pp. 1274-1279|review}}):
# <math>\min{w_p^0, w_p^1}</math> per ogni variabile <math>p</math>;
# <math>\min{w_{pq}^{0j}, w_{pq}^{1j}}</math> per ogni <math>(p, q) \in E</math> e per ogni <math>j \in \{0, 1\}</math>.
Data una funzione arbitraria <math>f</math>, è sempre possibile determinare una sua riparametrizzazione in forma normale tramite un algoritmo in due fasi ({{cita|Kolmogorov e Rother|pp. 1274-1279|review}}):
# fintanto che esistono degli indici <math>(p, q) \in E</math> e <math>j \in \{0, 1\}</math> che violano la seconda condizione di normalità, si eseguono le sostituzioni
#* <math>w_{pq}^{0j}</math> con <math>w_{pq}^{0j} - a</math>
#* <math>w_{pq}^{1j}</math> con <math>w_{pq}^{1j} - a</math>
#* <math>w_q^j</math> con <math>w_q^j + a</math>
#: dove <math>a = \min{w_{pq}^{0j}, w_{pq}^{1j}}</math>;
# per ogni <math>p = 1, \dots, n</math>, si eseguono le sostituzioni
#* <math>w_0</math> con <math>w_0 + a</math>
#* <math>w_p^0</math> con <math>w_p^0 - a</math>
#* <math>w_p^1</math> con <math>w_p^1 - a</math>
#: dove <math>a = \min{w_{pq}^{0j}, w_{pq}^{1j}}</math>.
</ref>
</references>
| |||