Vincec's Dimension

Algorithm Review Notes - Search Methods

Word count: 548 / Reading time: 3 min
2018/10/04 Share

Uninformed / Blind

  • Completeness: Guarantee to find a solution.
  • Optimality: Guarantee to find a least cost path.
  • b - max branching factor
  • d - depth of the least-cost solution
  • m - max depth of the state-space(may infinity).

Completeness:

  • Yes, for graph search version(check visited status) in finite space(bm).
  • For finite of m, DFS will still stuck when b is infinite.

Optimality:

  • No, in both graph or tree.

Time Complexity:

  • O(bm) / O(V+E)

Space Complexity:

  • O(b*m)

Completeness:

  • Yes, when b finite

Optimality:

  • Yes, when constant step cost

Time Complexity:

  • O(bd) / O(V+E)

Space Complexity:

  • Same as Time Complexity

UCS (Uniform Cost Search): BFS Enhanced with lowest path costs first

Only test from start to goal (Dijkstra, no goal state unitl all nodes are removed to get shortest paths to all nodes.)

Completeness:

  • Yes, when steps have non-zero costs

Optimality:

  • Yes, for non-decrease path cost

Time Complexity:

  • O(b1+⌊C/ ͼ ⌋), will be greater than O(bd), C is cost of optimial solution & every action costs at least ͼ.

Space Complexity:

  • Same as Time Complexity

Depth limited

Completeness:

  • Yes when cutoff appropriately

Optimality:

  • No.

Time Complexity:

  • O(bl), (l for depth cutoff)

Space Complexity:

  • O(b*l), (l for depth cutoff)

Combine DFS and BFS

Completeness:

  • Yes, if l >= d.

Optimality:

  • Yes, when constant step(1) cost (like BFS)

Time Complexity:

  • O(bd) (like BFS)

Space Complexity:

  • O(b*d)

Both search from forward and backwards.(Problem: must be an efficient way to check the given node belongs to same tree)

Need a hash table, T for comparsion is O(1)

Completeness:

  • Yes.

Optimality:

  • Yes.

Time Complexity:

  • 2*O(bd/2) = O(bd/2)

Space Complexity:

  • O(bm/2)

Comparison

  • BFS: Completeness, will not stuck only wait long.
  • DFS: Space, but will stuck and non-complete.
  • IDS: Same as BFS but advanced in Space.
  • Graph Search vs Tree Search: Graph search has a explored_set to check visited node avoid stuck.

Informed / Heuristic

Estimation Function

  • h(n) = estimate of cost from n to goal

Completeness:

  • No, will stuck in loop.

Optimality:

  • No.

Time Complexity:

  • Worse: O(bm)

Space Complexity:

  • Same as Time Complexity
  • Faster time less space.
  • Admissible Heursitics, (never over estimated).
  • Heursitics Consistent - nondecreasing along every path.
  • Admissible Heursitics can be Inconsistent, Consistent Heursitics must Admissible.

Estimation Function

  • f(n) = g(n) + h(n), g(n): estimated cost, h(n): estimated cost on path.
  • UCS: f(n) = g(n), when h(n) = 0, same as UCS / UCS is a special case of A Star

Completeness:

  • Yes, if no infinite nodes with f(n) < G(n)

Optimality:

  • No guarantee.
  • Yes, if admissible in Tree Search / consistent in Graph Search, if no infinite nodes with f(n) < G(n)

Time Complexity:

  • Exponential
  • Could be f(n) < C (expands all nodes) / f(n) = C (expands some nodes) / f(n) > C* (expands no nodes)

Space Complexity:

  • Exponential
  • Iterative-deepening A (IDA)
  • Recursive Best First Seach (RBFS)
  • Simple Memory-bounded A ((S)MA)

Minimax

Completeness:

  • Yes.

Optimality:

  • Yes.

Time Complexity:

  • O(bm)

Space Complexity:

  • O(b*m) or O(m)

Reference

  • slides
CATALOG
  1. 1. Uninformed / Blind
    1. 1.0.1. DFS (Depth First Search)
      1. 1.0.1.1. Completeness:
      2. 1.0.1.2. Optimality:
      3. 1.0.1.3. Time Complexity:
      4. 1.0.1.4. Space Complexity:
    2. 1.0.2. BFS (Breadth First Search)
      1. 1.0.2.1. Completeness:
      2. 1.0.2.2. Optimality:
      3. 1.0.2.3. Time Complexity:
      4. 1.0.2.4. Space Complexity:
    3. 1.0.3. UCS (Uniform Cost Search): BFS Enhanced with lowest path costs first
      1. 1.0.3.1. Completeness:
      2. 1.0.3.2. Optimality:
      3. 1.0.3.3. Time Complexity:
      4. 1.0.3.4. Space Complexity:
    4. 1.0.4. Depth limited
      1. 1.0.4.1. Completeness:
      2. 1.0.4.2. Optimality:
      3. 1.0.4.3. Time Complexity:
      4. 1.0.4.4. Space Complexity:
    5. 1.0.5. IDS or IDDFS (Iterative Deepening Search / Iterative Deepening Depth First Search)
      1. 1.0.5.1. Completeness:
      2. 1.0.5.2. Optimality:
      3. 1.0.5.3. Time Complexity:
      4. 1.0.5.4. Space Complexity:
    6. 1.0.6. Backward Search
    7. 1.0.7. Bidirectional Search
      1. 1.0.7.1. Completeness:
      2. 1.0.7.2. Optimality:
      3. 1.0.7.3. Time Complexity:
      4. 1.0.7.4. Space Complexity:
  2. 1.1. Comparison
  • 2. Informed / Heuristic
    1. 2.0.1. Greedy Best First Search
      1. 2.0.1.1. Estimation Function
      2. 2.0.1.2. Completeness:
      3. 2.0.1.3. Optimality:
      4. 2.0.1.4. Time Complexity:
      5. 2.0.1.5. Space Complexity:
    2. 2.0.2. A* Search (A Star Search)
      1. 2.0.2.1. Estimation Function
      2. 2.0.2.2. Completeness:
      3. 2.0.2.3. Optimality:
      4. 2.0.2.4. Time Complexity:
      5. 2.0.2.5. Space Complexity:
  • 2.1. Memory-Bounded Heuristic Search
  • 3. Minimax
    1. 3.0.0.1. Completeness:
    2. 3.0.0.2. Optimality:
    3. 3.0.0.3. Time Complexity:
    4. 3.0.0.4. Space Complexity:
  • 4. Reference