Quadratic pseudo-Boolean optimisation: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
forma normale |
→Note: fox |
||
Riga 55:
<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 \} = 0</math> per ogni variabile <math>p</math>;
# <math>\min \{ w_{pq}^{0j}, w_{pq}^{1j} \} = 0</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}}):
| |||