Algoritmo nogood
L'algoritmo nogood è un algoritmo di ricerca CSP che utilizza una tecnica di apprendimento dei vincoli durante l'esecuzione. L'apprendimento dei vincoli è una tecnica di ottimizzazione computazionale degli algoritmi di ricerca CSP. La tecnica consiste in un processo di apprendimento dalle situazioni di criticità nel corso dell'elaborazione dati Quando l'algoritmo incontra una situazione conflittuale o contraddittoria nell'assegnazione delle variabili, ossia una situazione in conflitto con i vincoli del problema CSP, l'algoritmo registra i dati in un insieme dei conflitti ( cd insieme no-good ). Nel corso dell'esecuzione l'algoritmo analizza l'insieme delle situazioni conflittuali al fine di individuarne gli elementi in comune e di aggiungere nuovi vincoli al problema ( apprendimento dei vincoli ). In questo modo l'algoritmo evita di elaborare continuamente altre situazioni fallimentari dello stesso tipo che possono verificarsi in altre sotto-ramificazioni dell'albero di ricerca Nel seguente esempio è rappresentato un albero di ricerca CSP con apprendimento dei vincoli.
Nel problema sono presenti quattro variabili binarie ( A, B, C, D ) con un dominio di valori ( 0, 1 ). L'algoritmo di ricerca CSP elabora tutti i valori delle variabili ( assegnazione ) sulla base dei vincoli iniziali del problema. Tuttavia, durante l'esecuzione possono emergere nuove situazioni conflittuali. Ad esempio, quando le variabili B e C sono entrambe uguale a zero ( 0 ), l'assegnazione di qualsiasi valore alla variabile D genera un conflitto con i vincoli del problema.
B=0, C=0 ⇒ D = { }
B=0, C=1 ⇒ D = { }
Questa situazione conflittuale non è inizialmente prevista tra i vincoli del problema. L'algoritmo riconosce il nuovo conflitto ( NC ) tra il sottoinsieme di variabili ( B, C, D ), lo aggiunge all'insieme no-good e procede all'elaborazione delle altre sotto-ramificazioni ( da sinistra verso destra ). Le successive assegnazioni non sono conflittuali ma, in ogni caso, non raggiungono l'obiettivo della ricerca ( NF ). Non essendo conflittuali, l'algoritmo non le aggiunge all'insieme no-good. Quando l'algoritmo si trova dinnanzi alla medesima assegnazione no-good dei valori, li riconosce ed evita di elaborarli di nuovo. Le combinazioni di valori no-good del sottoinsieme di variabili ( B, C, D ) sono conflittuali indipendentemente dal valore assunto dalle altre variabili del problema ( A ). È quindi possibile evitare di elaborarle nuovamente con gli altri valori della variabile A. L'algoritmo no-good salta l'assegnazione della sottoramificazione e passa alla successiva. Nel nostro esempio l'algoritmo trova la soluzione al problema nell'ultima sottoramificazione dell'albero di ricerca, quella più a destra ( F ). Ciò che però è importante evidenziare è il fatto che l'algoritmo abbia imparato dall'esperienza durante il processo di ricerca. In conclusione, la tecnica di apprendimento dei vincoli dell'algoritmo no-good aumenta l'efficienza dell'algoritmo tramite l'aggiunta di nuovi vincoli, non inizialmente presenti tra i vincoli di origine del problema CSP, che possono verificarsi e ripetersi durante il processo di assegnazione e di ricerca.
Ordine di assegnazione delle variabili. L'efficacia dell'algoritmo nogood e della tecnica di apprendimento dei vincoli è influenzata dall'ordine di assegnazione dei valori alle variabili. Ad esempio, nell'esempio precedente l'ordine di assegnazione è A->B->C->D, Se, invece, l'ordinefosse B->C->D->A l'algoritmo individuerebbe le combinazioni B->C->D "no good" ( 0->0->0 e 0->0->1 ) soltanto una volta nel corso dell'elaborazione. Una volta potata la sotto-ramificazione, questa non si presenta nuovamente. In quest'ultimo caso l'algoritmo di ricerca no-good si comporta in modo simile a una semplice ricerca di vincoli in avanti ( ricerca con inferenza in avanti ).
Differenza tra i nodi terminali NC e NF. È opportuno sottolineare la differenza tra i nodi terminali ( NC ) e i nodi terminali ( NF ). In entrambi i casi l'algoritmo non raggiunge la soluzione al problema. Le cause sono però diverse. Nel caso dei nodi terminali ( NC ) la combinazione di valori assegnati al sottoinsieme di variabili ( B, C, D ) determina una situazione conflittuale tra le stesse. In qualsiasi caso si presenti questa combinazione, indipendentemente dal valore delle altre variabili del problema ( A ), si presenta un conflitto con i vincoli. Nel caso dei nodi terminali ( NF ), invece, la combinazione di valori assegnati al sottoinsieme di variabili non provoca alcun conflitto, pur non risolvendo il problema. Si tratta soltanto di un fallimento dell'assegnazione. È quindi possibile riutilizzare la stessa combinazione di valori del sottoinsieme ( B, C, D ) anche nei successivi processi di assegnazione, modificando il valore delle altre variabili non comprese nel sottoinsieme ( A ).
