Sale!

# CS 440:Midterm Exam solved

Original price was: \$35.00.Current price is: \$30.00.

Category:

## 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)?
(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)
(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)?)