Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 21:51, 16 mar 2022

Versione delle 17:41, 31 mag 2024

Riga 13:

:<math> w_{pq}(0, 0) + w_{pq}(1, 1) \le w_{pq}(0, 1) + w_{pq}(1, 0) </math>

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" />

Riga 44:

== Termini di ordine superiore ==

L'ottimizzazione di funzioni pseudo-booleane di ordine superiore, ovvero contenenti termini dipendenti da tre o più variabili, è in generale un problema difficile. È sempre possibile ridurre in tempo polinomiale una [[funzione di ordine superiore]] a una funzione quadratica equivalente rispetto al problema di ottimizzazione (problema noto come ''higher-order [[cricca (teoria dei grafi)|clique]] reduction'', HOCR), e il risultato di tale riduzione può essere ottimizzato con QPBO. Metodi generali per la riduzione di funzioni arbitrarie sono basati su opportune tecniche di sostituzione di sotto-espressioni e in generale richiedono l'introduzione di variabili ausiliarie.<ref name="fix" /> In pratica, per la maggior parte dei termini di ordine superiore è possibile calcolare in maniera esatta una riduzione senza aggiunta di variabili ausiliarie, risultando in un problema di ottimizzazione più semplice; per i restanti termini irriducibili è possibile calcolare una riduzione esatta con metodi più generali, aggiungendo variabili ausiliarie, oppure eseguendo una riduzione approssimata senza aggiungere nuove variabili.<ref name="elc" />

== Note ==