CSCE 420 Lecture 3

« previous | Tuesday, January 22, 2013 | next »

Uninformed Search

(c.f. informed searches: intelligent/heuristic search)

Search a space without any knowledge; efficiency derived from implementation

many problems can be formulated as search problems: use a graph where

nodes are states of the environment and
edges are actions we can take to change the state of the world.

Example problems:

planning
games or puzzles
navigation
robotics
VLSI (Chip design)
parsing Natural Language
learning

Terminology

initial state: The starting state of the world
operators: actions or successor functions that change the state; $Op(S)\mapsto S$ , where the RHS may be a subset of successor states
discrete actions: finite/countable number of states; (c.f. continuous)
application: expanding a node; generating child node(s)
state space: reachable set of states
goals: 1. simply enumerated (specific target); 2. criteria/specification (defining target(s) by a set of rules; 3. subset of a space: $G\subset S$; 4. minimizing a path cost function to find the "best" goal; 5. find best goal that maximizes some score/utility

Example

Fox, Chicken, Grain:

All 3 on one side of a river, how to get them all across by following the rules:

Fox and Chicken cannot be left together or Fox will eat Chicken
Chicken and Grain cannot be left together or Chicken will eat Grain

Solution:

← Chicken
(empty) →
← Fox
Chicken →
← Grain
(empty) →
← Chicken

DFS and BFS

def graph_search algorithm, problem

 node = make_node initial_state
 frontier = case algorithm
   when :bfs then Queue[node]
   when :dfs then Stack[node]
 end

 loop do
   return false if frontier.empty?
   node = frontier.remove
   action.each do |a|
     child = a.target
     return child if goal_test child
     frontier.add child
   end
 end

end

When do we use each algorithm?

DFS can search down infinite paths if loops cannot be detected (track visited states; graph search)

Time Complexity Analysis

Counting number of goal_test() calls.

For solution at depth $d$ (all the way to one side) in a tree of branching fator $b$ with max height $m$ :

${\text{BFS}}\in O(b^{d})$ average-case
${\text{DFS}}\in O(b^{m})$ worst-case

Space Complexity

Spaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaace!

${\text{BFS}}\in O(b^{d+1})$ average-case
${\text{DFS}}\in O(b\,m)$ average-case