Ricerca con inferenza in avanti

La ricerca con inferenza in avanti è una inferenza dell'algoritmo di ricerca nei problemi CSP ( Constraint Satisfaction Problem ). La ricerca con inferenza in avanti integra la fase di inferenza ( ottimizzazione dei vincoli ) all'interno della fase di ricerca vera e propria ( ricerca CSP ). In genere, un problema CSP è affrontato in due fasi sequenziali e distinte. In una prima fase preliminare l'algoritmo verifica la consistenza dei vincoli, riducendo i valori nel dominio delle variabili e lo spazio di ricerca. In una seconda fase, infine, l'algoritmo enumera le combinazioni di valori legali delle variabili con le operazioni di assegnamento, al fine di individuare le combinazioni dei valori in grado di risolvere il problema. Nel caso della ricerca con inferenza in avanti, la fase preliminare ( inferenza ) non viene elaborata. I vincoli sono verificati ( verifica in avanti ) direttamente sui valori correnti delle variabili ( nodi ) durante la fase di ricerca.

Ad esempio, nel seguente problema a tre variabili ( A, B, C ), l'algoritmo deve ricercare una combinazione di valori tale da ottenere una somma eguale a cinque. Le variabili del problema hanno i seguenti domini: A { 5, 3, 1 }, B { 1, 2, 3 } e C { 5, 3, 1 }. Seguendo la logica dell'euristica fail-first, nelle operazioni di assegnamento dei valori l'ordine delle variabili è determinato a partire da quella meno vincolante ( C ) ed è pari a C⇒B⇒A. Per arrivare alla prima soluzione disponibile, l'algoritmo ( senza inferenza ) impiega 9 operazioni di assegnamento. L'albero di ricerca è il seguente.

L'efficienza della ricerca può essere migliorata elaborando l'inferenza in avanti dopo ogni assegnamento, al fine di verificare la consistenza d'arco con il nodo successivo o la consistenza di cammino sui successivi nodi in profondità. Utilizzando l'inferenza in avanti, l'algoritmo impiega soltanto 4 operazioni di assegnamento prima di giungere alla soluzione. L'albero di ricerca è il seguente:

• Assegnamento C=5. Dopo l'operazione di assegnamento C=5, l'algoritmo elabora la consistenza d'arco con il nodo B. Essendo C=5, è possibile ottenere una somma A+B+C pari a 5 soltanto nel caso in cui A=0 e B=0. Sappiamo però che l'estremo minimo del dominio di B è 1, quindi il dominio della variabile B si trasforma da { 1, 2, 3 } a un insieme vuoto { }. L'algoritmo interrompe la ricerca sulla ramificazione ( potatura logica ) per fare un passo indietro ( backtracking ) e passare alla ramificazione successiva.
• Assegnamento C=3. Dopo l'operazione di assegnamento C=3, l'algoritmo elabora la consistenza d'arco con il nodo C. Essendo C=3, è possibile ottenere una somma A+B+C=5 soltanto nel caso in cui B<=2. Il dominio delle variabile B viene ridotto da { 1, 2, 3 } a { 1, 2 }.
• Assegnamento C=3 e B=1. Dopo l'operazione di assegnamento B=1, l'algoritmo elabora la consistenza d'arco con il nodo A. Essendo C=3 e B=1, è possibile ottenere una somma A+B+C=5 soltanto nel caso in cui A=1. Il dominio della variabile A viene ridotto da { 5, 3, 1 } a { 1 }. L'algoritmo ha così trovato una combinazione di valori ( C=3; B=1; A=1 ) la cui somma è pari a 5.

Elimina l'ottimizzazione dei vincoli preliminare. La ricerca con inferenza in avanti è particolarmente utile quando l'algoritmo deve trovare la prima soluzione disponibile nel più breve tempo possibile. In tali casi, la fase preliminare di inferenza completa su tutti i vincoli del problema potrebbe incidere pesantemente sul tempo di esecuzione dell'algoritmo. L'elaborazione delle inferenze sul singolo valore corrente di una variabile ( nodo ) consente, invece, di concentrare l'analisi dei vincoli contingenti della singola ramificazione dell'albero di ricerca, volta per volta, ed elimina l'operazione preliminare di ottimizzazione dei vincoli su tutto l'albero di ricerca.

Consistenza di cammino ( k-consistenza ). La ricerca con inferenza in avanti è particolarmente utile quando si analizza la consistenza di cammino ( k-consistenza ). L'analisi della k-consistenza su tutto l'albero di ricerca ( ottimizzazione dei vincoli preliminare ) è molto dispendiosa in termini di risorse ( memoria ) e di tempo di esecuzione dell'algoritmo. La k-consistenza è, invece, molto meno dispendiosa quando viene calcolata soltanto su un singolo ramo dell'albero di ricerca, a partire dal nodo corrente. Ovviamente, la k-consistenza con inferenza in avanti conviene soltanto quando l'algoritmo deve trovare la prima soluzione utile di un problema. Non conviene, invece, quando l'algoritmo deve comunque analizzare l'intero albero di ricerca per trovare la soluzione migliore o l'insieme di tutte le soluzioni di un problema.