Eliminazione per bucket

È un algoritmo risolutivo completo

Si tratta di eliminare dal problema una variabile per volta

Quando si resta con una sola variabile, risolverlo è facile

Eliminazione di una variabile

Sia S l'insieme delle soluzioni di un problema

Se una variabile x non interessa, si può eliminare x da tutte le soluzioni

Ogni soluzione è una valutazione a tutte le variabili; si può però eliminare la valutazione di x da essa

Eliminazione di una variabile da un problema

Si tratta di modificare il problema (non l'insieme delle soluzioni) in modo che la variabile sparisca

Condizione: le soluzioni devono restare uguali, a parte la variabile scomparsa

Eliminazione variabile: come?

Si può sempre fare

Qualche volta la dimensione del problema aumenta

Soluzione errata: elimino x e tutti i vincoli che contengono questa variabile

Perchè non funziona?

Eliminazione variabile, modo sbagliato

Esempio ovvio: x<y con dominio {0,1} per tutte e due le variabili

Se elimino x e il vincolo, ogni valore di y è ammesso

Invece, l'unica soluzione è x=0,y=1

Eliminando x, dove restare y=1 come unica soluzione

Eliminazione variabile, modo corretto

Il modo più ovvio è quello di creare un nuovo vincolo fra tutte le altre variabili

Per eliminare x, si aggiunge un vincolo C(X\{x},R) su tutte le altre variabili

Questo vincolo è soddisfatto da tutte la valutazioni che si possono estendere ad x in modo da formare una soluzione del problema

Semplificazione

Invece di creare un vincolo su tutte le altre variabili, si crea solo sulle variabili che sono in un vincolo con x

Motivo: le altre variabili sono influenzate solo attraverso queste

Bucket elimination

Il principio è quello di eliminare una variabile per volta

Quando resta una sola variabile, il problema si risolve facilmente

Per ottenere una soluzione: data una soluzione a i variabili, si considerano in ordine tutti i valori possibili della variabile i+1

Bucket elimination

In pratica, si procede in questo modo

Si decide un ordine sulle variabili x₁,...,x_n

Si partizionano i vincoli in n classi

La classe i contiene tutti i vincoli che hanno x_i come variabile con indice più alto

Questo ordine permette di semplificare l'algoritmo di eliminazione

Eliminazione di un bucket

Si parte da x_n, e si elimina una variabile per volta

L'eliminazione di una variabile x_i comporta l'eliminazione di tutti i vincoli del bucket i

Al posto di questi vincoli, si mette la loro combinazione sulle loro variabili che non sono x_i

Bucket elimination, un passo per volta

All'inizio, si elimina il bucket di x_n, e al suo posto si mette un unico vincolo sulle variabili che sono in uno o più vincoli con x_n

Questo vincolo viene messo nel bucket giusto

Quello che resta è un problema sulle variabili x₁,...,x_n-1

Notare che questo è un problema equivalente, a parte la variabile eliminata

Ogni soluzione di questo problema si può estendere con un valore di x_n per formare una soluzione del problema originario

Si ripete per x_n-1 ecc.

Cose essenziali

L'algoritmo funziona perchè:

• l'eliminazione di un vincolo porta ad un problema equivalente ma con una variabile in meno
• una soluzione del problema equivalente si può sempre estendere a quello originario
• quando si resta con una variabile, il problema è facile da risolvere