Euristica fail-first
L'euristica fail-first è una tecnica euristica di ricerca CSP in cui le variabili del problema sono ordinate in funzione della probabilità di insuccesso. Secondo l'euristica fail-first, in un problema di assegnamento dei valori, le variabili con maggiore probabilità di insuccesso devono essere elaborate prima delle altre. Questa logica potrebbe sembrare apparentemente irrazionale. In realtà, l'euristica fail-first aumenta notevolmente le possibilità di potatura logica dell'albero di ricerca. L'eliminazione ( potatura ) dei nodi fallimentari nella parte superiore dell'albero di ricerca, consente di escludere dalle operazioni di assegnamento un maggiore numero di ramificazioni sottostanti, riducendo lo spazio di ricerca e il tempo di esecuzione dell'algoritmo di ricerca. Ad esempio, nel seguente sistema a tre variabili, i valori legali della variabile A sono { 5, 3, 1 }, della variabile B sono { 1, 2, 3 } e della variabile C { 5, 3 }.
L'obiettivo dell'algoritmo è di trovare una combinazione di valori delle variabili ( A, B, C ) tale da ottenere una somma A+B+C pari a 5. Le variabili seguono l'ordine A⇒B⇒C. L'algoritmo impiega 18 operazioni di assegnamento dei valori alle variabili, prima di giungere alla soluzione del problema. L'albero di ricerca è il seguente.
Adottando un'euristica fail-last è possibile migliorare l'efficienza della ricerca. Ad esempio, la variabile C ha soltanto due valori legali { 5, 3 } mentre le altre variabili ne hanno tre. La variabile C ha, quindi, una maggiore probabilità di giungere prima al fallimento. Questa euristica è conosciuta con il nome Minimum Remaining Value ( euristica MRV ). Proviamo a modificare l'ordine delle variabili dalla peggiore ( C ) alla migliore. In questo caso, l'algoritmo esegue le operazioni di assegnamento seguendo l'ordine delle variabili C⇒B⇒A. Questa semplice modifica all'ordine di assegnamento delle variabili consente all'algoritmo di ricerca di giungere alla soluzione del problema in soli 9 operazioni di assegnamento. L'albero di ricerca è il seguente.
In conclusione, l'euristica fail fist consente di elaborare prima le variabili con maggiore probabilità di insuccesso, al fine di ottenere una potatura logica delle sotto-ramificazioni e di ridurre lo spazio di ricerca. Ciò consente di migliorare l'efficienza dell'algoritmo di ricerca.
L'euristica fail-first migliora l'efficienza dell'algoritmo soltanto quando quest'ultimo deve trovare una soluzione al problema, la prima disponibile e nel minore tempo possibile. E', invece, del tutto inutile nelle ricerche complete, dove l'algoritmo deve comunque scandagliare l'intero albero di ricerca ( completezza ) per trovare l'insieme delle soluzioni o la soluzione migliore.
Ordine di assegnamento dei valori. L'efficienza della ricerca può essere ulteriormente migliorata combinando l'euristica fail-first con altre euristiche. Ad esempio, l'euristica fail-first sull'ordinamento delle variabili in un processo di assegnamento ( ordine assegnamento variabili ), può essere efficientemente combinata con un'euristica fail-last sull'ordinamento dei valori delle variabili ( ordine assegnamento valori ).