Question

Draw the constraint network for a CSP problem with three binary variables, A, B, C, with the three constraints A !=B, B != C, and A != C.

Trace arc consistency.

Reflect on the outcome.

Answer 1

where A=Green, B=Red, C=Blue

By tracing the above constraint network with arc consistency, we can conclude that there will be four temporary efficiency improvement turns will work for the same, which will result in following result

Turn 1: T=O(d³nc)

Turn 2: T=O(d³nc)

Turn 3: T=O(d³c)

Turn 4: T=O(d²c)

Similarly for space:

Turn 1: S= O(c+dn)

Turn 2: S= O(c+dn)

Turn 3: S= O(c+dn)

Turn 4: S= O(d²c)

where d: domain size, c=number of constraints, n=number of variables.