CS322 Fall 1999
Module 4 (Search)
Due: 1:30pm, Monday 4 October 1999.
The aim of this assignment is to learn about the basic search procedures.
Consider the graph:
Suppose the neighbours are given by the following relations:
Suppose the heuristic estimate of the distance to g is:
For each of the following search strategies to find a path from s to g:
- Depth-first search
- Breadth-first search
- Least-cost first search
- Best-first search
- A* search
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
- What is the final path found?
- How many nodes were expanded?
- Explain why it selected
nodes during the search that were not on the shortest path from s to g.
- 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).
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.
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
For each question in this assignment, say how long you spent on it.
reasonable? What did you learn?
- Give a graph where depth-first search is much more efficient (expands fewer nodes)
than breadth-first search.
- Give a graph where breadth-first search is much better than
- Give a graph where A* search is more efficient than either
depth-first search or breadth-first search.
- Give a graph where depth-first search and breadth-first search
are both more efficient than A* search.