Omar Arif

UNINFORMED SEARCH STRATEGIES Reading: Chapter 3

EXAMPLE: ROMANIA
vOn holiday in Romania; currently in Arad.
vFlight leaves tomorrow from Bucharest
vFormulate goal:
vbe in Bucharest
v
vFormulate problem:
vstates: various cities
vactions: drive between cities
v
vFind solution:
vsequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
v
PROBLEM FORMULATION

A problem is defined by five items:

1. initial state e.g., "at Arad”
2. Actions A description of possible actions. Given a state s, Actions(s) returns set of
actions that can be executed in s
3. Transition Model: A description of what action does. Specified by a function Result(s,a) that returns the state
that results from doing action a in state s.
4. Goal test Determines whether a given state is a goal. goaltest(s) à T|F
5. path cost
­ e.g., sum of distances, number of actions executed, etc.
­ c(s,a,ś) is the step cost, assumed to be ≥ 0
A solution is a sequence of actions leading from the initial state to a goal state
Set of all states is called state space
TREE SEARCH ALGORITHM
Tree-search (problem p) returns path
frontier = [p.initial]
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
if p.goaltest(s); return path
for a in p.action(s)
add [path+p.result(s,a)]to frontier
GRAPH SEARCH ALGORITHM
Graph-search (problem p) returns path
frontier = [p.initial], explored = {}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
if s is not in explored list: add s to explored list
if goaltest(s); return path
for a in p.action(s)
if p.result(s,a) not in explored list:
frontier.update([path+p.result(s,a)])
Where Frontier.update(path):
if path in not in frontier, add it to frontier
else add lower-cost path to frontier
GRAPH SEARCH ALGORITHM
Different Search Strategies
Graph-search (problem p) returns path differ in the way elements are
removed from the frontier
frontier = [p.initial], explored = {}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
if s is not in explored list: add s to explored list
if goaltest(s); return path
for a in p.action(s)
if p.result(s,a) not in explored list:
frontier.update([path+p.result(s,a)])
SEARCH STRATEGIES
A search strategy is defined by picking the order of node
expansion
Strategies are evaluated along the following dimensions:
­ completeness: does it always find a solution if one exists?
­ time complexity: How long does it take to find solution?
­ space complexity: How much memory is needed to perform search?
­ optimality: does it always find a least-cost solution?
Time and space complexity are measured in terms of
­ b: maximum branching factor of the search tree
­ d: depth of the least-cost solution
­ m: maximum depth of the state space (may be ∞)
UNINFORMED SEARCH STRATEGIES
nUninformed search strategies use only the information
available in the problem definition
nBreadth-first search
nUniform-cost search
nDepth-first search
nDepth-limited search
nIterative deepening search
BREADTH-FIRST SEARCH
nThe BFS begins at the initial state/node s, and inspects all the neighboring nodes.
Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which
were unvisited, and so on.
BREADTH-FIRST SEARCH
nImplementation:
nUse FIFO queue to implement frontier, i.e., paths are removed based on first in first out.
BREADTH-FIRST SEARCH
BREADTH-FIRST SEARCH
BREADTH-FIRST SEARCH
PROPERTIES OF BREADTH-FIRST SEARCH

Complete? Yes (if b is finite)

Optimal? Yes (if cost = 1 per step)
Time? 1+b+b2+b3+… +bd + bd+1 = O(bd+1)
Space? O(bd+1)

Space is the bigger problem

BREADTH-FIRST SEARCH

15
UNIFORM-COST SEARCH
nExpand least-cost unexpanded node
nImplementation:
nUse priority queue = queue ordered by path cost

nEquivalent to breadth-first if step costs all equal

EXAMPLE: ROMANIA – UNIFORM COST
PROPERTIES OF UNIFORM-COST SEARCH
Complete? Yes, if step cost greater than small positive
constant

Optimal? Yes – nodes expanded in the order of

