Up
Go up to Question 1

Solution

  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.

    A* and breadth-first search both do. Depth-first search and best-first search don't find a path.

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

    Number of nodes selected to get an answer:

  3. Is a backward search more efficient than a forward search for breadth-first search or A*? Explain why.

    Yes, backward search is more efficient, and there are fewer choices at each stage. For example, A* search has the following number of nodes selected for the backward search.

    Backwards, breadth-first search finds a solution in 13 steps, whereas forward search takes 95 steps (node expansions).
  4. How could a bi-directional search help? Explain. What forward and backward searches would be useful?

    The problem with this graph is that the forward search is so much worse than the backward search. A very limited forward search expands more nodes than we need to find the backward path. So a bi-directional search wouldn't help.

    One could imagine a limited A* search from mi, that quickly determines that the path length is at least 24.9 (when hi is selected). Therefore the distance from mi to bg must be at least 24.9-6.4=18.5. We could use this updated heuristic information to not expand bg, but this doesn't really save us, particularly with multiple path pruning.

    You can get full marks for this part by writing anything sensible.

  5. Give the distance table created by dynamic programming to find a path from mi to cp.
    dist(cp) = 0
    dist(fv) = 8.5
    dist(tw) = 21.7
    dist(gb) = 31.3
    dist(mv) = 34.8
    dist(bg) = 36.0
    dist(mi) = 53.1
    dist(hi) = 62.6
    dist(fg) = 63.8
    dist(uv) = 71.4
    dist(rs) = 92.7
    dist(ab) = 101.5
    dist(re) = 113.6

David Poole

Up