Go backward to Question 1 [15 marks]
Go up to Top
Go forward to Question 3(a)

Question 2 [15 marks]

Consider the graph (not drawn to scale) with arc lengths shown on the arcs:

Suppose we have the following heuristic values for the distance to sp.

(a): [6 marks] Show the nodes expanded (taken off the frontier), in order, and the f-value for each node added to the frontier for an A^* search from ubc to sp. Assume that multiple-path pruning is used, and that the search stops after the first path is found. Show clearly the path found.
[You can either number the nodes on the graph and give the f-values, or use the space below to write your answer.]
(b): [6 marks] Show how dynamic programming can be used to find a path from ubc to sp. Show all distance values that are computed, and how these are used to find the shortest path. What path is found?
[You may use the graph to show your answer, or write your answer in the space below, but you must explain clearly what your notation means.]
(c): [3 marks] Suppose you were contacted by TecnoTaxi to advise on a method for finding routes between locations in Vancouver. What method would you recommend, and why. Give one shortcoming of the method you propose. You must use full sentences.