Consistenza locale

Sono condizioni relative alla consistenza di alcuni vincoli

Ogni problema di può modificare in modo che sia localmente consistente senza modificare le sue soluzioni

Node consistency

Condizione già vista

Una variabile è node consistent se ogni valore del suo dominio soddisfa tutti i vincoli unari su di essa

Formalmente, per la variabile x con dominio Dx:

∀ a ∈ Dx ∀ C=(⟨x⟩,R) . a ∈ R

Constraint propagation

Modificare il problema in modo che:

1. la consistenza locale sia verificata
2. le soluzioni del problema non cambiano

Propagazione di vincoli per la node consistency

Se una variabile non è node consistent:

Si tolgono dal dominio i valori che non soddisfano dei vincoli

Dx' = Dx \ { a | ∃ C . C=(⟨x⟩,R) and a ∉ R }

Soddisfa le due condizioni?

Condizioni per la propagazione di vincoli

1. il nuovo dominio di x ora contiene solo valori che soddisfano tutti i vincoli: gli altri li ho eliminati
2. le soluzioni non sono cambiate: tutti i valori che ho eliminati non potevano far parte di una soluzione perchè violavano dei vincoli

Arc consistency

Riguarda vincoli binari (vincoli su due variabili)

Esempio:

• variabile x con dominio {0,1,2,3}
• variabile y con dominio {1,2}
• vincolo x<y

Non ci sono vincoli unari

Quindi il problema è node consistent

Ci sono valori dei domini che posso escludere?

Valori da escludere

Nell'esempio:

• y può valere solo 1 oppure 2
• x<y

Quindi, x può valere al massimo 1

Per x=2 oppure x=3 non esiste un valore di y che soddisfi il vincolo

I valori 2 e 3 si possono eliminare dal dominio di x

Non possono essere parte di nessuna soluzione

Motivo

Analizziamo il motivo, per poter generalizzare la condizione

x=2 non fa parte di nessuna soluzione perchè:

• ogni soluzione deve soddisfare tutti i vincoli
• quindi, deve anche soddisfare il vincolo x<y
• ogni soluzione deve dare un valore ad y
• se una valutazione ha x=2, il vincolo x<y è violato per qualsiasi valore di y

Conclusione: il valore x=2 non fa parte di nessuna soluzione

Rappresentazione grafica

È diversa dal grafo primale

Si usa solo per la consistenza locale

I nodi sono i valori per le variabili

Gli archi indicano i valori ammessi dai vincoli binari

Una soluzione è un valore per ogni variabile

Soddisfare i vincoli=tutti questi valori devono essere connessi fra loro

Arc consistency, graficamente

Per x=0 ci sono i valori y=1 e y=2

Per x=1 c'è il valore y=2

Per x=2 e per x=3 non c'è un valore consistente (collegato, nel grafo) per y

Questi due valori non sono arc-consistent

Propagazione di vincoli

Dato che x=2 non fa parte di nessuna soluzione, si può eliminare 2 dal dominio di x

Anche x=3 si può eliminare per lo stesso motivo

Questi sono valori che non fanno parte di nessuna soluzione, la loro eliminazione non cambia le soluzioni del problema

Consistenza e propagazione

Generalizzazione:

• consistenza: ogni valore nel dominio di una variabile ha (almeno) un valore nel dominio dell'altra variabile tale che i due valori soddisfino il vincolo binario
  motivo: altrimenti, questo valore è inutile, dato che non fa parte di una soluzione
• propagazione: i valori che non soddisfano la condizione di sopra si possono eliminare dal dominio della prima variabile
  motivo: questi sono valori che non fanno comunque parte di una soluzione

È utile?

Eliminazione di valori

A cosa serve?

Semplifica il problema

Esempio: eliminando 2 e 3 dal dominio di x, il backtracking deve solo fare le scelte x=0 ed x=1

In generale, meno possibilità ci sono, più il problema è facile da risolvere

Arc consistency e propagazione

Arc consistency=la condizione che tutti i valori di un dominio siano utili

Propagazione=modificare il problema per rendere vera la condizione (eliminando valori dal dominio) senza modificare le soluzioni

Arc consistency, definizione formale

Sia C=(⟨x,y⟩,R) un vincolo binario

Siano Dx e Dy i domini di x ed y

La variabile x è arc-consistent rispetto al vincolo se ogni valore per x ha un corrispondente valore di y tale che i due valori soddisfano il vincolo:

∀ a ∈ Dx ∃ b &isin Dy . ⟨a,b⟩ &isin R

Propagazione, definizione formale

Consiste nella modifica del dominio di x

Elimino i valori che violano la arc consistency

Dx'=Dx \ { a | ¬∃ b ∈ Dy . ⟨a,b⟩ ∈ R }

Modifica del dominio di x per ottenere la arc consistency rispetto al vincolo C=(⟨x,y⟩,R)

Elimino i valori che comunque non potrebbero soddisfare il vincolo

Dominio vuoto

Può succedere che un dominio resta vuoto?

Esempio:

• variabile x con dominio Dx={2,3}
• variabile y con dominio Dy={0,1}
• vincolo x<y

Nessun valore di x ha un valore in Dy per cui il vincolo è soddisfatto

La propagazione svuota Dx

