UoL CS Notes
Menu

Properties of Searches

COMP111 Lectures

For all algorithms there are certain properties that they can be evaluated against:

  • Completeness
    • Does the algorithm always find a solution if one exists?

    This is true for BFS but not for DFS as cycles can stop depth first if there is a loop.

  • Optimality
    • Does the algorithm always find a shortest path or one of lowest cost?

    Yes for BFS but no for DFS (neither take into account cost, just steps.)

  • Time Complexity
    • What are the number of paths generated?/How long will it take to compute?

    Harder to answer. This will need to be computed

  • Space Complexity
    • What are the maximum number of paths in memory (in frontier)?

    This will always be smaller or equal to the time complexity but it is still harder to answer.

Time & Space Complexity

Time and space complexity are measured in terms of:

  • $b$ - Maximum branching factor
    • The maximal number of successor states of a state in the state space.
  • $d$ - Depth of the optimal solution
    • The length of the shortest path from the start state to a goal state.
  • $m$ - Maximum depth of the state space
    • the length of the longest path in the state space (may be $\infty$ to to loops)

Example 1 - 8 Puzzle

  • $b$ (maximum branching factor) is 4
  • $d$ (optimal solution) is 31
  • $m$ (longest path) is $\infty$ as there are cycles

Example 2 - Holiday in Romania

  • $b=4$
  • $d=3$
  • $m=\infty$

The number of paths of length $d$ in a search tree with maximum branching factor $b$ is at most $b^d$.

The number of paths of length at most $d$ in a search tree with maximum branching factor $b$ is at most $1+b+b^2+\ldots + b^d$.

  • Time complexity
    • If the shortest path to a goal state has length $d$ then the worst case BFS will look at: \(1+b+B^2+\ldots +b^d\) paths before reaching a goal state.
  • Space complexity
    • If the shortest path to a goal state has length $d$, then in the worst case the frontier can contain $b^d$ paths and so the memory requirement is $b^d$.

Complexity

Depth Paths Time
0 1 1 msec
1 11 .01 sec
2 111 .1 sec
4 11,111 11 sec
6 10^6 18 sec
8 10^8 31 hours
10 10^10 128 days
12 10^12 35 years

Example of combinatorial explosion of a BFS at 1000 states/sec.

  • Not complete - No guarenteed to find a solution
  • Not optimal - Solution is not guaranteed to be the shortest path.
  • Time Complexity
    • If the length of the longest path from the start state is $m$, then the worst case DFS will look at: \(1+b+b^2+\ldots +b^m\) This may be an issue as $m$ is infinite in many problems.
  • Space Complexity
    • If the length of the longest path starting at a goal state is $m$, then the worst case the frontier can contain: \(b\times m\) paths. if $m$ is infinite, then the space requirement is infinite in the worst case. But if DFS finds a path to the goal state, then memory requirement is much less than for BFS.

Summary

  • DFS is complete ut expensive
  • DFS is cheap in space complexity but incomplete