Go up to Top
Go forward to Question 2
Question 1
The graph mod5gr1999, available from the web site in both
CILog format as well as for the graph-drawing applet, is meant to be
part of the road network for a city. For this graph,
the aim is find a path from node mi to the location cp that can
only be reached by round-about methods.
- Which of the following methods will find a path from mi to
cp without loop
detection or multiple-path pruning: depth-first search, A* search,
breadth-first search, best-first search.
- For A* search, how much saving (in the number of nodes expanded)
is obtained by using loop
detection and using Multiple-path pruning? (Give the number of nodes
selected from the frontier with and without each of the two pruning
methods).
- Is a backward search more efficient than a forward search
for breadth-first search or A*? Explain why.
- How could a bi-directional search help? Explain. What forward
and backward searches would be useful?
- Give the distance table created by dynamic programming to find a
path from mi to cp.
David Poole