Insieme di taglio condizionato

L'insieme di taglio condizionato è una metodologia di analisi e di risoluzione di un problema complesso, basata sull'analisi di un sottoinsieme di variabili ( insieme di taglio ) e sulla verifica di consistenza delle soluzioni nei domini delle altre variabili del problema. L'insieme di taglio condizionato ( cutset conditioning ) è una metodologia di risoluzione dei problemi utilizzata nel problem solving e nei sistemi CSP. Il modus operandi di un algoritmo costruito sulla logica dell'insieme di taglio condizionata è il seguente:

• Insieme di taglio. Si isolano ("tagliano") una parte delle variabili del problema da tutte le altre. L'algoritmo ricerca tutte le problema.
• Verifica della consistenza. Sulla base delle soluzioni individuate al sottoinsieme di variabili, si attua una propagazione dei vincoli per ridurre il dominio delle altre variabili del problema.

La metodologia consente di ridurre sensibilmente la complessità del problema, trasformando il grafo dei vincoli in una struttura ad albero più semplificata. Sulla base delle soluzioni individate in un sottoinsieme di variabili, la soluzione esiste soltanto se tutte le altre variabili conservano un dominio non nullo e se soddisfano gli altri vincoli del problema.

Dato un problema a 5 variabili ( a, b, c, d, e ) tra loro vincolate, ogni variabile è sottoposta a un vincolo di disuguaglianza con almeno altre due variabili. Il problema può essere rappresentato tramite un grafo dei vincoli nel seguente modo:

Per risolvere il problema, l'algoritmo individua il sottoinsieme di variabili ( a, c ). È opportuno sottolineare che l'algoritmo avrebbe potuto scegliere anche un'altra combinazione di variabili o, anche, una sola variabile. Una volta individuato l'insieme di taglio, analizza tutte le possibili soluzioni del sottoproblema di taglio. Sulla base dei vincoli binari tra le variabili (a) e (c) e dei relativi domini di valori delle variabili, le soluzioni possibili sono le seguenti:

a=1; c=2
a=2; c=1
a=3; c=1
a=3; c=2

Per ciascuna soluzione del sottoproblema di taglio, l'algoritmo propaga la consistenza del vincolo sui domini delle altre variabili del problema:

a=1; c=2 => b={}, d={1,3}, e={1} - senza soluzione
a=2; c=1 => b={}, d={2,3}, e={2} - senza soluzione
a=3; c=1 => b={2}, d={2,3}, e={2}
a=3; c=2 => b={1}, d={1,3}, e={1}

Nei primi due casi la propagazione dei vincoli sui domini delle altre variabili svuota del tutto il dominio della variabile (b). Ciò significa che le releative soluzioni all'insieme di taglio non risolvono il problema generale. Gli ultimi due casi, invece, consentono a ciascuna variabile di mantenere almeno un valore di variazione nel proprio dominio. Tra queste ultime due è possibile ricercare la soluzione al problema generale. Non siamo però ancora giunti a determinare la soluzione. Come ultimo passo è necessario verificare la consistenza dei vincoli tra tutte le variabili al di fuori dell'insieme di taglio. Dal grafo dei vincoli iniziale possiamo eliminare l'insieme di taglio ( a, c ) e i relativi vincoli, concentrando l'analisi sulle variabili e sui vincoli restanti.

Il grafo dei vincoli è molto più semplice rispetto a quello iniziale. La variabile (b) non ha vincoli con le altre due ed è isolata. Soltanto le variabili (d) ed (e) conservano un vincolo di disuguaglianza. L'analisi consente di eliminare le assegnazioni di valori che violano i vincoli binari tra le variabili.

a=3; c=1 => b={2}, d={2}, e={2} - non consistente
a=3; c=1 => b={2}, d={1}, e={2}
a=3; c=2 => b={1}, d={1}, e={1} - non consistente
a=3; c=2 => b={1}, d={3}, e={1}

Ad esempio, nel primo e nel terzo caso le variabili (d) ed (e) hanno il medesimo valore, violando il vincolo di disuguaglianza che le lega. Nel secondo e nel quarto caso, invece, tutti i vincoli sono rispettate. Abbiamo così trovato le soluzioni del problema generale.

a=3; c=1 => b={2}, d={1}, e={2} - soluzione del problema
a=3; c=2 => b={1}, d={3}, e={1} - soluzione del problema

La tecnica dell'insieme di taglio condizionato riduce la complessità del problema e, di conseguenza, il tempo di elaborazione e lo spazio di memoria necessario per risolvere il problema. Quanto più è piccolo ( semplice ) l'insieme di taglio, tanto più veloce è il processo di analisi e di risoluzione del problema.

Individuazione insieme di taglio. L'individuazione dell'insieme di taglio più piccolo non è sempre un'operazione facile. Per individuare l'insieme di taglio più piccolo si ricorre, spesso, alle tecniche euristiche.