## 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.