Description
Problem 1 (30 points):
Figure 1: Find the shortest path from A to Z
Consider the graph in Figure 1 for a search problem
from A to Z. All edges of the graph are undirected (bidirectional) and labelled with their cost. The labels of the
nodes contain a heuristic approximation (in paranthesis)
w.r.t. the remaining cost to the goal node Z. Whenever several nodes have identical priorities for expanding, the nodes
shall be expanded in the alphabetical order of their labels.
(a) Using graph-search (i.e., no loops), conduct a breadthfirst search, depth-first search, greedy best-first search
and A*-search, on the graph. For each of these methods, show the open list at each step, and the path that
is returned as the result.
(b) Did the A*-search find the optimal path? Why (not)?
How about the other methods?
(c) Do all these search methods find a solution in general
(using graph-search), if one exists?
Problem 2 (30 points):
Figure 2: Game Tree
Consider the game in Figure 2.
(a) Circle the terminal nodes that will be visited during a
minimax depth-first search (from left to right) that uses
alpha-beta pruning. Draw a line accros each edge that
is pruned.
(b) In the first move, will player MAX move to node (D)
or (H)? Justify your answer.
(c) Suppose that MIN does not follow a minimax strategy
in playing the game. Instead, suppose that at node (D),
MIN would choose to move to node (C), and at node
(H), MIN would choose to move to node (G). Under
this strategy for MIN, what would MAX’s best first
move be? (I.e. player MAX move to node (D) or (H)?)
Justify your answer.
Problem 3 (30 points): Consider the following CSP with 3 variables X,Y and Z: Dom(X) = {1, . . . , 10}, Dom(Y ) =
{5, . . . , 15}, and Dom(Z) = {5, . . . , 20}, and binary constraints: C(X, Y ) : X > Y , C(Y, Z) : Y + Z = 12, and
C(X, Z) : X + Z = 16.
(a) Draw the constraint graph.
(b) Are the constraints arc consistent? If no, apply arc consistency method repeatedly so they become arc consistent (show
the domains of the variables at each iteration).
Problem 4 (10 points): In a Constraint Satisfaction Problem (CSP) search, explain why it is a good heuristic to choose the
variable that is most constrained but the value that is least constraining.
