Euristica valore meno vincolante
L'euristica del valore meno vincolante è una tecnica euristica di ottimizzazione del processo di assegnamento dei valori in una ricerca CSP tramite un particolare ordinamento dei valori delle variabili . In base a questa euristica, l'algoritmo deve elaborare ( assegnamento valore ) prima i valori meno vincolanti e poi tutti gli altri. A partire da un determinato ordine di assegnazione delle variabili, l'euristica effettua un ordinamento dei valori contenuti all'interno del dominio delle variabili. L'ordine dei valori è in funzione del vincolo tra il valore stesso e i valori potenziali delle altre variabili. A parità di condizioni, il valore meno vincolante ha minore probabilità di insuccesso poiché lascia maggiore campo di variazione ( range ) di valori alle altre variabili del problema. L'euristica del valore meno vincolante appartiene alla categoria delle euristiche fail-last poiché predilige l'ordine dei valori dal migliore ( minore probabilità di fallimento ) al peggiore. Ad esempio, nel seguente sistema a tre variabili e due vincoli, i valori legali della variabile A sono { 5, 3, 1 }, della variabile B sono { 1, 2, 3 } e della variabile C { 5, 3 }. Il grafo dei vincoli del problema è il seguente.
L'algoritmo ricerca una combinazione dei valori delle variabili ( A, B, C ) tale da restituire una somma A+B+C uguale a 5. L'ordine di assegnamento delle variabili è predeterminato da un'altra euristica ( euristica MRV ) ed è pari a C⇒B⇒A. Per giungere alla prima soluzione disponibile, l'algoritmo impiega 9 operazioni di assegnamento. L'albero di ricerca è il seguente.
L'efficienza dell'algoritmo di ricerca è migliorabile. Nel corso della ricerca l'algoritmo incontra tre fallimenti ( nodi di colore rosso ) e altrettanti passi indietro ( backtracking ). Se fossero analizzati prima i valori più bassi, ossia i valori meno vincolanti rispetto al problema, si potrebbe ridurre le probabilità di fallimento e le relative operazioni di backtracking. L'euristica del valore meno vincolante modifica l'ordine dei valori, all'interno dei dominio delle variabili, nel seguente modo: A { 1, 3, 5 }, B { 1, 2, 3 }, C { 3, 5 }. Con il nuovo ordine di assegnamento dei valori, l'algoritmo di ricerca impiega soltanto 3 operazioni di assegnamento, senza incontrare alcun fallimento ( backtracking ). L'albero di ricerca è il seguente:
In conclusione, l'euristica del valore meno vincolante altera l'ordine di assegnamento valori alle variabili, anticipando quelli in grado di avere maggiore possibilità di successo ( fail-last ). L'euristica del valore meno vincolante consente di migliorare sensibilmente l'efficienza dell'algoritmo di ricerca.
Tipo di problema. Nel nostro esempio i valori sono ordinati in ordine crescente, dal più basso al più alto, in quanto il problema da risolvere consiste nel trovare una combinazione di valori delle variabili tale da restituire una somma uguale a cinque. In altri problemi potrebbe accadere l'inverso. I valori meno vincolanti potrebbero essere quelli più alti oppure potrebbero essere individuati sulla base di funzioni specifiche di ordinamento/selezione.
Ordine di assegnamento delle variabili. L'euristica del valore meno vincolante analizza i valori delle variabili al fine di individuare l'ordine migliore dei valori nella procedura di assegnamento. Per trovare l'ordine migliore delle variabili, invece, è necessario ricorrere ad altre euristiche ( es. euristica della variabile vincolante )
Prima soluzione disponibile. L'euristica del valore meno vincolante migliora l'efficienza della ricerca quando l'algoritmo ha il compito di restituire la prima soluzione disponibile nel minore tempo possibile. Quando l'algoritmo deve trovare la migliore soluzione o tutte le soluzioni possibili, invece, l'euristica del valore meno vincolante è del tutto inutile. In quest'ultimo caso, l'algoritmo deve comunque scandagliare l'intero albero di ricerca ( completezza ) e tutte le combinazioni di valori delle variabili del problema.
