COMS 4701 Midterm Practice Exam Spring 2024 1. Consider the directed search graph shown below. S is the start state and G is the goal state. Transition costs are shown
COMS 4701 Midterm Practice Exam Spring 2024 1. Consider the directed search graph shown below. S is the start state and G is the goal state. Transition costs are shown along the graph edges. Note that the transition between C and D is bidirectional. (a) For each of the search algorithms below, indicate the largest number of nodes that may possibly be expanded, not counting the goal state. Assume all algorithms conduct the goal test upon popping a node from the frontier. (Your answer may be ∞ .) Depth-first search with no reached table Depth-first search with reached table Breadth-first search with reached table (b) Suppose we run uniform-cost search on this search graph. List the order in which nodes are expanded (do not count the goal state) and give the final solution returned. Expanded nodes Returned solution (c) Suppose we currently have a heuristic function h(n) = 0 for all nodes n. Propose a change to the heuristic of a single node (indicate both node and heuristic value), such that h remains admissible and A* may expand fewer nodes than UCS. Also write out this shorter sequence of… Read More »COMS 4701 Midterm Practice Exam Spring 2024 1. Consider the directed search graph shown below. S is the start state and G is the goal state. Transition costs are shown