11. Ragionamento con vincoli PT. 2

In questa seconda parte relativa al ragionamento con vincoli, introduciamo ulteriori concetti rispetto all'articolo precedente. Il primo è senza dubbio un ulteriore metodo per semplificare la rete dei vincoli, ovvero la suddivisione del dominio, denominata anche come analisi dei casi. L'idea alla base di questo metodo è quella di suddividere il problema in un numero di casi disgiunti e risolvere ogni caso separatamente. L'insieme di tutte le soluzioni al problema iniziale è l'unione delle soluzioni a ciascun caso.

Considerando un semplice caso, supponiamo di avere una variabile binaria X con un dominio { t, f }. Le soluzioni avranno X=t o X=f, quindi per semplificare il problema possiamo dividere il dominio principale in due sotto domini, risolvere il problema in questi due. In questo modo stiamo effettuando una riduzione.

Ci sono diversi metodi per dividere un dominio composto da diversi elementi. I due più semplici consistono del dividere il dominio in più sottodomini, uno per ogni caso, mentre il secondo consiste nel dividere il dominio in due sottodomini disgiunti e non vuoti. Il primo metodo porta più risultati rispetto al secondo, ma allo stesso tempo il secondo consente una potatura del dominio con meno passaggi.

Risolvere ricorsivamente i casi utilizzando la suddivisione del dominio, riconoscendo quando non c'è soluzione basata sulle assegnazioni, è equivalente all'algoritmo di ricerca visto nel precedente articolo. Un modo per renderlo più efficiente, consiste nell'utilizzare la consistenza dell'arco all'interno di un algoritmo di ricerca.

Per semplificare la risoluzione di un CSP, si potrebbe semplificare la rete prima di ogni fase della suddivisione del dominio. Questo algoritmo non richiede la consistenza dell'arco per ripartire da zero dopo la divisione del dominio. La suddivisione del dominio costituisce uno spazio di ricerca da cui è possibile utilizzare uno qualsiasi dei metodi di ricerca visti in precedenza. Tuttavia, poiché interessa solo la soluzione e non il percorso e poiché lo spazio di ricerca è finito, per questi problemi viene spesso utilizzata la ricerca in profondità.

Eliminare le variabili

A differenza della consistenza dell'arco in cui viene semplificata la rete rimuovendo i valori delle variabili, vi è un metodo complementare attraverso il quale si semplifica la rete rimuovendo le variabili ed è definito eliminazione delle variabili (VE). L'idea alla base di questo metodo consiste nell'eliminare una variabile X e costruire un nuovo vincolo, sulle variabili rimanenti, che riflette gli effetti della variabile X sulle altre.

Vengono sostituiti tutti i vincoli che comportano X, formando una rete ridotta che non coinvolge quest'ultimo. Il nuovo vincolo è costruito in modo tale che qualsiasi soluzione al CSP ridotto possa essere estesa a una soluzione del CSP che contiene X. Possiamo definire uno pseudocodice di questo algoritmo che riceve in input un insieme Vs contenente tutte le variabili e un insieme CS contenente i vincoli su Vs. In output restituisce le assegnazioni delle variabili coerenti.

Il caso base della ricorsione si verifica quando rimane solo una variabile. In questo caso ( riga 2 ), esiste una soluzione se e solo se ci sono righe nel join delle relazioni finali. Si noti che queste relazioni sono tutte relazioni su una singola variabile, e quindi sono gli insiemi di valori legali per questa variabile. L'unione di queste relazioni è l'intersezione di questi insiemi.

Durante la ricorsione una variabile X è selezionata per l'eliminazione alla riga 4. La variabile selezionata non influisce sulla correttezza dell'algoritmo, ma può influire sull'efficienza. Per eliminare la variabile X, l'algoritmo propaga l'effetto alle variabili correlate. Questo è possibile farlo unendo tutte le relazioni in cui X è coinvolto e quindi proietta X dalla relazione risultante.

Se si vuole ottenere solo una soluzione si può restituire un elemento del join. Indipendentemente dall'elemento restituito, è garantito che quell'elemento farà parte di una soluzione. L'efficienza dell'algoritmo VE dipende dall'ordine in cui le variabili vengono selezionate. Essa può essere determinata considerando la struttura grafica.

In generale, VE è efficiente quando la rete di vincoli è sparsa. Il numero di variabili nella relazione più grande restituita per un particolare ordinamento di variabili è chiamato larghezza dell'albero del grafico per quell'ordinamento di variabili. La larghezza dell'albero di un grafico è la larghezza minima dell'albero per qualsiasi ordinamento. La complessità di VE è esponenziale nella larghezza dell'albero e lineare nel numero di variabili.

Trovare un ordinamento di eliminazione che si traduca nella larghezza dell'albero più piccola è NP-difficile. Tuttavia, esistono alcune buone euristiche. I due più comuni sono:

• min-factor: in ogni fase si seleziona la variabile che risulta nella relazione la più piccola
• carenza minima o riempimento minimo: in ogni fase si seleziona la variabile che aggiunge il minor numero di archi alla rete di vincoli rimanente.

Ricerca locale

