Go backward to 1 Finding Paths in a Grid
Go up to Top
Go forward to 3 Comparting Different Search Strategies

2 Searching on a simple graph

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.

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.
[Explain clearly what your notation means.]
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?
Suppose you were contacted by TecnoTaxi to advise on a method for finding routes between locations in your city. What method would you recommend, and why. Give one shortcoming of the method you propose. You must use full sentences.