Consistenza relazionale

Simile alla i-consistenza

Si vuole la consistenza con un singolo vincolo, non con tutti quelli rilevanti

Su archi (vincoli binari)

Arc consistency di un vincolo (binario)= ogni assegnamento consistente ad una variabile del vincolo si può estendere all'altra in modo che il vincolo fra loro sia soddisfatto

Riformulazione:

• una valutazione consistente ad una variabile si può estendere a tutte le variabili del vincolo in modo che il vincolo sia soddisfatto
• una valutazione consistente a tutte le variabili di un vincolo tranne una si può estendre all'una in modo che il vincolo sia soddisfatto

Su vincoli binari, è la stessa cosa

Su vincoli non binari, la prima è hyperarc consistency, la seconda è relational consistency

Consistenza relazionale: definizione

Relational arc consistency=ogni assegnamento consistente a tutte le variabili del vincolo tranne una si può estendere all'altra

Si può vedere come una estensione della arc consistency a vincoli non binari

Relational arc consistency e hyperarc consistency

Differenza: dato un vincolo:

hyperarc consistency

ogni assegnamento consistente ad una variabile del vincolo si può estendere ad un assegnamento a tutte le variabili del vincolo in modo che il vincolo sia soddisfatto

relational arc consistency

ogni assegnamento consistente a tutte le variabili del vincolo tranne una si può estendre a quella in modo che il vincolo sia soddisfatto

Differenza: esempi

Hyperarc consistente ma non consistente relazionalmente

Consistenza del vincolo alldifferent(x,y,z) quando le variabili hanno dominio {0,1,2} e non ci sono altri vincoli

hyperarc:

consistente, perchè ogni valore di una variabile (es. x=0) si puè estendere in modo da soddisfare C (es. valori y=1,z=2)

relational:

inconsistente: x=0,y=0 è consistente perchè non ci sono vincoli con scope contenuto in {x,y}

Relazionalmente consistente ma non hyperarc consistente

Consistenza del vincolo equal(x,y,z) (=tutte e tre le variabili uguali), domini D_x={0,1} e D_y=D_z={0} e altri vincoli x=y, y=z e x=z

hyperarc:

inconsistente, perchè il valore x=1 non si può estendere alle altre variabili in modo che equal(x,y,z) sia soddisfatto

relational:

consistente: ogni valutazione consistente di due variabili deve necessariamente assegnare 0 ad esse (per via degli altri vincoli); usando 0 come valore dell'altra variabile, il vincolo equal(x,y,z) è soddisfatto

Rappresentazione grafica

Consistenza relazionale del vincolo C con la variabile x

Esempio: problema con questo ipergrafo:

Il vincolo C è su quattro variabili

Per le tre a sinistra della freccia, ci sono valutazioni che soddisfano gli altri vincoli

Queste si devono poter estendere a x in modo che C sia soddisfatto

Notare che il vincolo fra la variabile in alto a sinistra e x non viene considerato affatto; viene invece considerato da i-consistency

Conta solo se C è soddisfatto o no

Definizione formale

Un vincolo C=(S,R) è relazionalmente arc consistent in un problema se:

• per ogni variabile x ∈ S
• per ogni valutazione V delle variabili S \ {x}
• esiste un valore a ∈ Dx tale che V ∪ {x=a} soddisfa C

Consistenza e propagazione

Se una valutazione non si può estendere a un'altra variabile in modo che un vincolo sia soddisfatto, non fa parte di nessuna soluzione

Queste valutazioni si possono eliminare

Da dove?

Propagazione, in generale

Si rende esplicito il fatto che una valutazione parziale non fa parte di nessuna soluzione

Viene realizzato facendo in modo che la valutazione parziale violi un vincolo

Propagazione per consistenza relazionale

Si assume che ogni insieme di variabili abbia un vincolo

Se una valutazione di S\{x} non fa parte di una soluzione, si può eliminare dal vincolo sulle variabili S\{x}

Se questo vincolo non esiste, si assume quello sempre soddisfatto

Dopo l'eliminazione, non è più un vincolo soddisfatto da tutte le valutazioni

Questo significa che la propagazione può creare vincoli nuovi

Relational path consistency

Path consistency su vincoli binari: ogni valutazione consistente di due variabili si può estendere ad una terza in modo che i vincoli binari siano soddisfatti

Nella figura sono evidenziati i vincoli che devono essere soddisfatti: C_xz e C_yz

Path consistency: generalizzazione

Due vincoli con una variabile in comune

Ogni valutazione a tutte le variabili tranne quella si può estendre a quella in modo che i due vincoli siano soddisfatti

Path consistency relazionale: stessa definizione, con due vincoli qualsiasi e una variabile comune ad essi

Relational path consistency: definizione

Relational path consistency è fra due vincoli e una variabile comune ad essi

Due vincoli sono relazionalmente path consistent con la variabile se ogni assegnamento consistente a tutte le altre variabili dei due vincoli si può estendere alla variabile in modo che i due vincoli siano soddisfatti

Grafica

Consistenza path-relazionale di C e D con x

Se una valutazione delle tre variabili in colonna a sinistra soddisfa i vincoli relativi (E, F ed H),

allora questa valutazione si può estendre con un valore di x in modo tale che C e D siano soddisfatti

Estensione a più vincoli

La condizione si estende a più vincoli

Un insieme di m vincoli è relazionalmente m-consistente con una variabile che si trova nello scope di tutti loro se:
ogni assegnamento consistente alle altre loro variabili si può estendere all'altra in modo che tutti i vincoli siano soddisfatti

Consistenza di un problema

Un insieme di m vincoli è m-relazionalmente consistente se lo è rispetto ad ogni possibile variabile nello scope di tutti loro

Un problema è m-relazionalmente consistente se lo è ogni suo sottoinsieme di m vincoli

Strong relational consistency

Un problema è fortemente relazionalmente m-consistente se è relazionalmente k-consistente per ogni k<m

Versione direzionale

Esiste anche una versione direzionale della consistenza relazionale

Relational directional arc consistency: la variabile a cui si deve estendere l'assegnamento è l'ultima variabile dello scope del vincolo

Casi completi

Se un problema è fortemente m-relational consistent e i domini hanno tutti cardinalità ≤m allora è consistente

Si dimostra facendo vedere che ogni valutazione a k variabili si può estendere ad un'altra variabile

Questo si dimostra per contraddizione

Considero una valutazione x₁=a₁,...,x_k=a_k

Assumo che non si possa estendere in nessun modo ad y

Se D_y={a₁,...,a_m}, allora queste valutazioni sono inconsistenti:

Quindi, ognuna di queste viola un vincolo

Questi sono m vincoli violati (alcuni possono coincidere, per cui sono in effetti al più m vincoli violati)

Quindi, non c'è modo di estendere una valutazione ad un'altra variabile in modo da soddisfare m vincoli

Questo contraddice la assunzione di m-consistenza

Altro caso completo

Misura dei vincoli (invece che dei domini)

Un vincolo è m-stretto se ogni valutazione di tutte le sue variabili tranne una si può estendere all'altra variabile in modo che il vincolo sia soddisfatto:

• con tutti i valori possibili dell'ultima variabile
• con al più m valori possibili dell'ultima variabile

Se tutti i vincoli di un problema sono m-stretti e il problema è fortemente relazionalmente m+1-consistente, allora è consistente