Trasformazione vincoli n-ari in vincoli binari
La trasformazione dei vincoli n-ari in vincoli binari è un processo di razionalizzazione dei problemi CSP. Ogni vincolo n-ario può essere trasformato in una serie di vincoli binari assumendo una variabile ausiliaria per ogni vincolo n-ario in relazione ( vincolo binario ) con ognuna delle variabili originarie del vincolo. Quando tutti i vincoli binari sono soddisfatti, allora anche il vincolo n-ario è soddisfatto. Ad esempio, dato un vincolo ternario A+B=C, in cui ogni variabile ha i seguenti domini:
A={0,1}
B={2,4}
C={4,5}
In questo caso sarebbe necessario calcolare tutte le combinazioni possibili tra le variabili A, B e C, per verificare quali soddisfano il vincolo A+B=C.
| A | B | C | A+B=C |
| 0 | 2 | 4 | false |
| 0 | 2 | 5 | false |
| 0 | 4 | 4 | true |
| 0 | 4 | 5 | false |
| 1 | 2 | 4 | false |
| 1 | 2 | 5 | false |
| 1 | 4 | 4 | false |
| 1 | 4 | 5 | true |
Il problema può anche essere risolto in modo diverso, trasformando il vincolo ternario in tre vincoli binari introducendo una quarta variabile X che assume un vincolo con ognuna delle variabili originarie ( A, B, C )
A-X
B-X
C-X
Relazione binaria tra A e X. Prendiamo la prima relazione A-X, il dominio di A è { 0, 1 } mentre il dominio di X è dato dalla combinazione dei valori possibili delle restanti variabili B e C. La variabile X è pari a X=C-B.
| C | B | X |
| 4 | 2 | 2 |
| 4 | 4 | 0 |
| 5 | 2 | 3 |
| 5 | 4 | 1 |
Possiamo vedere che in due casi il vincolo binario A-X è soddisfatto, quando X è uguale a zero e quando è uguale a uno ( X=0 e X=1). Queste due situazioni coincidono ad altrettante coppie di valori delle variabili B e C. Ciò consente di ridurre il dominio in cui ricercare la soluzione all'interno delle restanti variabili.
C=4, B=4, A=0
C=5, B=4, A=1
Relazione binaria tra B e X. Passiamo ora ad analizzare la seconda relazione (B-X) tra la variabile X e la seconda variabile originaria B. Utilizziamo una variabile di comodo per calcolare la combinazione di valori tra le restanti variabili A e C. La variabile X è pari a X=C-A.
| A | C | X |
| 0 | 4 | 4 |
| 0 | 5 | 5 |
| 1 | 4 | 3 |
| 1 | 5 | 4 |
Il dominio originario della variabile B è {2,4}. Sappiamo però che soltanto il valore 4 soddisfa la relazione tra la variabile A e la variabile X. Possiamo quindi ridurre il dominio della variabile B da { 2, 4 } a { 4 }. La relazione tra la variabile B e la variabile X è soddisfatta in cue situazioni ( X=5 e X=4 ). Queste due situazioni coincidono ad altrettante coppie di variabili A e C. Ciò consente di ridurre ulteriormente il dominio in cui ricercare la soluzione.
A=0, C=4, B=4
A=1, C=5, B=4
Relazione binaria tra C e X. Infine, verifichiamo quando è soddisfatta l'ultima relazione (C-X) tra la variabile originaria C e la variabile ausiliaria X. La variabile X è pari a X=A+B.
| A | B | X |
| 0 | 2 | 2 |
| 0 | 4 | 4 |
| 1 | 2 | 3 |
| 1 | 4 | 5 |
Sappiamo che il dominio della variabile C è {4,5} e che il dominio della variabile B è ridotto soltanto al dominio { 4 } dalla relazione A-X. Le combinazioni con i valori B indicati in rosso sono eliminati dall'elaborazione. La relazione (C-X) viene soddisfatta in due situazioni ( X=4 e X=5 ) quando le coppie di variabili A e B assumono i seguenti valori:
A=0, B=4, C=4
A=1, B=4, C=5
Soluzione finale. In conclusione, sommando tutte le situazioni in cui i vincoli binari sono tutti soddisfatti è possibile ottenere l'insieme delle situazioni in cui il vincolo ternario originario è soddisfatto.
C=4, B=4, A=0 -- relazione A-X
C=5, B=4, A=1 -- relazione A-X
A=0, C=4, B=4 -- relazione B-X
A=1, C=5, B=4 -- relazione B-X
A=0, B=4, C=4 -- relazione C-X
A=1, B=4, C=5 -- relazione C-X
Eliminando le ridondanze di valori otteniamo le situazioni in cui il vincolo ternario è soddisfatto.
A=0, B=4, C=4
A=1, B=4, C=5
Conclusione. Abbiamo così dimostrato di poter trattare un vincolo ternario come un insieme di vincoli binari. In generale, qualsiasi vincolo n-ario può essere trasformato in un insieme di vincoli binari utilizzando una variabile ausiliaria X che si trova in relazione binaria con ciascuna variabile originaria del vincolo n-ario.
Algoritmi CSP. Se ogni vincolo n-ario può essere trasformato in vincolo binario e ogni vincolo unario può essere eliminato modificando il dominio delle variabili ( eliminazione vincoli unari ), allora qualsiasi problema CSP può essere trasformato in un insieme di vincoli binari. Per questa ragione gli algoritmi CSP sono predisposti per lavorare esclusivamente su vincoli binari.
