Up Next
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.
  1. 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.
  2. 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).
  3. Is a backward search more efficient than a forward search for breadth-first search or A*? Explain why.
  4. How could a bi-directional search help? Explain. What forward and backward searches would be useful?
  5. Give the distance table created by dynamic programming to find a path from mi to cp.
  • Solution

  • David Poole

    Up Next