Go backward to 2 Searching on a simple graph
Go up to Top
Go forward to 4 Generating Graphs Good for Different Search Strategies
3 Comparting Different Search Strategies
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).
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999