CSCE 420 Lecture 4

« previous | Thursday, January 24, 2013 | next »

Review of BFS and DFS

For a tree with branching factor $b$, max height $m$, and a solution at worst-case position at depth $d$

Table 3.21

	BFS	DFS	UC	ID
Time	$O(b^d)$	$O(b^m)$	$O\left(b^{1+\frac{c^{*}}{ϵ}}\right)$	$O(b^d)$
Space	$O(b^d)$	$O(bm)$	$O\left(b^{1+\frac{c^{*}}{ϵ}}\right)$	$O(bd)$
Completeness	yes	no	yes	yes
Optimality	yes	no	yes	yes

Uniform Cost Algorithm

Same basic algorithm as BFS, but use a Priority Queue data structure instead.

Explores nodes in search space in order of increasing cost.

def graph_search algorithm, problem
  node = make_node initial_state
  frontier = case algorithm
    when :bfs then Queue[node]
    when :dfs then Stack[node]
    then :uniform_cost then PriorityQueue[node] {|node| node.path_cost}
  end

  loop do
    return false if frontier.empty?
    node = frontier.remove
    return child if problem == :uniform_cost
    action.each do |a|
      child = a.target
      return child if problem in [:bfs, :dfs] and goal_test child
      frontier.add child
    end
  end
end

This algorithm implies positive edge costs $c$, the smallest of which is $0<ϵ\le c$

Complexity

Suppose optimal goal has cost $c^{*}=c(n^{*})$. How many other nodes do we have to search before we arrive at a goal node?

Both time and space complexity:

$O\left(b^{1+\frac{c^{*}}{ϵ}}\right)$

Correctness

proof by contradiction. Suppose UC finds a suboptimal goal $n$ such that there exists a better node $n^{\prime }$: $c(n)>c(n^{\prime })$.

$n$ has a parent $p$ such that $c(p)<c(n)$.

By the graph separation property, there must have been some node

$s$

on the path from the root to

$n$

such that

$c(s)<c(p)$

. In that case,

$s$

would have been pulled before

$n$

. Contradiction.

Q.E.D.

Graph Separation Property

in graph search, frontier separates the visited/explored part of search space from the unvisited/unexplored space. Therefore, for any node $n$, there is always some node $s$ in the frontier that is on the path from the root node to $n$. Each of these nodes have the property $c(s_i)<c(s_{i+1})$.

Iterative Deepening

To obtain space complexity of DFS without the threat of infinite depth searchi, we could implement a depth-limited search (DLS) that caps the maximum search depth:

def depth_limited_search init, oper, goal_test, limit
  frontier = Stack[init]
  until frontier.empty?
    node = frontier.pop
    return child if goal_test node
    oper(node).each {|child| frontier.push child} if depth(node) < limit
  end
  false
end

Iterative deepening algorithm is a wrapper for depth_limited_search:

 def iterative_deepening init, oper, goal_test
  limit = 0
  loop do
    result = depth_limited_search init, oper, goal_test, limit
    return result if result
    limit += 1
  end
end