Dominio vuoto

Se un dominio resta vuoto, il problema non ha soluzioni

Motivo: se Dx è vuoto, la variabile x non ha valori ammessi

Una soluzione deve avere un valore per x

Se nessun valore va bene, il problema è inconsistente

Condizione sufficiente ma non necessaria

Se un dominio resta vuoto, allora il problema è inconsistente

Non vale il viceversa:

• variabili x,y,z con lo stesso dominio {0,1}
• vincoli x≠y, y≠z e z≠x

Arc consistency vale per tutte le variabili: se una variabile vale 0, l'altra può valere 1 e viceversa

Il problema è inconsistente: non si possono scegliere tre valori diversi in un dominio di due valori

Arc consistency di un problema

Finora, si è definita per una variabile e un vincolo

Si generalizza a tutto un problema

Un problema è arc-consistent se lo è per ogni variabile e ogni vincolo binario

Propagazione per un problema

La arc-consistency si può forzare su una variabile e un vincolo come visto prima

Si può forzare per un intero problema?

Se faccio propagazione per ogni variabile e ogni vincolo cosa succede?

  for v in (variabili)
    for vincolo in (vincoli su v)
      forza consistenza di v rispetto a vincolo

Funziona?

Non funziona

Questo algoritmo non funziona:

  for v in (variabili)
    for vincolo in (vincoli su v)
      forza consistenza di v rispetto a vincolo

Motivo: quando si forza la consistenza di una variabile, si può perdere la consistenza di un'altra

Vediamo perchè.

Effetti della propagazione

Esempio: l'algoritmo di prima forza la consistenza di z con tutti i suoi vincoli

Ora z è arc-consistent con tutti i suoi vincoli

Si fa lo stesso con x

Ora z potrebbe non essere più arc-consistent

Effetti della propagazione

Per forzare la consistenza su una variabile, si eliminano elementi dal suo dominio

Questo può rendere non arc-consistent altre variabili

Esempio:

• variabile x con dominio Dx={0,1,2,3}
• variabile y con dominio Dy={1,2}
• variabile z con dominio Dz={0,1,2}
• vincoli x < y e z<x

La variabile z è arc-consistente rispetto al vincolo con x

Infatti, ogni valore di z ha un valore di x superiore

Ma...

Effetti della propagazione

Come visto prima, la propagazione per x elimina dei valori:

• variabile x con dominio Dx={0,1,2,3}
• variabile y con dominio Dy={1,2}
• variabile z con dominio Dz={0,1,2}
• vincoli x < y e z<x

Questi valori sono eliminati perchè non corrispondono a valori di y

Ora però z non è più consistente con x!

Infatti, i valori z=1 e z=2 non hanno più un valore corrispondente per x

I valori corrispondenti che c'erano prima sono stati eliminati

Effetti della propagazione, in generale

Può succedere che:

• una variabile z è consistente con x
• ma la variabile x non è consistente con y
• si fa propagazione, e vengono eliminati elementi dal dominio di x
• come effetto, z non è più consistent con x

La propagazione su una variabile può rendere altre variabili non più arc consistent

Recuperare la arc-consistency

In questo caso particolare, si può recuperare la arc-consistency?

• variabile x con dominio Dx={0,1,2,3}
• variabile y con dominio Dy={1,2}
• variabile z con dominio Dz={0,1,2}
• vincoli x < y e z<x

Basta eliminare i valori 1 e 2 dal dominio di z

• variabile x con dominio Dx={0,1,2,3}
• variabile y con dominio Dy={1,2}
• variabile z con dominio Dz={0,1,2}
• vincoli x < y e z<x

Notare che ora z ha un valore singolo ammesso

Il problema è ancora più semplice

Altre inconsistenze

In questo problema, x=0 non ha un valore corrispondente in z

Viene eliminato

Dopo aver eliminato x=0, il valore y=1 non ha più un valore corrispondente per x

Viene quindi eliminato anche y=1

Il problema è risolto (ogni variabile ha un solo valore possibile)

Propagazione per arc-consistency

Possibile scenario:

• si forza la arc consistency di x
• questo rende y non più arc-consistent con x
• si fa propagazione eliminando valori di y
• questo rende z non più arc consistent con y
• si fa propagazione eliminando valori di z
• questo rende x non più arc consistent con y
• ...

Quanto può andare avanti un ciclo del genere?

Propagazione e monotonia

Ogni volta che si propagano dei vincoli, si elimina qualche valore da qualche dominio

I valori non vengono mai aggiunti

Se non viene modificato il dominio di nessuna variabile, il problema è arc-consistent e l'algoritmo termina

Alla fine si deve terminare per forza: o si svuota un dominio oppure si dimostra la inconsistenza

Numero di iterazioni

Questo algoritmo non basta:

  for v in (variabili)
    for vincolo in (vincoli su v)
      forza consistenza di v rispetto a vincolo

Va ripetutto più volte. Quante?

Numero di iterazioni

  for v in (variabili)
    for vincolo in (vincoli su v)
      forza consistenza di v rispetto a vincolo

Se un dominio si svuota, il problema è inconsistente

Se in una esecuzione del ciclo interno non si elimina nessun elemento da nessun dominio, il problema è arc consistenct

