Soddisfacimento di vincoli distribuiti

Il soddisfacimento di vincoli distribuiti è una tecnica di risoluzione dei problemi CSP, basata sulla suddivisione del problema in una collezione di sottoproblemi collegati. Ogni sottoproblema è caratterizzato da un sottoinsieme delle variabili e dei vincoli del problema. I sottoproblemi possono anche non essere indipendenti tra loro. Ad esempio, una variabile potrebbe essere utilizzata contemporaneamente in più sottoproblemi, creando dei vincoli tra i sottoproblemi ( sottoproblemi dipendenti o sottoproblemi vincolati ). Il modus operandi dell'algoritmo di soddisfacimento dei vincoli distribuiti è il seguente:

• Ricerca soluzione in ogni sottoproblema. L'algoritmo ricerca le soluzioni in ogni singolo sottoinsieme di variabili vincolate ( sottoproblema ).
• Verifica dei vincoli tra sottoproblemi. Per ogni soluzione di un sottoproblema S viene verificata la sua compatibilità con le soluzioni di tutti gli altri S-1 sottoproblemi.

Il problema viene risolto quando l'algoritmo individua un'assegnazioni di valori tale da risolvere tutti i sottoproblemi e di soddisfare tutti i vincoli tra i sottoproblemi.

Dato un problema composto da 5 variabili ( a, b, c, d, e ) tra loro vincolate, soltanto la variabile c è vincolata con tutte le altre variabili del problema. Le restanti variabili hanno vincoli binari soltanto con un sottoinsieme di variabili. Ad esempio, la variabile (a) ha due vincoli di disuguaglianza con le variabili (b) e (c), ecc. Il problema può essere rappresentato nel seguente grafo dei vincoli. I valori a lato identificano i domini delle variabili ossia i valori che le stesse possono assumere.

Il problema può essere scomposto in due sottoproblemi ( SP₁, SP₂ ) tramite una scomposizione funzionale vincolata. Nel sottoproblema SP₁ sono raggruppati i vincoli tra le variabili ( a, b, c ) e nel sottoproblema SP₂ sono raggruppati i vincoli tra le variabili ( c, d, e ). Si può facilmente notare che i due sottoproblemi non sono indipendenti poiché la variabile (c) compare in entrambi.

L'algoritmo risolve i due sottoproblemi separatamente giungendo alle soluzioni dei due sottoproblemi. Ad esempio, l'insieme delle soluzioni del problema SP₁ è composto dalle assegnazioni ( a=3, b=1, c=2 e a=3, b=2, c=1 ). L'insieme delle soluzioni del sottoproblema SP₂ è composto dalle assegnazioni ( c=1, d=3, e=2 ).

A questo punto l'algoritmo analizza la compatibilità delle soluzioni individuate per ciascun sottoproblema nei confronti del vincolo tra i sottoproblemi. Nel nostro esempio, il vincolo tra SP₁ e SP₂ è l'uguaglianza della variabile (c). Una delle soluzioni del sottoproblema SP₁ non rispetta il vincolo di uguaglianza (c=2) mentre l'altra lo rispetta (c=1). Combinando le due soluzioni compatibili dei sottoproblemi, otteniamo la soluzione del problema generale.

In conclusione, il soddisfacimento dei vincoli distribuiti consente di utilizzare la scomposizione funzionale di un problema complesso in più sottoinsiemi, più semplici da risolvere, verificando in seconda istanza la compatibilità delle soluzioni. A differenza della scomposizione funzionale semplice, nel soddisfacimento dei vincoli distribuiti i due sottoproblemi non sono indipendenti ( sottoproblemi dipendenti o vincolati ). Ciò nonostante, l'analisi del vincolo in comune tra i due sottoinsiemi di variabili consente di risolvere il problema.

Sottoproblemi vincolati. La soluzione di tutti i sottoproblemi dipendenti/vincolati ( es. SP₁, SP₂ ) è una condizione necessaria ma non sufficiente per risolvere il problema generale. Nell'algoritmo di soddisfacimento dei vincoli è necessario che siano soddisfatti anche tutti i vincoli tra i sottoproblemi. Soltanto nel caso di sottoproblemi indipendenti la soluzione di tutti i sottoproblemi garantisce anche la soluzione del problema generale.