Arc consistency (slides5)

Question 1

arc consistency

Answer 1

simplest form of propagation makes each arc consistent
X–>Y is consistent iff
-for every value x of X there is some allowed y
-If X loses a value, neighbors of X need to be rechecked

Question 2

arc consistency properties

Answer 2

detects failure earlier than forward checking

can be run as a preprocessor or after each assignment

Question 3

Generalized Arc Consistency (GAC)

Answer 3

implementation of Arc Consistency

Question 4

GACSupport

Answer 4

does a value v for variable X have support in constraint c?

Question 5

IsItGAC

Answer 5

does GACSupport answer yes for every value in the domain of each variable of a constraint c?

Question 6

NoGACWipeout

Answer 6

are there non empty subsets of the domains of the variables such that IsItGAC answer yes?

Question 7

MaxGAC

Answer 7

will IsItGAC answer yes for the domains of the variables and no for every superset of the domains

Question 8

GACDomain

Answer 8

return the domains of the variables such that MaxGAC will answer yes

Question 9

arc consistency algorithm

Answer 9

receives a binary CSP as input and returns the CSP possibly with reduced domains

main function is AC-3
calls RM-Inconsistent -Values function

Question 10

function AC-3

Answer 10

function AC-3(csp) returns the CSP , possibly with reduced domains
inputs: csp, a binary CSP with variables {X1,X2,...,Xn}
local variables: queue: a queue of arcs, initially all the arcs in csp

while queue is not empty do

• (Xi,Xj)<–Remove-First(queue)
• if RM-Inconsistent-Values(Xi,Xj) then
• -for each Xk in Neighbors[Xi] do
• –add(Xk,Xi) to queue

Question 11

function RM-Inconsistent-Values

Answer 11

function RM-Inconsistent-Values(Xi,Xj) returns true iff remove a value
removed<--true
return removed

Question 12

complexity of AC-3

Answer 12

for binary constraint networks
Time: O(ed^3) and O(n^2d^3) since e=O(n^2)
-n = number of variables
-e = number of constraints
-d = domain size

Space: O(e): the queue contains at most e elements

Question 13

Directional arc Consistency (DAC)

Answer 13

observation 1: arc revisions have a directional character but CSP is not directional

obs2: AC has to repeat arc revisions; the total number of revisions depends on the number of arcs but also on the size of domains

Definition: A binary CSP is directional arc consistent using a given order of variables iff for every constraint c(Xi,Xj) such that Xi<Xj the (Xi,Xj) is arc consistent

Question 14

Algorithm DAC-1

Answer 14

1) Consistency of the constraint is required just in one direction
2) Variables are ordered

if the arc are explored in a “good” order, no revision has to be repeated!

Question 15

how to use DAC setup

Answer 15

-AC is stronger than DAC(if CSP is AC then it is DAC as Well)
-is it useful?
–DAC-1 is much faster than any algorithm for AC
–there exist problems where DAC is enough
Example: if the constraint graph forms a tree then DAC is enough to solve the problem without backtracks
-how to order the vertices for DAC?
-How to order the vertices for search?

Question 16

How to use DAC

Answer 16

1) apply DAC in the order from the leaf nodes to the root
2) Label vertices starting from the root

DAC guarantees that there is a value for the child node compatible with all the ancestors

Question 17

problems with arc consistency

Answer 17

we dont get a solution from using it

we dont know if a solution exists from using it

Question 18

benefits of arc consistency

Answer 18

-Many incompatible values can be removed
-sometimes we have a solution after AC
–a domain is empty–> no solution exists
–all the domains are singleton–> we have a solution
in general, AC prunes the search space –> equivalent easier problem