Ordine assegnamento valori variabili

L'ordine di assegnamento dei valori alle variabili è una caratteristica degli algoritmi di ricerca e uno dei principali fattori del problema di assegnamento. Nel processo di ricerca, l'algoritmo assegna dei valori alle variabili al fine di verificare il raggiungimento dell'obiettivo ( soluzione ). Il problema di assegnamento consiste in una procedura sequenziale di assegnamento dei valori alle variabili del problema. Ad esempio, una variabile x può assumere un vettore di valori { v₁, v₂, ..., v_n }. L'ordine di assegnamento degli n valori può incidere fortemente sull'efficienza, sulla complessità e sul tempo di esecuzione dell'algoritmo 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 { 2, 3 }, B { 1, 4 }, C { 1, 3 }.

L'algoritmo di ricerca cerca una combinazione di valori delle variabili in grado di restituire come risultato una somma A+B+C pari a cinque ( A+B+C=5 ). Nell'assegnamento dei valori l'algoritmo segue l'ordine di presentazione degli stessi nel dominio delle variabili. Per quanto riguarda la variabile A { 2, 3 }, l'algoritmo assegna prima il valore 2 e poi il valore 3, per quanto riguarda la variabile B { 1, 4 } assegna prima il valore 1 e poi il valore 4, ecc. L'algoritmo impiega otto operazioni di assegnamento prima di giungere al risultato ( soluzione ). Tuttavia, se l'ordine dei valori della variabile A fosse { 3, 2 } anziché { 2, 3 }, l'algoritmo di ricerca impiegherebbe soltanto tre operazioni di assegnamento per raggiungere l'obiettivo.

In conclusione, l'ordine dei valori in un problema di assegnamento influisce sulla complessità, sull'efficienza e sul tempo di esecuzione del processo di ricerca ( algoritmo ). È sempre consigliabile, se possibile, individuare un'inferenza in grado di razionalizzare l'ordine dei valori delle variabili nel processo di assegnamento.

Euristica fail-last. L'euristica fail-last è una tecnica euristica che consente di ridurre lo spazio di ricerca dell'algoritmo, anteponendo nel processo di assegnamento i valori con maggiore probabilità di successo ( minore probabilità di insuccesso ). La tecnica euristica fail-last consente di aumentare le possibilità di trovare più rapidamente una soluzione al problema, di ridurre lo spazio di ricerca e il tempo di esecuzione dell'algoritmo.