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)

• 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

• 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)

• Yes.

• Yes.

#### Time Complexity:

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

• 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.

• No.

• Worse: O(bm)

#### Space Complexity:

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

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

• Yes.

• Yes.

• O(bm)

#### Space Complexity:

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

• slides

Author: VINCEC