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.
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.
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.
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999