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`

.
- Depth-first search
- What is the final path found?
*s -> a -> b -> h -> i -> g*. - How many nodes were expanded?
7.

- Explain why it selected
nodes during the search that were not on the shortest path from
*s*to*g*.It selects nodes in order irrespective of where the goal is.

- Explain why it may have been led astray in the final solution.
It reports whatever path it finds first; this could be any path depending on the order of the neighbours.

- What is the final path found?
- Breadth-first search
- What is the final path found?
*s -> a -> b -> g*. - How many nodes were expanded?
9.

- Explain why it selected
nodes during the search that were not on the shortest path from
*s*to*g*.It selects all nodes that are two steps from the start node, irrespective of where the goal is, before it expands nodes that are three steps away and finds the goal.

- Explain why it may have been led astray in the final solution.
It finds the path with the fewest arcs, not the shortest path.

- What is the final path found?
- Least-cost first search
- What is the final path found?
*s -> c -> d -> e -> f -> g*. - How many nodes were expanded?
10

- Explain why it selected
nodes during the search that were not on the shortest path from
*s*to*g*.It explores the paths in order of length, irrespective of where the goal is.

- Explain why it may have been led astray in the final solution.
It wasn't; least cost first always finds the shortest path to the goal.

- What is the final path found?
- Best-first search
- What is the final path found?
*s -> a -> b -> g*. - How many nodes were expanded?
4

- Explain why it selected
nodes during the search that were not on the shortest path from
*s*to*g*.It chooses the node closest to the goal, and doesn't take into account the path length from the start node.

- Explain why it may have been led astray in the final solution.
Node

*a*was closer to the goal than node*c*, once it had nodes on the frontier that were close to goal, it never considered*c*.

- What is the final path found?
- A
search^{*}- What is the final path found?
*s -> c -> d -> e -> f -> g*. - How many nodes were expanded?
7.

- Explain why it selected
nodes during the search that were not on the shortest path from
*s*to*g*.Node

*a*looked as thought it was on a direct route to the goal. But, the deviation to go to*b*was greater than the cost of going via*c*. - Explain why it may have been led astray in the final solution. .
It wasn't; A

always finds the shortest path to the goal.^{*}

- What is the final path found?

David Poole