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^{*}}{\epsilon }}}\right)$	$O(b^{d})$
Space	$O(b^{d})$	$O(b\,m)$	$O\left(b^{1+{\frac {c^{*}}{\epsilon }}}\right)$	$O(b\,d)$
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<\epsilon \leq 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^{*}}{\epsilon }}}\right)$

Correctness

proof by contradiction. Suppose UC finds a suboptimal goal $n$ such that there exists a better node $n'$: $c(n)>c(n')$.

$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