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,[]).

For each of the following search strategies to find a path fromh(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).

- 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`

.
Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999