Searching
• Examine different possible sequences of actions &
states, and come up with specific sequence of
operators/actions that will take you from the initial
state to the goal state
–Given a state space with initial state and goal state, find
optimal sequence of actions leading through a sequence
of states to the final goal state
• Searching in State Space
– select min-cost/max-profit node/state in the state space,
– test whether the state selected is the goal state or not,
– if not, expand the node further to identify its successor.
Search Tree
• The searching process is like building the search tree that is
super imposed over the state space
– A search tree is a representation in which nodes denote paths and
branches connect paths. The node with no parent is the root node. The
nodes with no children are called leaf nodes.
Example: Route finding Problem
• Partial search tree for route finding from Sidist Kilo to Stadium.
goal test
(a) The initial state SidistKilo
SidistKilo
(b) After expanding Sidist Kilo generating a new state
AratKilo Giorgis ShiroMeda
choosing one SidistKilo
option
(c) After expanding Arat Kilo AratKilo Giorgis ShiroMeda
MeskelSquare Piassa Megenagna
Search algorithm
• Two functions needed for conducting search
– Generator (or successors) function: Given a state and action,
produces its successor states (in a state space)
– Tester (or IsGoal) function: Tells whether given state S is a
goal state IsGoal(S) True/False
– IsGoal and Successors functions depend on problem domain.
• Two lists maintained during searching
– OPEN list: stores the nodes we have seen but not explored
– CLOSED list: the nodes we have seen and explored
– Generally, search proceeds by examining each node on the
OPEN list, performing some expansion operation that adds its
children to the OPEN list, & moving the node to the CLOSED list.
• Merge function: Given successor nodes, it either append,
prepend or arrange based on evaluation cost
• Path cost: function assigning a numeric cost to each path;
either from initial node to current node and/or from current
node to goal node
Search algorithm
• Input: a given problem (Initial State + Goal state + transit
states and operators)
• Output: returns optimal sequence of actions to reach the goal.
function GeneralSearch (problem, strategy)
open = (initialState); //put initial state in the List
closed = {}; //maintain list of nodes examined earlier
while (not (empty (open)))
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
succ = Successors (f)
left = not-in-closed (succ, closed );
open = merge (rest(open), left); //append or prepend l to open
list
end while
return ('fail')
end GeneralSearch
Algorithm Evaluation:
Completeness and Optimality
• Is the search strategies find solutions to problems with
no solutions
– Is it produces incorrect solutions to problems
• Completeness
– Is the algorithm guarantees in finding a solution whenever
one exists
– Think about the density of solutions in space and evaluate
whether the searching technique guaranteed to find all
solutions or not.
• Optimality
– is the algorithm finding an optimal solution; i.e. the one with
minimum cost
• how good is our solution?
Algorithm Evaluation: Time & Space
Tradeoffs
• With many computing projects, we worry about:
– Speed versus memory
– Time complexity: how long does it take to find a solution
– Space complexity: how much space is used by the
algorithm
• Fast programs can be written
– But they use up too much memory
• Memory efficient programs can be written
– But they are slow
• We consider various search strategies
– In terms of their memory/speed tradeoffs
Searching Strategies
•Search strategy gives the order in which the search
space is examined
•Uninformed (= blind) search
– they do not need domain knowledge that guide them towards
the goal
– Have no information about the number of steps or the path
cost from the current state to the goal
– It is important for problems for which there is no additional
information to consider
•Informed (= heuristic) search
– have problem-specific knowledge (knowledge that is true from
experience)
– Have knowledge about how far are the various state from the
goal
– Can find solutions more efficiently than uninformed search
Search Methods:
• Uninformed search
– Breadth first
– Depth first
– Uniform cost, …
– Depth limited search
– Iterative deepening
– etc.
• Informed search
– Greedy search
– A*-search
– Iterative improvement,
– Constraint satisfaction
– etc.
Breadth first search
•Expand shallowest unexpanded node,
–i.e. expand all nodes on a given level of
the search tree before moving to the next
level
•Implementation: use queue data
structure to store the list:
–Expansion: put successors at the end of
queue
–Pop nodes from the front of the queue
•Properties:
–Takes space: keeps every node in
memory
–Optimal and complete: guarantees to
find solution
Algorithm for Breadth first search
function BFS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed );
open = merge ( rest(open), l); //append to the
list
}
return ('fail')
}
Uniform cost Search
•The goal of this technique is to find the shortest path to the
goal in terms of cost.
–It modifies the BFS by always expanding least-cost
unexpanded node
•Implementation: nodes in list keep track of total path
length from start to that node
–List kept in priority queue ordered by path cost
A
S S S
1 10 S
5 B 5
S G 0 A B C A B C A B C
1 5 15 5 15 15
G G G
15 5
11 11 10
C
•Properties:
–This strategy finds the cheapest solution provided the cost of
a path must never decrease as we go along the path
g(successor(n)) ≥ g(n), for every node n
–Takes space since it keeps every node in memory
Algorithm for Uniform Cost search
function uniform_cost (problem){
open = (C_0); //put initial state C_0 in the List
g(s) = 0;
closed = {}; /maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed );
g(f,li) = g(f) + c(f,li);
open = merge(rest(open), l, g(f,li)); //keep the open list sorted in
ascending order by edge cost
}
return ('fail')
}
Depth-first search
•Expand one of the node at the deepest
level of the tree.
–Only when the search hits a non-goal dead
end does the search go back and expand
nodes at shallower levels
•Implementation: treat the list as stack
–Expansion: push successors at the top of
stack
–Pop nodes from the top of the stack
•Properties
–Incomplete and not optimal: fails in infinite-
depth spaces, spaces with loops.
• Modify to avoid repeated states along the path
–Takes less space (Linear): Only needs to
remember up to the depth expanded
Algorithm for Depth first search
function DFS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed );
open = merge ( rest(open), l); //prepend to the
list
}
return ('fail')
}
Iterative Deepening Search (IDS)
• IDS solves the issue of choosing the best depth limit by trying
all possible depth limit:
–Perform depth-first search to a bounded depth d, starting at d = 1 and
increasing it by 1 at each iteration.
Example: for route finding problem we can take the diameter of
the state space. In our example, at most 9 steps is enough to
reach any node
• This search combines the benefits of DFS and BFS
–DFS is efficient in space, but has no path-length guarantee
–BFS finds min-step path towards the goal, but requires memory space
–IDS performs a sequence of DFS searches with increasing depth-cutoff
until goal is found
Limit=0 Limit=1 Limit=2
Algorithm for IDS
function IDS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not reached maxDepth) {
while (not (empty (open))) {
f = remove_first(open);
if (IsGoal (f)) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed);
if (depth(l) < maxDepth) then
open = merge (rest(open), l); //prepend to
the list
}
}
return ('fail')
}
Bidirectional Search
• Simultaneously search both forward from the initial
state to the goal and backward from the goal to the
initial state, and stop when the two searches meet
somewhere in the middle
– Requires an explicit goal state and invertible operators (or
backward chaining).
– Decide what kind of search is going to take place in each
half using BFS, DFS, uniform cost search, etc.
Start Goal
Bidirectional Search
• Advantages:
– Only need to go to half depth
– It can enormously reduce time complexity, but is not
always applicable
– bd/2 +bd/2< bd
– bd/2 +bd/2=bd
– b=2, d=4
• Difficulties
– Do you really know solution? Unique?
– Cannot reverse operators
– Memory requirements may be important: Record all
paths to check they meet
• Memory intensive
• Note that if a heuristic function is inaccurate, the
two searches might miss one another.
Comparing Uninformed Search
Strategies Complete Optimal Time Space
complexity complexity
Breadth first search yes no O(bd) O(bd)
Depth first search no no O(bm) O(bm)
Uniform cost search yes yes O(bd) O(bd)
Depth limited search if l >= d no O(bl) O(bl)
Iterative deepening yes no O(bd) O(bd)
search
bi-directional search yes yes O(bd/2) O(bd/2)
• b is branching factor,
• d is depth of the shallowest solution,
• m is the maximum depth of the search tree,
• l is the depth limit
Exercise: Uninformed Search Strategies
• Assume that node 3 is the initial state and
node 5 is the goal state
Exercise: Uninformed Search Strategies
S
1 5 8
A B C
3 9
7 4 5
D E G