Le principali classi di algoritmi visti finora:
Algoritmi ibridi: usando tecniche miste
È un algoritmo ibrido che sfrutta il fatto che inferenza (arc consistency) è completa su problemi il cui grafo primale è aciclico
Cycle cutset di un grafo=insieme di nodi che rendono il grafo aciclico se rimossi dal grafo
Idea: usare backtracking sulle variabili di un cutset, poi inferenza sull'albero risultante
Dato il problema binario con questo grafo:
Se si eliminano x ed y, il problema diventa aciclico:
Come usare questa proprietà?
Sia data una valutazione fissa delle variabili del cutset
Esempio: x=1,y=2
Si può vedere come un nuovo problema in cui il dominio di x sia composto solo da 1 e il dominio di y sia composto solo da 2
Questo problema si può trasformare duplicando la variabile x:
È la stessa cosa: dove prima c'era una variabile che poteva valere solo 1, c'è ancora una variabile con dominio 2
Perchè in generale non si può fare: se una variabile ha dominio {1,2} e la si sdoppia, una potrebbe valere 1 mentre l'altra vale 2
Per le variabili che hanno un solo valore possibile, non può succedere
Ogni variabile che ha un solo valore possibile si può sdoppiare
I vincoli fra variabili fissate già si sa se sono violati oppure no
Se ne esiste uno violato, il problema è inconsistente
Altrimenti, basta risolvere il problema senza di essi:
Quello che resta è un albero (non contiene cicli)
Si può risolvere con arc consistency
Le variabili con valore fissato si possono moltiplicare a piacere
In particolare, si può creare una variabile separata per ogni vincolo di quella originale
Se è data una valutazione delle variabili di un cutset:
Allora il risultato di questa moltiplicazione è un problema aciclico
Si indentifica un cutset del problema
Si fa ricerca sul cutset (backtracking oppure local search
Ogni volta che si ha una valutazione totale di tutte le variabili del cutset:
Propagazione è efficiente (polinomiale) mentre backtracking in generale è esponenziale
Il cutset deve però essere piccolo, altrimenti backtracking ci mette troppo tempo
D'altra parte, trovare un cutset piccolo può richiedere tempo
Sono due fattori contrastanti
Invece di usare arc consistency, si usa directional path consistency
Invece di un cutset, basta un insieme di nodi che riduce il problema ad avere larghezza indotta ≤ 2
Questo si può generalizzare a larghezza indotta costante
Invece di un cutset prima di iniziare il backtracking, si verifica ad ogni passo
In altre parole, ogni volta che si valuta una nuova variabile, si va a vedere se l'insieme delle variabili valutate è un cutset
In questo caso, si passa a propagazione invece di continuare con backtracking
Un altro algoritmo ibrido si vedrà quando si faranno le decomposizioni ad albero