Molti spazi sono troppo grandi per una ricerca sistematica e forse sono anche infiniti. In un tempo ragionevole, la ricerca sistematica non sarà riuscita a considerare uno spazio sufficiente per fornire risultati significativi. I metodi non cercano sistematicamente l'intero spazio di ricerca, ma sono progettati per trovare rapidamente soluzioni in media. Non garantiscono che verrà trovata una soluzione anche se ne esiste una, e quindi non sono in grado di dimostrare che non esiste alcuna soluzione.

I metodi di ricerca locale iniziano con un'assegnazione totale di un valore a ciascuna variabile e cercano di migliorare questa assegnazione in modo iterativo eseguendo passaggi di miglioramento, eseguendo passaggi casuali o ricominciando con un'altra assegnazione totale. Sono stati definiti diversi algoritmi di ricerca, definiamo lo pseudocodice di un algoritmo di ricerca generico per un CSP. Questo accetta in input un insieme di variabili Vs, una funzione dom tale che dom(X) è il dominio della variabile X e un insieme di vincoli Cs da soddisfare. Come output restituisce un'assegnazione totale che soddisfa i vincoli. Infine utilizza un array A di valori indicizzati dalle variabili in Vs.

Il vettore A specifica l'assegnamento di un valore a ogni variabile. Il primo loop assegna un valore casuale a ogni variabile, la prima volta che questo procedimento viene eseguito, prende il nome di random initializtion, inizializzazione casuale. Le altre iterate prendono il nome di try. Gli assegnamenti alle righe 2 e 3 prendono il nome di random restart. Il loop alla riga 4 esegue una ricerca locale o un cammino. In questo processo viene considerato un insieme di possibili successori per l'assegnamento totale di A.

Il criterio di stop è dato dalla funzione stop_walk() per decidere quando interrompere la ricerca locale corrente ed eseguire un riavvio casuale, ricominciando con una nuova assegnazione. L'arresto di questo algoritmo non è garantito. In particolare, se la condizione di terminazione è falsa, continua all'infinito se non c'è soluzione e, anche se c'è una soluzione, è possibile rimanere intrappolati in qualche regione dello spazio di ricerca. Un algoritmo è completo se garantisce di trovare una risposta ogni volta che ce n'è una. Questo algoritmo può essere completo o incompleto, a seconda della selezione e del criterio di arresto.

Miglioramento iterativo

Il miglioramento iterativo è un algoritmo di ricerca locale che seleziona un successore dell'assegnazione corrente che migliora maggiormente alcune funzioni di valutazione. Se ci sono diversi possibili successori che migliorano maggiormente la funzione di valutazione, ne viene scelto uno a caso. Quando l'obiettivo è minimizzare, questo algoritmo è chiamato discesa avida. Quando l'obiettivo è massimizzare una funzione, si parla di arrampicata in collina o ascesa avida.

Il miglioramento iterativo richiede un modo per valutare ogni assegnazione totale. Per i problemi di soddisfazione dei vincoli, una funzione di valutazione comune è il numero di vincoli violati. Un vincolo violato è chiamato conflitto. Poiché la funzione di valutazione è il numero di conflitti, una soluzione è un'assegnazione totale con una valutazione pari a zero. A volte questa funzione di valutazione viene affinata ponderando alcuni vincoli più di altri.

Un ottimo locale è un'assegnazione tale che nessun possibile successore migliora la funzione di valutazione. Questo è anche chiamato minimo locale in discesa avida, o massimo locale in salita avida. Un ottimo globale è un'assegnazione che ha il miglior valore tra tutte le assegnazioni. Tutti gli ottimi globali sono ottimi locali, ma possono esserci molti ottimi locali che non sono ottimi globali. Se la funzione euristica è il numero di conflitti, un CSP soddisfacibile ha un ottimo globale con un valore euristico pari a 0 e un CPS insoddisfacente ha un ottimo globale con un valore superiore a 0. Se la ricerca raggiunge un minimo locale con un valore superiore a 0 , non sai se si tratta di un minimo globale (il che implica che il CSP non è soddisfacibile) o meno.

Il miglioramento iterativo considera la migliore assegnazione del successore anche se è uguale o addirittura peggiore dell'assegnazione corrente. Ciò significa che se ci sono due o più assegnazioni che sono possibili successori l'una dell'altra e sono tutte ottimali locali, ma non globali, continuerà a spostarsi tra queste assegnazioni e non raggiungerà mai un ottimo globale. Pertanto, questo algoritmo non è completo.

Algoritmi randomizzati

La casualità può essere utilizzata per sfuggire ai minimi locali che non sono minimi globali in due modi principali:

• riavvio casuale, in cui i valori per tutte le variabili vengono scelti a caso. Ciò consente alla ricerca di iniziare da una parte completamente diversa dello spazio di ricerca.
• passeggiata casuale, in cui vengono eseguiti alcuni passaggi casuali interlacciati con i passaggi di ottimizzazione. Con la discesa avida, questo processo consente passaggi verso l'alto che possono consentire alla passeggiata casuale di sfuggire a un minimo locale che non è un minimo globale.

Una passeggiata casuale è una mossa casuale locale, mentre un riavvio casuale è una mossa casuale globale. Per problemi che coinvolgono un gran numero di variabili, un riavvio casuale può essere piuttosto costoso. Un mix di miglior miglioramento iterativo con mosse casuali è un'istanza di una classe di algoritmi nota come ricerca locale stocastica.