Caso peggiore: ad ogni iterazione si elimina un elemento da un dominio

Tutto questo va ripetuto al massimo m volte, dove m è la somma della dimensione di tutti i domini

Propagazione: caso peggiore

• variabile x con dominio Dx={0,1,2,3,4}
• variabile y con dominio Dy={0,1,2,3,4}
• variabile z con dominio Dz={0,1,2,3,4}
• vincoli: x<y, y≤z e z≤x

È insoddisfacibile, chiaramente

Quanto ci mette la propagazione a scoprirlo?

Numero di propagazioni

• variabile x con dominio Dx={0,1,2,3,4}
• variabile y con dominio Dy={0,1,2,3,4}
• variabile z con dominio Dz={0,1,2,3,4}
• vincoli: x<y, y≤z e z≤x

Se si fa una variabile per volta:

1. si elimina 4 da Dx
2. si elimina 4 da Dz
3. si elimina 4 da Dy
4. si elimina 3 da Dx
5. si elimina 3 da Dz
6. si elimina 3 da Dy
7. ...

Poteva anche andare peggio (ad ogni iterazione si elimina un valore in un solo dominio)

Arc consistency basata su vincoli

Per ogni vincolo, faccio verifica e propagazione per entrambe le sue due variabili

Algoritmo alternativo per il vincolo C=(⟨x,y⟩,R):

1. elimino da Dx e da Dy tutti i valori che non compaiono nella prima e seconda colonna di R, rispettivamente
2. cancello le righe di R il cui primo o secondo valore non compare in Dx e Dy, rispettivamente,
3. ripeto finchè non si modifica più R

Equivale a forzare la arc consistency di x ed y rispetto al vincolo allo stesso tempo

Infatti: dopo aver eliminato dalla colonna x di R gli elementi non stanno in Dx, quelli che restano nella seconda colonna sono tutti valori di Dy che hanno un corrispettivo in Dx

Graficamente: il passo 1 equivale ad eliminare i nodi che non hanno archi; il passo 2 equivale ad eliminare gli archi che hanno un nodo eliminato

Algoritmo di propagazione

Algoritmo banale: per ogni vincolo binario, verifico ed eventualmente forzo la arc-consistency delle sue variabili

Dato che altre variabili potrebbero essere diventate non più arc-consistent, ripeto

Ripeto tutto per un numero di volte pari alla somma della dimensione di tutti i domini

Oppure, ripeto finchè in una intera iterazione non è stato modificato nessun dominio

Algoritmo AC-3

Idea: ogni volta che forzo la arc consistency su x ed y:

• arc-consistency vale fra x ed y
• potrebbe non valere (anche se prima valeva) fra:
  • x ed un'altra variabile
  • y ed un'altra variabile

Idea: mantere l'insieme delle coppie di variabili che ''potrebbero'' attualmente non essere consistenti fra loro

Algoritmo AC-3

Mantiene un insieme di coppie di variabili che potrebbero non essere arc-consistent fra loro

