Euristica fail-last
L'euristica fail-last è una tecnica euristica di ricerca CSP in cui i valori nei domini delle variabili sono ordinati in base alle probabilità di successo. I valori con maggiore probabilità di raggiungere la soluzione sono assegnati prima degli altri. L'euristica fail last è applicata negli algoritmi di ricerca per ridurre lo spazio 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 giungere alla combinazione di valori delle variabili ( A, B, C ) in grado di restituire una somma A+B+C pari a 5. Le variabili seguono l'ordine C⇒B⇒A sulla base dell'euristica MRV ( fail first ). L'algoritmo impiega 9 operazioni di assegnamento di valori alle variabili, prima di giungere alla soluzione del problema. L'albero di ricerca è il seguente.
Utilizzando un'euristica fail-last sull'ordinamento dei valori all'interno dei domini delle variabili è possibile migliorare l'efficienza dell'algoritmo In questo caso, i valori più bassi hanno maggiore probabilità di successo ( minore probabilità di insuccesso ). Mantenendo lo stesso ordine di assegnamento delle variabili C⇒B⇒A, proviamo a ordinare i valori nei domini dal più basso al più alto. Con l'euristica fail-last l'algoritmo impiega soltanto 3 operazioni di assegnamento, prima di giungere alla soluzione del problema. L'albero di ricerca è il seguente:
In conclusione, l'euristica fail-last consente di elaborare prima i valori migliori nell'ordine di assegnamento valori alle variabili, aumentando la probabilità di giungere prima alla soluzione del problema e, quindi, l'efficienza dell'algoritmo di ricerca. L'euristica fail-last analizzata nell'esempio è conosciuta anche come euristica del valore meno vincolante.
L'euristica fail-last migliora l'efficienza nelle ricerche in cui l'algoritmo deve trovare la prima soluzione accettabile a un problema nel minore tempo possibile. L'euristica fail-last è, invece, inutile nelle ricerche complete ossia in quelle ricerche in cui è importante trovare il migliore risultato. In quest'ultimo caso, per risolvere il problema l'algoritmo deve comunque elaborare l'intero albero di ricerca.
L'efficienza della ricerca può essere ulteriormente aumentata combinando l'euristica fail-last con l'euristica fail-first. Ad esempio, l'euristica fail-first consente di ottenere un ordine di assegnamento delle variabili dalla peggiore alla migliore, ottenendo una rapida potatura logica dell'albero di ricerca. Contemporaneamente, l'euristica fail-last può migliorare l'efficienza della ricerca nelle operazioni di assegnamento dei valori legali, dal valore migliore a quello peggiore, al fine di aumentare le probabilità di successo.
