Euristica dinamica
L'euristica dinamica è una procedura di analisi reiterata e di indicizzazione dei dati durante l'esecuzione di un algoritmo di ricerca. Nella fase di assegnazione dei valori alle variabili ( model checking ) un algoritmo di ricerca esplora l'albero logico fino a giungere alla prima soluzione valida del problema o della formula logica. Le euristiche consentono di velocizzare il processo di analisi basandosi su regole pratiche, dettate dall'esperienza o dal buon senso. Esistono diverse tipologie di euristiche ( euristica del simbolo puro, euristica della clausola unitaria, ecc. ). Generalmente le euristiche sono elaborate prima dell'esecuzione dell'algoritmo di ricerca, al fine di semplificare la formula originaria.
Questa tecnica potrebbe, tuttavia, non essere efficiente. Ad esempio, l'euristica della clausola unitaria suggerisce di assegnare i valori prima alle variabili delle clausole unitarie della formula. Nella seguente formula non è però presente alcuna clausola unitaria.
( A ∨ B ) ∧ ( ¬A ∨ C ) ∧ ( ¬B ∨ ¬C )
In questo caso, l'applicazione preliminare dell'euristica della clausola unitaria non produce alcun effetto sull'ordine di assegnamento delle variabili (A⇒B⇒C) dell'algoritmo di ricerca che, in assenza di altre indicazioni, segue l'ordine alfabetico dei nomi delle variabili. Nella seguente figura è rappresentato l'albero logico del processo di ricerca.
Nel primo ciclo di esecuzione l'algoritmo assegna il valore booleano true alla variabile A. La prima clausola ( A ∨ B ) diventa vera e si annulla. Nella seconda clausola il letterale ¬A assume il valore "false" e, pertanto, può essere eliminato. In questa fase intermedia dell'elaborazione la formula logica cambia e non è più quella iniziale, l'eliminazione della clausola e del letterale modifica la formula in ( C ) ∧ ( ¬B ∨ ¬C ). Come si può notare nella nuova formula logica si è creata una clausola unitaria (C) ma l'algoritmo, non sapendolo, procede con l'ordine di assegnamento iniziale delle variabili (A⇒B⇒C). L'algoritmo assegna il valore true alla variabile B, poi i valori true e false, alla variabile C, giungendo a due punti morti ( passo 4 e 5 ). A questo punto l'algoritmo torna indietro ( backtracking ) e assegna il valore false alla variabile B ( passo 6 ) e, successivamente, il valore true alla variabile C, giungendo alla prima soluzione valida del problema ( passo 7 ). Complessivamente l'algoritmo di ricerca ha compiuto 7 operazioni prima di giungere alla soluzione. Il percorso di ricerca potrebbe essere più corto elaborando le euristiche in modo dinamico. Ad esempio, dopo il passo 1 la formula logica diventa ( C ) ∧ ( ¬B ∨ ¬C ), applicando dinamicamente l'euristica della clausola unitaria dopo ogni passo l'algoritmo potrebbe individuare la clausola unitaria (C) nella formula intermedia e, quindi, modificare l'ordine di assegnamento delle variabili da (A⇒B⇒C) a (C⇒B). Così facendo l'algoritmo giungerebbe alla prima soluzione valida del problema in soli 5 passi.
Le euristiche dinamiche applicano le regole di ottimizzazione durante il processo di assegnamento delle variabili rendendo più efficiente il processo di ricerca. In un generico diagramma a blocchi di un algoritmo di ricerca la funzione euristica viene richiamata nella fase di feed-back.
Indicizzazione. Per applicare le euristiche dinamiche è necessario memorizzare l'evoluzione della formula logica durante l'elaborazione, in modo tale da mantenere in memoria le varie formule logiche che vengono a crearsi durante l'esplorazione dell'albero logico. Questa funzione è conosciuta come indicizzazione.
Complessità temporale. L'elaborazione delle euristiche dinamiche comporta un maggior consumo di risorse ( memoria, processore, ecc. ) e un maggiore tempo di elaborazione per ogni ciclo di elaborazione. Non sempre il risultato finale è efficiente. L'utilità delle euristiche dinamiche è direttamente correlata al numero delle variabili e dei valori che possono assumere, ed è inversamente correlata all'insieme delle euristiche da verificare. Quando il problema è caratterizzato da poche variabili e da pochi valori, l'elaborazione dinamica delle euristiche potrebbe generare forti ritardi temporali e inefficienze in conseguenza dell'esecuzione delle euristiche. È preferibile utilizzare le euristiche dinamiche quando il problema è caratterizzato da una quantità elevata di variabili e/o da un campo di associazione dei valori molto ampio.
