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; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} (all the way to one side) in a tree of branching fator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} with max height Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{BFS} \in O(b^d)} average-case
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{DFS} \in O(b^m)} worst-case

Space Complexity

Spaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaace!

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{BFS} \in O(b^{d+1})} average-case
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{DFS} \in O(b \, m)} average-case