• inizialmente PossInc={⟨x,y⟩|∀x,y . ∃ C=(⟨x,y⟩,R}
  (contiene tutte tutte le possibili coppie di variabili che sono nello scope di un vincolo)
• while PossInc ≠ ∅
  • prendi una coppia ⟨x,y⟩ ∈ PossInc
  • eliminala: PossInc=PossInc \ {⟨x,y⟩}
  • forza la arc consistency del vincolo fra x ed y
  • aggiungi a PossInc tutte le coppie di variabili che contengono x ed y ma non tutte e due, e che sono lo scope di un vincolo:
    PossInc=PossInc ∪ { ⟨z,x⟩ . ∃ C=(⟨z,x⟩,R) } ∪ { ⟨z,y⟩ . ∃ C=(⟨z,y⟩,R) } \ { ⟨x,y⟩ }

In questo algoritmo le coppie si considerano non ordinate

Forma normale

Da questo momento in poi, si assume la forma normale in cui i vincoli sulle stesse variabili sono unificati

Quindi, su due variabili x ed y ci può essere al più un vincolo (uno oppure nessuno)

In alcuni casi, si assume anche la forma normale in cui esiste sempre un vincolo fra due variabili (quello sempre soddisfatto se in origine non c'era)

Path consistency

Si considerano tre variabili insieme

Vantaggi:

• alcuni problemi sono arc consistent ma non sono path consistent
• per alcuni problemi, ci vuole meno a forzare la path consistency

Path consistency

Per ogni vincolo binario e variabile singolo, ogni coppia di valori che soddisfa il vincolo deve avere un valore corrispondente nella variabile

In altre parole, dato il vincolo C=(⟨x,y⟩,R) e la variabile z:

• se ⟨a,b⟩ ∈ R allora deve esistere un valore c ∈ Dz tale che:
  • x=a, z=c soddisfa il vincolo fra x e z
  • y=b, z=c soddisfa il vincolo fra y e z

Path consistency, graficamente

Arc consistency=ogni valore consistente di x si estende ad y

x=2 ed x=3 si possono estendere a un valore per y

x=1 non si può estendere ad y
Quindi arc consistency non vale

Path consistency=ogni coppia consistente di valori per x,y si estende a z

Path consistency, graficamente

Esempio:

Le coppie consistenti di valori per x,y sono ⟨1,1⟩ e ⟨2,2⟩

x=1,y=1 è consistente con z=1

x=2,y=2 non è consistente con nessun valore di z

Infatti:

• x=2 è consistente solo con z=1
• y=2 è consistente solo con z=2

Nessun singolo valore di z consistente sia con x=2 che con y=2

Path consistency, definizione formale

Sia data una coppia di variabili x,y e una terza variabile z

Siano Cxy, Cxz e Cyz i vincoli fra essi
(se un vincolo non esiste, si assume il vincolo soddisfatto da tutti i valori)

Path consistency è soddisfatta se:

• per ogni coppia di valori a ∈ Dx e b ∈ Dy
• se x=a,y=b soddisfa Cxy allora esiste c ∈ Dz tale che:
  • x=a,z=c soddisfa Cxz
  • y=b,z=c soddisfa Cyz

Cosa succede se non vale?

Esiste una coppia di valori x=a,y=b tale per cui non esiste un valore di z che soddisfa Cxz e Cyz

Ogni soluzione deve dare un valore a z e deve soddisfare Cxz e Cyz

Quindi, x=a,y=b non fa parte di nessuna soluzione

Infatti una soluzione che contiene x=a,y=b dovrebbe anche dare un valore a z e soddisfare Cxz e Cyz

Path consistency di un problema

Vale su un problema se vale per ogni coppia di variabili e ogni altra variabile

Il nome path consistency deriva dalla definizione originale, che riguarda una coppia di variabili e una sequenza di altre variabili

Nel caso in cui si assume la consistenza locale sull'intero problema e vincoli su tutte le variabili, non fa differenza

Propagazione per path consistency

Se un problema non è path consistent, allora:

Esiste una coppia di valori x=a,y=b che soddisfa il vincolo fra x ed y ma non si può estendere a z

Questa coppia di valori non fa parte di nessuna soluzione

È inutile; eliminarla semplifica il problema

Propagazione=modificare il problema in modo da ottenere la consistenza ma senza cambiare le soluzioni

Propagazione: rimozione dal dominio

Per node- e arc-consistency, si toglievano elementi dal dominio di una variabile

Si può fare anche per path consistency?

Eliminazione elementi del dominio: esempio

La coppia x=1,y=1 non ha nessun valore per z

Si potrebbe eliminare 1 dal dominio di x oppure 1 dal dominio di y

Quale?

Non si possono eliminare elementi dai domini

Questo problema non ha soluzioni che contengono x=1,y=1

Può avere soluzioni con x=1,y=2

Può anche avere soluzioni con x=2,y=1

Se esistono soluzioni del primo tipo o del secondo dipende dagli altri vincoli del problema

Quindi, x=1 non si può escludere a priori:

• ci potrebbero essere soluzioni con x=1
• le soluzioni potrebbero anche contenere tutte x=1

Lo stesso vale per y=1

Causa del problema

Non è il singolo valore x=1 a causare il problema. Infatti, potrebbero esserci soluzioni con x=1

Lo stesso per y=1

È la coppia di valori x=1,y=1 che non possono stare insieme in una soluzione

La path consistency si ottiene eliminando la coppia

Come eliminare la coppia

Definizione di path consistency:

1. se x=a,y=b soddisfano il vincolo Cxy allora:
2. esiste c ∈ Dz ...

Se per una coppia x=a,y=b il punto due non è vero, faccio in modo che il vincolo Cxy non sia soddisfatto

In questo modo, la condizione è vera perchè la coppia x=a,y=b non viene più considerata nel punto 1

Non soddisfazione vincolo

Se per x=a,y=b non esiste un valore di x ecc., allora faccio in modo che x=a,y=b non soddisfi il vincolo

Formalmente: prima ⟨a,b⟩ ∈ Rxy

Modifica: Rxy'= Rxy \ {⟨a,b⟩}

Propagazione vincoli

node- e arc-consistency

si elimina qualche valore dai domini

path-consistency

si elimina qualche coppia da vincoli binari

Equivalenza

Quando la propagazione fa Rxy'= Rxy \ {⟨a,b⟩}, non elimina soluzioni

Infatti, ⟨a,b⟩ viene eliminato solo se x=a,y=b non ha un valore per z che soddisfa i vincoli fra x e z e fra y e z

Ma questi vincoli devono essere soddisfatti da ogni soluzione

Quindi, se ⟨a,b⟩ viene eliminato è perchè non c'è nessuna soluzione che contiene questo assegnamento

Perchè eliminare la coppia?

Non esiste nessuna soluzione che contiene x=a,y=b

Ma x=a,y=b soddisfa il vincolo fra x ed y

Confronto prima e dopo:

• prima: mi accorgo che non esistono soluzioni con x=a,y=b solo quando guardo i valori di z
• dopo: i due valori x=a,y=b violano il vincolo (non mi serve guardare z)

Il fatto che x=a,y=b non fa parte di nessuna soluzione è stato reso esplicito

Path consistency e backtracking

Se l'algorimto di backtracking arriva ad una valutazione parziale che contiene x=a,y=b ma non z:

se il problema non è stato reso path consistent:

l'algoritmo non si accorge della inconsistenza e va avanti;
questo può generare un sottoalbero di ricerca anche molto grande che non contiene nessuna soluzione

se il problema è stato reso path consistent:

il vincolo fra x ed y è violato, e si fa backtracking

Vantaggi della path consistency sulla arc consistency

• ci sono problemi inconsistenti che la propagazione per path consistency dimostra inconsistenti ma quella per arc consistency no
• la propagazione può essere più veloce

Esempio di problema inconsistente

• variabili x,y,z con lo stesso dominio {0,1}
• vincoli x≠y, y≠z e z≠x

Come visto prima, questo problema è arc-consistent

Non è path-consistent (vediamo fra un momento il perchè)

Quindi, path consistency permette di dimostrare la inconsistenza, mentre arc consistency no

Esempio di problema inconsistente

Perchè è path inconsistent

La coppia x=0,y=1 non ha nessun valore corrispondente (=diverso da entrambi in questo caso) per z

Anche la coppia x=1,y=0 non ha nessun valore per z

Il vincolo x ≠ y sarebbe:

Eliminado le due coppie ⟨0,1⟩ e ⟨1,0⟩ resta una relazione vuota:

Dato che Rxy è vuoto, nessuna coppia di valori può soddisfare questo vincolo

È un vincolo sempre violato

Una soluzione dovrebbe soddisfare tutti i vincoli, anche questo

Dato che questo vincolo non si può soddisfare, il problema non ha soluzioni

Esempio di maggiore velocità

• variabile x con dominio Dx={0,1,2,3,4}
• variabile y con dominio Dy={0,1,2,3,4}
• variabile z con dominio Dz={0,1,2,3,4}
• vincoli: x<y, y≤z e z≤x

Propagazione per arc consistency richiede vari passi

Per path consistency: per ogni valore di x ed y che soddisfa x<y, non c'è nessun valore di z che sia uguale sia ad x che ad y

Path consistency dimostra la inconsistenza guardando solo una coppia di variabili

Propagazione e inconsistenza

Confronto fra i tipi di propagazione:

Propagazione per path consistency

Quando si forza la path consistency su una coppia, si potrebbe perdere su un'altra

La path consistency di x=a,y=b con z dipende dai vincoli Cxz e Cyz

Se Cxz oppure Cyz viene ristretto (si tolgono righe dalla relazione), x=a,y=b potrebbe perdere tutti i valori corrispondenti di z

Perdita di consistenza: esempio

Qui x=1,y=1 è path consistent con z

La coppia x=1,z=1 potrebbe venire eliminata quando si fa propagazione fra la x,z e un'altra variabile k

Ora x=1,y=1 non è più path consistent con z

Propagazione: coppie da riconsiderare

Se si eliminano valori dalla relazione di Cxy, dove si può perdere la path consistency?

Si può perdere la path consistency dove dipende da Cxy

Quindi, si può perdere:

• fra la coppia ⟨x,z⟩ e y
• fra la coppia ⟨y,z⟩ e x

per qualsiasi variabile z diversa da x e y

Propagazione per path consistency

Come per la arc consistency: all'inizio, tutte le coppie di variabili potrebbero avere valori non validi

Ogni volta che si modifica un vincolo Cxy, vanno considerati di nuovo tutti i vincoli Cxz e Cyz

Togliendo coppie da Cxy, possono esserci coppie in Cxz che perdono il valore corrispondente in y
(può cambiare la path consistency di Cxz)

Lo stesso per Cyz

Algoritmo di propagazione

Si mantiene l'insieme dei vincoli che potrebbero non soddisfare la path consistency

All'inizio è vuoto

Si prende un vincolo Cxy dall'insieme, e si forza la path consistency

Se vengono tolte coppie, allora ogni altro vincolo che ha x oppure y nello scope potrebbe diventare non più path consistent
lo si aggiunge all'insieme

Si termina quando l'insieme è vuoto oppure quando la relazione di un vincolo è diventata vuota

Creazione nuovi vincoli

Nella definizione di path consistency per un intero problema, si assume che esista un vincolo per ogni coppia di variabili

È il vincolo soddisfatto da tutte le possibili coppie di valori

Quando si forza la path consistency, alcune coppie di valori potrebbero venire eliminate

Questo equivale a un nuovo vincolo

Creazione vincoli: esempio

Rappresentazione grafica dei vincoli di un problema

Dominio {0,1} per tutte e tre le variabili

Rappresentazione grafica con i valori

Gli archi marcati in verde sono quelli che corrispondono al vincolo sempre soddisfatto fra x ed y

Le coppie x=1,y=2 ed x=2,y=1 non sono path consistent

Per esempio, x=2,y=1 non corrisponde allo stesso valore di z:
(in rosso i vincoli rilevanti)

Eliminazione valori=creazione vincoli

Le coppie x=1,y=2 e x=2,y=1 vanno eliminate

Ma ora il vincolo fra x ed y non ammette tutti i valori

Quello che rimane del vincolo è soddisfatto solo dalle coppie x=1,y=1 e x=2,y=2

Si è creato il vincolo x=y, quando all'inizio non c'era nessun vincolo fra x ed y

Quali vincoli si possono creare?

Se c'è un vincolo fra x e z

e un vincolo fra y e z

Allora la propagazione può creare un vincolo fra x ed y anche se prima non c'era

Creazione vincoli, graficamente

Se due nodi (variabili) sono collegate alla stessa altra variabile, allora propagazione potrebbe creare un vincolo fra loro

Non è detto che un nuovo vincolo venga aggiunto
(succede solo se ci sono coppie di valori per x,y che non hanno un valore per z

Dove non si creano vincoli

Due nodi non collegati alla stessa variabile:

Se ogni valore di x corrisponde a un valore di z,
allora ogni coppia di valori per x,y corrisponde ad un valore di z:
è quello che corrisponde al solo valore di x

Se una delle due variabili x,y non è collegata a z, path consistency=arc consistency

Se si fa prima propagazione per arc consistency, allora path consistency vale automaticamente se manca il vincolo fra una delle due variabili della coppia e l'altra

Propagazione multiple

Propagazione potrebbe creare un nuovo vincolo fra x ed y?

Propagazione multiple

Inizialmente no, perchè x ed y non sono collegate ad una stessa variabile

Pero'...

Influenza dei nuovi vincoli

z ed y sono tutte e due collegate a w

Potrebbero non essere path-consistent

Questo porta ad eliminare una coppia di valori dal vincolo virtuale fra y e w

Questo crea un vincolo reale fra y e w

Ora x ed y sono tutte e due collegate a z

Potrebbero non essere consistenti

Questo porta alla creazione di un vincolo fra di esse

Usi della consistenza locale e della propagazione

Ci sono tre usi principali:

• condizione sufficiente per dimostrare la insoddisfacibilità
• semplificazione del problema
• sottocasi trattabili

Li vediamo uno per volta

Condizione sufficiente

Se si fa propagazione e si ottiene un dominio o una relazione vuota, il problema è inconsistente

In questo caso, non c'è bisogno di fare altre operazioni

Utile:

• come tentativo preliminare: se si ottiene inconsistenza ci si ferma, altrimenti si lancia backtracking
• quando basta una condizione sufficiente (look-ahead, si vedrà in seguito

Semplificazione del problema

Propagazione per arc consistency toglie valori dal dominio

Quando backtracking assegna valori alla variabile, ci sono meno valori da assegnare, quindi meno sottoalberi da visitare

Se il dominio di una variabile contiene cinque valori, ci sono cinque sottoalberi da visitare	Eliminando tre valori dal dominio, restano solo due sottoalberi da visitare

Semplificazione: rendere esplicito un vincolo

Se x=a non ha nessun valore di y, allora backtracking si potrebbe accorgere rapidamente della inconsistenza:

Questo però avviene solo se dopo x viene assegnata la variabile y

Altrimenti, l'albero da visitare potrebbe risultare molto grande:

Usando la consistenza locale, il valore x=a viene escluso subito

Path consistency

Quando si fa path consistency, viene ristretto o creato un nuovo vincolo

Questa è una semplificazione:

• se x=a,y=b non è path-consistent con un'altra variabile, allora il problema viene modificato in modo che x=a,y=b violi un vincolo
• quando backtracking incontra la valutazione x=a,y=b, si accorge immediatamente dell'inconsistenza

Dato che comunque non ci sono soluzioni con x=a,y=b, meglio saperlo subito che scoprirlo dopo aver fatto una visita a un sottoalbero

senza path consistency, nessun vincolo è violato da x=a,y=b si visita quindi il sottoalbero, che può risultare anche molto grande	con path consistency, il vincolo fra x ed y è violato backtracking non visita il sottoalbero

Nota: se si scegliesse z subito dopo y la inconsistenza si vedrebbe subito, ma non è detto che backtracking faccia questa scelta

Sottocasi trattabili

Se un problema è arc consistent e non ci sono domini vuoti, in generale il problema puù essere inconsistente comunque

Per alcuni problemi, questo non succede

Per questi problemi, la propagazione per arc consistency dice se il problema è soddisfacibile

Quindi, la soddisfacibilità di questi problemi è polinomiale

Discorso simile vale per path consistency

Per capire come sono fatti questi problemi, vediamo perchè un problema può essere arc consistent ma inconsistente

Inconsistenza

Quando si forza arc o path consistency, si può svuotare un dominio o la relazione di un vincolo

Questo dimostra che il problema è inconsistente

Esistono problemi inconsistenti che però sono sia arc che path consistenti

Esempio:

Con domini {0,1,2} per tutte le variabili

Per ogni valore di una variabile (es, 0) c'è sempre un valore per un'altra (es, 1)

Per ogni coppia di valori ammessi per due variabili (es, 0 ed 1) c'è sempre un terzo valore ammesso per una terza altra variabile (es. 2)

Però il problema è inconsistente: non esistono quattro valori tutti diversi fra loro e scelti nell'insieme {0,1,2}

Consistenza e consistenza locale

Arc consistency=per ogni valore di una variabile, c'è un valore per l'altra

Perchè un problema arc-consistent può essere inconsistente?

Arc consistency e inconsistenza

Consideriamo una variabile x

Siano y e z le variabili collegate (c'è un vincolo con x,y come scope e uno con x,z)

Per ogni valore di x c'è un valore consistente in y

Per ogni valore di x c'è un valore consistente in z

Scegliendo un valore qualsiasi per x e poi quelli corrispondenti per y e z, si ottiene una soluzione?

I valori di y e z possono non essere consistenti fra loro

Arc consistency e inconsistenza

In questo esempio, non solo x è arc consistent con y e con z

Ogni variabile è consistente con ogni altra

Infatti, ogni nodo ha un arco verso ogni altra variabile

Quindi, il problema è arc consistent

Perè, non è consistente

Per esempio, ad x=1 corrispondono y=1 e z=1, ma questi valori sono inconsistenti fra loro

Perchè esiste l'inconsistenza?

Ogni valore di una variabile si può estendere a tutte le variabili collegate

Lo stesso vale per quei valori delle variabili collegate, ecc.

Il problema è che i valori che si ottengono potrebbero non essere consistenti fra loro

Se il problema non ha cicli, le estensioni si possono fare separatamente

I valori ottenuti non si "incrociano" mai

Quindi, non si possono avere inconsistenze

Caso completo

arc consistency+nessun dominio vuoto=consistenza
se il grafo primale è aciclico

Se un problema con soli vincoli binari ha un grafo primale aciclico, si può seguire questo algoritmo:

1. propagazione che rende il problema arc consistent
   dato che arc consistency non crea nuovi vincoli, il grafo primale resta lo stesso
2. se nessun dominio resta vuoto:
   si sceglie un valore per una variabile, e si estende finchè possibile

Il passo 1 non modifica il grafo, dato che arc consistency non crea nuovi vincoli (rimuove elementi dal dominio)

Il grafo resta quindi aciclico anche dopo il passo 1

Si assume sempre che la node consistency sia già stata ottenuta

Caso completo per la path consistency

La path consistency assicura consistenza in un caso particolare

Path consistency+arc consistency implica che:
consistenza=nessun dominio o relazione vuota se

• vincoli binari
• domini tutti composti da due valori

Vale anche se il grafo primale contiene cicli

Si assume che il problema sia già node e arc consistent

Hyperarc consistency

È una estensione di arc consistency al caso di vincoli non binari

Si può vedere come una riformulazione di arc consistency

Il dominio di una variabile e la relazione di un vincolo si possono scrivere come tabelle:

Arc consistency=ogni elemento del dominio di x compare nella colonna x della relazione del vincolo

E inoltre, il valore di y nella stessa riga deve stare nel dominio di y

Es. per x il valore 1 va bene, 2 no perchè non appare nella tabella, 3 no perchè sta nella tabella ma non c'è un valore per y

x=2 ed x=3 non stanno in nessuna soluzione e quindi si possono eliminare

Estensione a vincoli con più variabili

Stesso principio:

Dato che 2 non compare nella colonna x della relazione, x=2 non può stare in nessuna soluzione

Stessa cosa vale per i valori che stanno nella relazione ma la riga non va bene perchè contiene valori che non stanno nel dominio di altre variabili

Definizione formale

A partire dalla definizione sulle tabelle
riscritta sulla definzione formale di vincolo

Una variabile xi è hyperarc consistent con un vincolo C=(⟨x1,...,xn⟩,R) che contiene xi se valgono le seguenti condizioni

• per ogni valore a ∈ Dxi
• esiste una tupla di valori ⟨a1,...,an⟩ ∈ R tale che:
  • aj &isin Dxj per ogni j ∈ {1,..,n}
  • ai=a

È la stessa definizione di arc consistency, solo che ora nel vincolo ci sono più variabili

Validità della arc consistency

Se per x=a la arc consistency con C non vale, allora non esistono valori per le altre variabili in modo che C sia soddisfatto

Quindi x=a si può eliminare dal dominio di x

Questo è il tipo di propagazione che si usa per hyperarc consistency

Consistenza locale: generalizzazione

Arc: per ogni valore consistente di x, esiste un valore di y consistente con esso

Path: per ogni coppia di valori di x ed y consistente, esiste un valore di z consistente con entrambi

Generalizzione: data una valutazione consistente di i-1 variabili, esiste un valore per un'altra variabile che sia consistente con la essa

Condizione sul singolo vincolo

Un singolo vincolo con i-1 variabili è i-consistente con una variabile y che non è nel suo scope se:

• se una valutazione soddisfa il vincolo
• allora esiste un valore di y consistente con essa

Condizione sul problema

È quella che interessa

• se una valutazione di i-1 variabili è consistente
• allora esiste un valore consistente per una qualsiasi altra variabile

Notare: una valutazione di un sottoinsieme di variabili è consistente se soddisfa tutti i vincoli che hanno solo quelle variabili nello scope

Definizione formale

Un problema è i-consistente se:

• per ogni qualsiasi valutazione di i-1 variabili qualsiasi x1=a1,...,xi-1=ai-1
• se questa valutazione soddisfa tutti i vincoli il cui scope è contenuto in x1,...,xi-1
• allora, per una qualsiasi altra variabile xi
• esiste un valore ai tale che la valutazione x1=a1,...,xi-1=ai-1,xi=a1 soddisfa tutti i vincoli il cui scope è contenuto in x1,...,xi-1,xi

Arc e path consistency

Assumendo la forma normale (i vincoli sulle stesse variabili sono raggruppati)

Arc consistency=2-consistency

Infatti, si può riscrivere come: ogni valutazione consistente di una variabile si può estendere ad un'altra

Path consistency=3-consistency solo per vincoli binari

Si può riscrivere come: ogni valutazione consistente di due variabili si può estendere alla terza

Non è la stessa cosa se i vincoli non sono binari

Path consistency e 3-consistency

Differenza, per vincoli non binari:

path consistency

se una valutazione soddisfa Cxy, allora esiste un valore per z per cui Cxz e Cyz sono soddisfatti

3-consistency

se una valutazione su x ed y è consistente (=soddisfa Cxy) allora si può estendere a z in modo che tutti i vincoli siano soddisfatti (Cxz, Cyz e Cxyz)

Se i vincoli ternari non sono ammessi, allora Cxyz non esiste e le due condizioni sono uguali

Strong i-consistency

Indica che un problema è j consistente per ogni j <= i

Quindi: ogni valutazione consistente di i e meno variabili si può estendere consistentemente ad un'altra variabile

Consistenza e consistenza forte

Un problema può essere i-consistente ma non fortemente i-consistente

Esempio: problema 5-consistente che non è 4-consistente

• variabili X
• dominio {0,1}
• vincoli allequal(...) su tutti i sottoinsiemi di esattamente cinque variabili

Per questo problema risulta:

• ogni valutazione parziale di quattro variabili è consistente (nessun vincolo ha solo quttro variabili nello scope, quindi nessun vincolo può essere violato)
• una valutazione di cinque variabili è consistente solo se le cinque variabili sono tutte uguali
• lo stesso per le valutazioni su sei variabili

Il problema è 6-consistente perchè ogni valutazione a cinque variabili uguali si può estendere a una sesta usando lo stesso valore

Il problema non è 5-consistente perchè una valutazione di quattro valori diversi non si può estendere con altro valore in modo che tutti i valori siano uguali fra loro

Propagazione

Una valutazione sulle variabili X potrebbe non essere estendibile ad un'altra variabile

Questa valutazione non fa parte di nessuna soluzione

Si può eliminare questa valutazione

Si fa eliminando la tupla di valori dalla relazione del vincolo CX, il vincolo sulle variabili X

Cosa garantisce la propagazione?

Effetti della propagazione

Se un problema è fortemente i-consistente:

• una valutazione consistente di una variabile si può estendere a una consistente di due
• una valutazione consistente di due variabili si può estendere a una consistente di tre
• una valutazione consistente di tre variabili si può estendere a una consistente di quattro
• ...
• una valutazione consistente di i-1 variabili si può estendere ad una consistente di i

Quindi, si può arrivare facilmente ad una valutazione consistente di i variabili, se ne esiste una di una variabile

Se i è uguale al numero di variabili, si arriva ad una soluzione del problema se esiste un dominio non vuoto

Problemi senza soluzione

Se un problema è n-consistente, dove n è il numero delle variabili, allora è consistente?

La catena vista prima dice solo che una valutazione consistente di una variabile si può estendere a una soluzione

Il problema ha soluzioni (se e) solo se esiste un dominio non vuoto

Propagazione

Per problemi fortemente n-consistenti:

Esistenza soluzioni=esistenza domini non vuoti dopo la propagazione

Per gli altri tipi di consistenza, era: domini/relazioni vuote implica inconsistenza

In questo caso, vale nei due versi

Nota: se propagazione svuota una relazione, allora poi svuota anche tutti i domini

Costo della valutazione/propagazione

Per i-1 variabili con domini di d valori ognuno:

Esistono d^i-1 valutazioni possibili

Queste vanno poi estese con un valore di un'altra variabile

Costo totale, nel caso peggiore: ordine di dⁱ

Vincoli specifici

Per vincoli particolari esistono algoritmi specializzati di la propagazione

In particolare, vediamo per il vincolo alldifferent(x₁,...,x_n)

Arc consistency su alldifferent

alldifferent(x₁,...,x_n) equivale a tutti i vincoli binari x_i ≠ x_j

Problema già visto: se tutte le variabili hanno dominio {0,1}, allora tutti i vincoli x_i ≠ x_j sono arc-consistent

In generale: alldifferent(x₁,...,x_n) è inconsistente se il numero totale di valori dei domini di queste variabili è maggiore di n (numero di variabili)

Infatti, per dare valori differenti ad n variabili, servono almeno un numero di valori complessivi pari ad n

Dopo aver ottenuto la arc consistency sui vincoli binari, questa condizione dice se il vincolo è consistente oppure no

Arc consistency specializzata

Si prende un valore di una variabile

Si assegna questo valore alla variabile
(si fa una prova con il dominio della variabile che contiene solo questo valore)

Si fa arc consistency

Si verifica la consistenza del vincolo alldifferent come detto prima

In caso di inconsistenza, il valore scelto della variabile non va bene, e si può eliminare dal dominio

Variante migliore

Il metodo visto prima per verificare se il vincolo alldifferent è soddisfacibile si può migliorare

Si tratta di trovare un matching in un grafo bipartito

Gli archi neri sono quelli del matching

I nodi sono: le variabili da una parte e i valori dall'altra

Gli archi rappresentano il fatto che una variabile può assumere un valore

Si usano algoritmi specializzati