Ordine assegnamento variabili
L'odine di assegnamento delle variabili è un aspetto del problema di assegnamento degli algoritmi di ricerca. Per trovare una soluzione a un sistema di vincoli ed equazioni, l'algoritmo di ricerca deve assegnare dei valori alle variabili, al fine di verificare il raggiungimento o meno dell'obiettivo ( soluzione ). Il problema di assegnamento consiste in una procedura sequenziale di assegnamento dei valori alle variabili del problema. Ad esempio, date due variabili ( x1, x2 ), potremmo decidere di assegnare prima il valore alla variabile x1. Nulla però ci vieta di assegnare prima il valore alla variabile x2. Questa scelta, apparentemente sterile, può avere effetti anche molto importanti sulla complessità temporale dell'algoritmo di ricerca. In particolar modo negli algoritmi in cui è necessario trovare rapidamente una soluzione, la prima disponibile nel minore tempo possibile e non la migliore in assoluto. L'ordine delle variabili nel processo di assegnamento può incidere sensibilmente sotto il profilo dell'efficienza e del tempo di ricerca. Ad esempio, nel seguente albero di ricerca viene mostrato il cammino della ricerca in profondità in un sistema composto da tre variabili ( A, B, C ).
L'algoritmo cerca una combinazione dei valori delle variabili in grado di restituire una somma A+B+C pari a cinque ( A+B+C=5 ). L'ordinamento delle variabili nel processo di assegnamento è A⇒B⇒C, ossia prima viene assegnato il valore alla variabile A, poi alla variabile B e, infine, alla variabile C. Dopo otto operazioni di assegnamento l'algoritmo giunge alla soluzione. Tuttavia, se l'ordinamento delle variabili fosse B⇒C⇒A, l'algoritmo di ricerca impiegherebbe soltanto quattro operazioni di assegnamento.
In conclusione, l'ordine delle variabili in un problema di assegnamento influisce sul tempo di esecuzione dell'algoritmo di ricerca, sulla complessità e sull'efficienza della ricerca. È quindi sempre consigliabile verificare l'eventuale esistenza di inferenze, in grado di razionalizzare l'ordinamento delle variabili nel processo di assegnamento. L'ordine delle variabili in un problema di assegnamento è particolarmente impotante nei modelli matematici della ricerca operativa e nella risoluzione dei problemi CSP ( Constraint Satisfaction Problem ).
Euristica fail-first. L'euristica fail-first è una tecnica euristica che consente di ridurre lo spazio di ricerca dell'algoritmo, anteponendo nel processo di assegnamento le variabili con maggiore probabilità di insuccesso. Ciò consente di ottenere una potatura logica dell'albero di ricerca fin dai nodi più in alto, eliminando dalle operazioni di assegnamento tutte le ramificazioni sottostanti.
