Euristica MRV
L'euristica MRV è una tecnica di selezione delle variabili in una ricerca CSP. L'ordine di assegnamento delle variabili influisce sensibilmente sull'efficienza della ricerca. Tuttavia, non è sempre possibile conoscere a priori il migliore ordine delle variabili da adottare nella ricerca CSP . L'euristica MRV consente di adottare una selezione razionale, partendo dal presupposto che le variabili con minor numero di valori rimanenti da analizzare nel proprio dominio siano quelle con maggiore probabilità di giungere prima al fallimento ( euristica fail-first ), evitando così di dover assegnare i valori alle altre variabili ( potatura logica ). L'acronimo MRV significa Minimum Remaining Values. Ad esempio, il seguente problema CSP è composto da tre variabili A, B e C. Le variabili A e B hanno un dominio composto da tre valori legali mentre la variabile B ha un dominio composto soltanto da due valori legali { 5, 3 }.
L'algoritmo di ricerca CSP ha l'obiettivo di trovare una combinazione di valori delle variabili ( A, B, C ) tale da restituire una somma A+B+C uguale a 5. Seguendo l'ordine di assegnazione delle variabili A⇒B⇒C, l'algoritmo di ricerca esegue 18 operazioni di assegnazione prima di giungere alla soluzione del problema. L'albero di ricerca è il seguente:
Utilizzando l'euristica MRV l'ordine di assegnazione diventa C⇒B⇒A, in quanto la variabile C ha minor numero di valori legali nel suo dominio { 5, 3 } rispetto alle variabili A { 5, 3, 1 } e B { 1, 2, 3 }. L'ordine C⇒B⇒A dell'euristica MRV consente di giungere al risultato finale in sole 9 operazioni di assegnazione. L'albero di ricerca è il seguente:
I risultati ottenuti con l'euristica MRV variano a seconda dei dati del problema. Tuttavia, il fatto di utilizzare una variabile con minor numero di valori legali consente di aumentare la probabilità di giungere al fallimento e di ridurre, da un punto di vista empirico, la ramificazione dell'albero di ricerca. Quanto più in alto in un albero di ricerca si verifica il fallimento, tanti più nodi delle ramificazioni sottostanti sono potati. Le variabili con meno valori legali, secondo l'euristica MRV, hanno maggiore probabilità di giungere prima al fallimento rispetto a quelle con molti valori legali.
L'euristica MRV è inefficace quando il dominio delle variabili è composto dallo stesso numero di valori. Ad esempio, se la variabile A avesse un dominio composto da tre valori { 5, 3, 9 } anziché due { 5, 3 }, l'euristica MRV non potrebbe suggerire nessun ordinamento delle variabili. In tali casi si ricorre ad altre euristiche come, ad esempio, l'euristica della variabile vincolante.
