Propagazione estremi
La propagazione degli estremi è una tecnica di ottimizzazione di un problema rispetto a un vincolo tra due variabili. In presenza di un vincolo binario tra due variabili, un algoritmo dovrebbe verificare le combinazioni di assegnamento per escludere quelle non consistenti rispetto al vincolo. Questa operazione preliminare riduce il dominio delle variabili ai soli valori consistenti. Tuttavia, l'analisi completa delle combinazioni potrebbe rivelarsi molto complessa e lunga. Ad esempio, nel seguente problema le variabili A e B sono legate tra loro da un vincolo A+B=25.
Il dominio della variabile A è { 0,...,20 } ( 21 valori ) mentre quello della variabile B è { 0,...,10 } ( 11 valori ). Volendo analizzare tutte le possibilità di assegnamento delle due variabili è necessario effettuare 221 combinazioni ( 21x11 ) in altrettanti cicli di elaborazione.
Essendo gli insiemi composti da valori continui, è possibile ottimizzare l'operazione analizzando soltanto gli estremi dei domini delle variabili ( consistenza estremi ) rispetto al vincolo binario. La propagazione degli estremi consente di ottimizzare il dominio delle variabili in due operazioni.
- L'estremo superiore di A è 20 mentre l'estremo inferiore di B è 0. Per essere consistente rispetto al vincolo A+B=25 l'estremo della variabile B deve essere almeno pari a 5. Possiamo quindi riscrivere il dominio di B da { 0,...,10 } a { 5,...,10 }. Il dominio della variabile B si riduce da 11 a 6 valori.
- L'estremo superiore di B è 10 mentre l'estremo inferiore di A è 0. Per essere consistente rispetto al vincolo A+B=25 l'estremo della variabile A deve essere almeno pari a 15. Possiamo quindi riscrivere il dominio di A da { 0,...,20 } a { 15,...,20 }. Il dominio della variabile A si riduce da 21 a 6 valori.
Dopo l'analisi di consistenza degli estremi i domini delle variabili sono estremi-consistenti. In sole due operazioni di confronto lo spazio di ricerca del problema è stato ridotto dalle 221 combinazioni iniziali (21x11) a 36 combinazioni estremo-consistenti (6x6).
Efficienza. La propagazione degli estremi ottiene il medesimo risultato dell'analisi completa dell'assegnamento delle variabili con un costo risorse notevolmente più basso. L'assegnamento completo richiede 221 cicli macchina per verificare la consistenza di tutte le combinazioni di valori delle variabili. La propagazione degli estremi ottiene il medesimo risultato in soli 2 cicli macchina.
