Suppose we have the following heuristic values for the distance to

h(sp)=0 | h(dt)=2 | h(kb)=3 |

h(jb)=3 | h(ubc)=5 | h(kd)=6 |

h(mp)=7 | h(bby)=8 | h(ap)=8 |

h(rm)=9 | h(sry)=29 |

- 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.

Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999