State space Search (more)

Breadth-first search v. Depth-first search

Let us compare these two forms of exhaustive search.

Breadth-first is guaranteed to find the (joint) shortest path to the goal. Whereas Depth-first might find a goal deep in the structure, yet not realise that a different choice at the start could have led straight there.
If path length matters, Depth-first could keep going after finding goal and find multiple paths, compare lengths.
Problem with Depth-first is tree might grow forever. Often, Depth-first is given a depth bound of n levels after which it will backtrack.
Problem with Breadth-first is it must keep a list, called say OPEN, of all known but unsearched nodes. This will be every single "cousin" at the current level down.
If there is a high Branching factor, OPEN grows very big.
e.g. Every node has B children. Down at level n, there will be Bⁿ nodes.
When Breadth-first gets down to level n, all of these will be added to OPEN before it examines the first one.
See trace, step 4.
Breadth-first good if goal is fairly small number of steps away. Not good if goal is large number of steps away with high branching factor.
e.g. Breadth-first not possible in Chess.
Depth-first memory cost much lower - does not have to keep all nodes across a given level on open list.
Depth-first good if path to goal will be long. Won't waste time searching shallow states. Gets deep into state space quickly. But may miss optimal path.

3.2.4 - Iterative deepening depth-first search

   Depth-first with bound of 1 level.
   If goal not found, depth-first with bound of 2.
   If goal not found, depth-first with bound of 3.
   ...

Guaranteed to find shortest path.

Image above.

Depth-first search (problem - path down might never end)

  A, B, E, K, S, (backtrack to E), L, T, (backtrack to B), F, M, ...

Breadth-first search (problem - has to hold exponentially growing number of cousins in memory)

  A, B, C, D, (recover B from memory), E, F, (recover C), G, H, (recover D), I, J, (recover E), K, L, ...

Iterative deepening depth-first search (low memory, limited path length)

 A, B, C, D
 A, B, E, (backtrack to B), F, (backtrack to A), C, G, (backtrack to C), H, (backtrack to A), D, I, (backtrack to D), J
 A, B, E, K, (backtrack), L, (backtrack), ...
 ...

Uninformed search

These are all Uninformed search algorithms.
Generic algorithms for any search problem.
No problem-specific information.
No problem-specific heuristic to guide/restrict search.