CS322 Fall 1999
Module 4 (Search)
Assignment 4

Due: 1:30pm, Monday 4 October 1999.

The aim of this assignment is to learn about the basic search procedures.

Question 1

Consider the graph:
Search Graph
 

Suppose the neighbours are given by the following relations: 

neighbours(s,[a,c,k]).
neighbours(a,[b]).
neighbours(b,[h,g]).
neighbours(c,[d]).
neighbours(d,[e]).
neighbours(e,[f]).
neighbours(f,[g]).
neighbours(g,[]).
neighbours(h,[i]).
neighbours(i,[j]).
neighbours(j,[]).
neighbours(k,[l]).
neighbours(l,[]).
Suppose the heuristic estimate of the distance to g is: 
h(a,2).     h(b,3).
h(c,4).     h(d,3).
h(e,2).     h(f,1).     
h(g,0).     h(h,4).     
h(i,5).     h(j,6).     
h(k,5).     h(l,6).     
h(s,4).

For each of the following search strategies to find a path from s to g:

  1. Depth-first search
  2. Breadth-first search
  3. Least-cost first search
  4. Best-first search
  5. A* search
Specify:
  1. What is the final path found?
  2. How many nodes were expanded?
  3. Explain why it selected nodes during the search that were not on the shortest path from s to g.
  4. Explain why it may have been led astray in the final solution. (Either state that it found the shortest part, or explain why the shortest path was not found).
Note there are 20 parts to this question. By brief and concise. You can use the search applet available on the web page and at ~cs322/tools/search/search.

Question 2

For each of the following, give a graph that is a tree (there is at most one arc into any node), contains at most 15 nodes, and has at most two arcs out of any node.
  1. Give a graph where depth-first search is much more efficient (expands fewer nodes) than breadth-first search.
  2. Give a graph where breadth-first search is much better than depth-first search.
  3. Give a graph where A* search is more efficient than either depth-first search or breadth-first search.
  4. Give a graph where depth-first search and breadth-first search are both more efficient than A* search.
You must draw the graph and show the order of the neighbours (this is needed for the depth-first search). Either give the arc costs and heuristic function or state explicitly that you are drawing the graph to scale and are using Euclidean distance for the arc costs and the heuristic function.

Question 3

For each question in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
David Poole