increasing path cost

Time? O(b1+ceiling(C*/ ε)) where C* is the cost of the

optimal solution, and ε is the least cost an action can
have

Space? O(b1+ceiling(C*/ ε))

DEPTH-FIRST SEARCH
nExpand longest unexpanded node
nImplementation:
nUse LIFO queue to implement frontier, i.e., paths are removed from frontier
based on Last in first out.
DEPTH-FIRST SEARCH
nExpand longest/deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
DEPTH-FIRST SEARCH
nExpand deepest unexpanded node
PROPERTIES OF DEPTH-FIRST SEARCH

nComplete? No: fails in infinite-depth spaces, spaces with loops

à Graph search is complete in finite spaces

nOptimal? No

nTime? O(bm): terrible if m is much larger than d

nSpace? O(bm) for tree-search, i.e., linear space! For graph-search

space complexity is same as BFS
SUMMARY OF ALGORITHMS
EXAMPLE 1
a) What path would breadth-first graph search return for this
problem?

b) What path would uniform cost graph search return for this
search problem?

c) What path would depth-frist graph search return for this

search problem?
EXAMPLE 1
a) What path would breadth-first graph search return for this
problem?
S-G
b). What path would uniform cost graph search return for this
search problem?
S-A-C-G
c). What path would depth-first graph search return for this
search problem?
S-G
[if you add elements to frontier in reverse alphabetical order
then the path returned would be: S-A-B-D-G]
 Consider the search space below, where S is the start node and
EXAMPLE 2 G1, G2, and G3 satisfy the goal test. Arcs are labeled with the
cost of traversing them (ignore the numbers reported inside
nodes)

Breadth First Search

Goal state reached _________________________

Order of states added to the explored list _________________________

Uniform-Cost Search

Goal state reached _________________________

Order of states added to the explored list _________________________

Depth First Search

Goal state reached _________________________

Order of states added to the explored list _________________________

 Breadth First Search (Graph search)

EXAMPLE 2
 Consider the search space below, where S is the start node and
EXAMPLE 2 G1, G2, and G3 satisfy the goal test. Arcs are labeled with the
cost of traversing them (ignore the numbers reported inside
nodes)

Breadth First Search

Goal state reached ________G1_________________

Order of states added to the explored list ______S A B C E G1________

Uniform-Cost Search

Goal state reached ____G1_____________________

Order of states added to the explored list __S B C D A E G1_

Depth First Search

Goal state reached ______G3___________________

Order of states added to the explored list _____S C G3____________________

EXAMPLE 3
a is the start state and f is the goal state. Would you prefer BDS or DFS in this case?
EXAMPLE 3
a is the start state and f is the goal state. Would you prefer BDS or DFS in this case?

DFS:
• Tree search
• DFS can stuck in infinte loop
[Incomplete]
• DFS is sensitive to the ordering of
nodes
• Graph search
• Will return the solution but the
solution may not be optimal.
BFS:
• Complete and optimal
 EXAMPLE 4 1. What path will BFS tree search return? (Show your
solution)

2. What path will UCS tree search return? (Show your

solution)

3. What path will UCS graph search return? (Show your

solution)

4. For UCS graph search, write the ordered sequence of states

put on the explored list

5. In what scenario uniform cost search and breadth-first

search result in the same path? Explain briefly.

Note:Ties are broken alphabetically

 EXAMPLE 4 1. What path will BFS tree search return? (Show your
solution)
SBG
2. What path will UCS tree search return? (Show your
solution)
SADG
3. What path will UCS graph search return? (Show your
solution)
SADG
4. For UCS graph search, write the ordered sequence of states
put on the explored list
SBADCG
5. In what scenario uniform cost search and breadth-first
search result in the same path? Explain briefly.
When path cost is same for all paths

Note:Ties are broken alphabetically

 EXAMPLE 4

Note:Ties are broken alphabetically

QUESTIONS