Euristica di grado
L'euristica di grado è un'euristica utilizzata negli algoritmi del calcolo proposizionale per determinare l'ordine di selezione delle variabili in un'operazione di ricerca. Secondo l'euristica di grado, l'algoritmo deve analizzare prima le variabili più vincolanti ( euristica delle variabili vincolanti ), ossia quelle che hanno un maggior numero di relazioni ( vincoli ) con le altre variabili del problema. L'euristica di grado è utilizzata nella verifica della soddisfacibilità di un problema di logica proposizionale o CSP. Ad esempio, la seguente formula logica in forma CNF ( forma normale congiuntiva ) è composta da tre clausole e da quattro variabili letterali.
( A ∨ B ) ∧ ( ¬B ∨ ¬C ) ∧ ( ¬B ∨ C ∨ ¬D )
Un algoritmo di ricerca segue un processo di assegnazione dei valori secondo un ordine alfabetico delle variabili. Nella seguente rappresentazione è mostrato il processo di ricerca. L'algoritmo impiega otto passi (n=8) prima di giungere alla prima soluzione valida.
L'euristica di grado consente di migliorare l'algoritmo di ricerca. Nella formula dell'esempio la variabile con più relazioni con le altre è la variabile B, in quanto compare in tutte le clausole, seguita dalla variabile C e, infine, dalle variabili A e D ( ordine delle variabili ). Secondo l'euristica un algoritmo di ricerca dovrebbe fissare l'ordine di assegnazione dei valori nel seguente ordine B⇒C⇒A⇒D. In genere in un processo di ricerca viene assegnato prima il valore "true" e poi il valore "false". Si tratta però di una scelta arbitraria e, come tale, non è detto che sia la migliore. Ad esempio, nell'esempio precedente la variabile B è presente due volte in forma negata (¬B) e una volta in forma positiva (B). È quindi consigliabile anteporre l'assegnazione "false" per questa variabile ( ordine dei valori ). Seguendo questa euristica l'ordine di assegnazione delle variabili e dei valori booleani è il seguente: ¬B⇒C⇒A⇒¬D. La rappresentazione grafica del processo di ricerca è il seguente:
L'algoritmo impiega soltanto tre passi ( n=3 ) per giungere alla prima soluzione del problema. L'utilità dell'euristica di grado delle variabili e dei valori è particolarmente evidente. L'euristica di grado migliora l'efficienza dell'algoritmo.
- Algoritmo DPLL. L'euristica di grado è utilizzata dall'algoritmo DPLL per semplificare la formula logica prima di analizzare la sua soddisfacibilità logica. L'euristica rende particolarmente più efficiente l'algoritmo di ricerca.
