Homework 2: Constraint Satisfaction Problems

CS410: Artificial Intelligence 
Homework 2: Constraint Satisfaction Problems

1. A* graph search. Consider the following undirected graph shown in
Figure 1 where we are searching from start state A to goal state G. The
number over each edge is the transition cost. Additionally, we are given
a heuristic function h as follows: {h(A) = 7, h(B) = 5, h(C) = 6, h(D) =
4, h(E) = 3, h(F) = 3, h(G) = 0}. Assume that, in case of ties, the search
procedure uses an alphabetical order for tie-breaking.
Find the sequence of nodes expanded by A* graph search algorithm, with
problem-solving steps (i.e., updates for the frontier and explored set).
B
A
C
D
F
E
G
2
4
3
3 1
2
1
1
4
3
Figure 1: Problem 1.
2. CSP formulation. Consider the following three problems:
(a) Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.
(b) Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots
for classes. Each professor has a set of classes that he or she can
teach.
1
(c) Hamiltonian tour: given a network of cities connected by roads,
choose an order to visit all cities in a country without repeating
any.
Determine each as a planning problem or an identification problem and
explain why. Give precise formulations for each problem as constraint
satisfaction problems.
Recall a CSP consists of three components, X, D, and C. Note that there
are many valid formulations, but you only need to provide one.
3. Forward checking. Solve the cryptarithmetic problem shown in Figure 3
step by step, using the strategy of backtracking with forward checking.
Assume the variable order is X3 → F → X2 → X1 → O → T → R →
U → W, and the value order is increasing. Note that different variables
have different domains (e.g., the domain for X3 is {0, 1}, the domain for
Section 6.1. Defining Constraint Satisfaction Problems 207
O is {0, 1, . . . , 9}, and the domain for F is {1, 2, . . . , 9}).
(a)
F T U W R O
(b)
+
F
T
T
O
W
W
U
O
O
R
one binary constraint for each pair of constraints in the original graph that share variables. For
example, if the original graph has variables {X,Y,Z} and constraints (X,Y,Z),C1 and
(X,Y ),C2 then the dual graph would have variables {C1,C2} with the binary constraint
(X,Y ),R1, where (X,Y ) are the shared variables and R1 is a new relation that defines the
constraint between the shared variables, as specified by the original C1 and C2.
There are however two reasons why we might prefer a global constraint such as Alldiff
rather than a set of binary constraints. First, it is easier and less error-prone to write the
problem description using Alldiff . Second, it is possible to design special-purpose inference
algorithms for global constraints that are not available for a set of more primitive constraints.
We describe these inference algorithms in Section 6.2.5.
The constraints we have described so far have all been absolute constraints, violation of
which rules out a potential solution. Many real-world CSPs include preference constraints PREFERENCE
CONSTRAINTS
indicating which solutions are preferred. For example, in a university class-scheduling problem there are absolute constraints that no professor can teach two classes at the same time.
But we also may allow preference constraints: Prof. R might prefer teaching in the morning,
whereas Prof. N prefers teaching in the afternoon. A schedule that has Prof. R teaching at
2 p.m. would still be an allowable solution (unless Prof. R happens to be the department chair)
but would not be an optimal one. Preference constraints can often be encoded as costs on individual variable assignments—for example, assigning an afternoon slot for Prof. R costs
2 points against the overall objective function, whereas a morning slot costs 1. With this
formulation, CSPs with preferences can be solved with optimization search methods, either
pathbasedorlocalWecallsuchaproblemaconstraintoptimizationproblemorCOPCONSTRAINT
OPTIMIZATIONX3 X2 X1
(a) A cryptarithmetic problem. Each letter stands for a distinct digit; the aim is
to find a substitution of digits for letters such that the resulting sum is arithmetically correct,
with the added restriction that no leading zeroes are allowed. (b) The constraint hypergraph
for the cryptarithmetic problem, showing the Alldiff constraint (square box at the top) as
well as the column addition constraints (four square boxes in the middle). The variables X1,
X2, and X3 represent the carry digits for the three columns.
Figure 2: Problem 3.
4. AC-3. Consider the following CSP:
• Variables: A, B, C, D
• Domain: {1, 2, 3}
• Constraints: A 6= B, B > C, C < D
Solve the problem using the strategy of backtracking search with AC-3
algorithm. Give the problem-solving steps, specifying each assignment
2
when backtracking and the consequence of each pop operation in AC-3
(i.e., what values you cross off and which arcs you push to the queue).
Suppose the value order is descending and the variable order is alphabetical, which both queue initialization and neighbor consideration follow
(i.e., the queue is initialized as A → B, B → A, . . .).
5. K-consistency & tree structure. Consider the following three questions:
(a) Give a concrete CSP example to show that k-consistency does not
imply (k + 1)-consistency for some k ≥ 2.
(b) Give a concrete CSP example to show that k-consistency does not
imply (k − 1)-consistency for some k ≥ 3.
(c) Why graphs with cycles can not be applied with the algorithm for
tree-structured CSPs (introduced in Page 77-83, Lecture 4)? What
step in the analysis fails? Why this step holds for trees? Give an
example to explain the failure.
3