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
Figure 1: Find the shortest path from A to Z
(using graph-search), if one exists?
Problem 2 (30 points):
Consider the game in Figure 2.
(a) Circle the terminal nodes that will be visited during aminimax 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 strategyin 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.
Figure 2: Game Tree
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 (showthe 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.
