Module 4 (Search)

Assignment 4

Suppose the neighbours are given by the following relations:

Suppose the heuristic estimate of the distance toneighbours(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,[]).

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*:

- Depth-first search
- Breadth-first search
- Least-cost first search
- Best-first search
- A
search^{*}

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

`~cs322/tools/search/search`

.
- 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 depth-first search.
- 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.^{*}

David Poole