AnIntroduction

to Artificial
Dr. Sahar Kamal Intelligence
Searching Strategies

Lecture 3
Search Strategies
➢ Breadth-first search
Uninformed ➢ Depth-first search
Some ➢ Uniform Cost search
path ➢ Depth-limited search
➢ Iterative deepening search
➢ Bi-directional search

➢ Hill Climbing search

Search ➢ Beam search
Informed ➢ Best-first search
Strategies
Optimal ➢ British museum search
Informed ➢ Branch& Bound search
path (Heuristic) ➢ Dynamic programming
➢ A* search

➢ Minimax search
Games ➢ Alpha-beta search 38
Uninformed search
strategies
Uninformed (blind):
You have no clue whether one non-goal state is better than
any other. Your search is blind. You don’t know if your current
exploration is likely to be fruitful.
Various blind strategies:
Breadth-first search
Uniform-cost search
Depth-first search
Iterative deepening search (generally preferred)
Bidirectional search (preferred if applicable)

4
Search strategy evaluation
A search strategy is defined by the order of node expansion

Strategies are evaluated along the following dimensions:

completeness: does it always find a solution if one exists?

time complexity: number of nodes generated
space complexity: maximum number of nodes in memory
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 ∞)

5
Queue for Frontier

FIFO (First In, First Out)

Results in Breadth-First Search
LIFO (Last In, First Out)
Results in Depth-First Search
Priority Queue sorted by path cost so far
Results in Uniform Cost Search
Iterative Deepening Search uses Depth-First

6
General Search Problem
A Basic Search Problem
• Suppose we want to find some path from one
city to another using a highway map as the one
shown in the following figure:

For Example, If we will start at city S (starting point)

and will end at city G (Goal).
Net Search and Tree Search
(The Knowledge Representation)

Search Tree

Network
(graph)

• A net is converted into a search tree by tracing out all possible

paths until we can not extend one of them without creating a
loop. All loop paths (such as S-A-D-S-A-D..) are eliminated
Terminology
• Node (S) is the root node.
• Node (G) is the goal node.
• Nodes (C, D, G, C, G, C, G, A, C,G ) are leaf nodes.
• The branching factor (b): of a node equals the number of its
children.
• The complete path is a path that reaches the goal.
• A partial path: is a path that does not reach the goal.
• Expanding a node: is the determination of the children of that
node.
• Size of the search tree:
– if the average number of children of nodes in a search tree is
b= branching factor.
– And if the depth of this tree is d.
– Then the total number of nodes in this search tree= bm
The Search Space
• Search tree (The knowledge)
– generated as the search space is traversed
– a search tree is generated by generating search nodes by successively
expanding states starting from the initial state as the root
– expansion of nodes
• as states are explored, the corresponding nodes are expanded by applying
the successor function.
• A state can be expanded by generating all states that can be reached from
this state by applying a legal operator to it
– a successor function that returns all states produced by applying a single
legal operator. It generates a new set of (child) nodes

• search strategy (The technique)

– the tree specifies possible paths through the search space
– determines the selection of the next node to be expanded
– can be achieved by ordering the nodes in the fringe
• e.g. queue (FIFO), stack (LIFO), “best” node w.r.t. some measure
Exercise: Draw the Search Tree for this Graph
1
A D
4 3

1 1 1 3

S 5 C 2 G
3 2 0

1 3 3 4

B E
2 1
2

• the graph describes the search (state) space

– each node in the graph represents one state in the search space
• e.g. a city to be visited in a routing or touring problem
• this graph has additional information
– names and properties for the states (e.g. S, 3)
– links between nodes, specified by the successor function
• properties for links (distance, cost, name, ...)
Route Finding
• states
– locations
• initial state
– starting point
• successor function (operators)
– move from one location to another
• goal test
– arrive at a certain location
• path cost
– may be quite complex
• money, time, travel comfort, scenery, ...
Search Strategies
• A search strategy is defined by picking the
order of node expansion
• Two major strategies:
– Depth-first
– Breadth-first
More Information Improves
(Guides) Search

• Uninformed Search
– Also called blind, exhaustive or brute-force
– Makes use of no information about the problem
– May be quite inefficient
• Informed Search
– Also called heuristic or intelligent
– Uses information about the problem to guide the search
– Usually guesses the distance to a goal state
– Not always possible (depends on whether there is
information or not)
1. Breadth-First Search
• All nodes at a particular depth are expanded
before any below them
• 2 questions:
– What is the algorithm?
– How does BFS perform?
• Completeness
• Optimality
• Complexity Breadth-first search tress after
0, 1, 2, and 3 node expansions (b=2, d=2)
1. Breadth-first search

• Expand shallowest unexpanded node first

• Implementation:
– fringe is a FIFO queue, i.e., new successors go at
end
–
1. Breadth-first search

• Expand shallowest unexpanded node first

• Implementation:
– fringe is a FIFO queue, i.e., new successors go at
end
–
1. Breadth-first search
• Expand shallowest unexpanded node first
• Implementation:
– fringe is a FIFO queue, i.e., new successors go at
end
–
1. Breadth-first search

• Expand shallowest unexpanded node first

• Implementation:
– fringe is a FIFO queue, i.e., new successors go at
end
–
Breadth First Search Example

• Search all first level children;

• If goal not found, search all next level children

Note: All numbers refer to order visited in search.

1. Breadth-first Algorithm
Breadth-first-search
1. Form one-element List consisting of the root node.
2. Until the List is empty or the goal has been reached,
determine if the first element in the List is the Goal node.
a. If the first element is the Goal node, do nothing
b. If the first element is not the Goal node, remove
the first element from the front of the List and add
its children, if any, to the BACK of the List
3. If the Goal node has been found, announce success,
otherwise announce failure.
1. Breadth-first Algorithm
Breadth-first-search
open = [start];
closed = [];
while open  []
remove leftmost state from open, call it X;
put X on closed;
if X is goal return SUCCESS
else
generate children of X;
discard children if on closed or open;
put remaining children on right end of open;
return FAIL

Note: List ordering is a queue

Assume goal node at level d with constant branching factor b

Time complexity (measured in #nodes generated)

➢1 (1st level ) + b (2nd level) + b2 (3rd level) + … + bd (goal level)
+ (bd+1 – b) = O(bd+1)

This assumes goal on far right of level

Space complexity
➢At most majority of nodes at level d + majority of nodes at
level d+1 = O(bd+1)
➢Exponential time and space

Features
Completeness: Yes
Time complexity: bd+1
Space complexity: bd
Optimality: No
2. Depth First Search

❑ How does depth first search operate?

❑ How would we implement it?
❑ Performance:
•Completeness
•Optimality
•Space Complexity
•Time Complexity
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search

• Expands deepest unexpanded node

• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
2. Depth-first search
• Expands deepest unexpanded node
• Implementation:
– fringe = LIFO queue, i.e., put successors at
front
–
Depth-first search

Expand deepest unexpanded node

Implementation:
frontier = LIFO queue, i.e., put successors at front

CMPT 310 - Blind Search 35

Depth-first search

Expand deepest unexpanded node

Implementation:
frontier = LIFO queue, i.e., put successors at front

CMPT 310 - Blind Search 36

Depth-first search

Expand deepest unexpanded node

Implementation:
frontier = LIFO queue, i.e., put successors at front

CMPT 310 - Blind Search 37

Depth-first search

Expand deepest unexpanded node

Implementation:
frontier = LIFO queue, i.e., put successors at front

CMPT 310 - Blind Search 38

Depth first Search Example
❑ Search down one branch;
❑ if goal not found backtrack to
immediate parent node;
❑ go down next branch

Note: All numbers refer to order visited in

search.
2. Depth-First Algorithm

Depth-first-search
open = [start];
close = [];
while open  []
remove leftmost state from open, call it X;
put X on closed;
if X is goal return SUCCESS
else
generate children of X;
discard children if on closed or open;
put remaining children on left end of open;
return FAIL

51
2. Depth-First Search
❑ Many problems have very deep or even infinite search trees.
❑ One problem with DFS is that it can get stuck going down the
wrong path.
❑ DFS should be avoided for search trees with large or
infinite maximum depths.
❑ It is common to implement a DFS with a recursive
function that calls itself on each of its children in turn.

•Completeness: No
•Time complexity: bm
•Space complexity: bm
•Optimality: No
(b-branching factor, m-max depth of tree)
Properties of depth-first search
Complete? Time? Space?Optimal?
Complete? No: fails in infinite-depth spaces, spaces with loops
Modify to avoid repeated states along path (graph search)
→ complete in finite spaces
Time? O(bm): terrible if maximum depth m is much larger than solution depth d
but if solutions are dense, may be much faster than breadth-first
Space? O(bm), i.e., linear space! Store single path with unexpanded siblings.
Seems to be common in animals and humans.
Optimal? No.
Important for exploration (on-line search).

CMPT 310 - Blind Search 42

Breadth-First vs. Depth-First
•Uninformed breadth-first search:
❑ Requires the construction and memorization of almost the complete
search tree.
❑ Space complexity for search depth n is O(en).
❑ Is guaranteed to find the shortest path to a solution (if all step costs
are equal).

•Uninformed depth-first search:

❑ Requires the memorization of only the current path and the
branches from this path that were already visited.
❑ Space complexity for search depth n is O(n).
❑ May search unnecessarily deep for a shallow goal.
Improving BFS

•Uniform-Cost Search
• 3. Uniform Cost Search
❑ Similar to breadth first, but takes path cost into account
❑ BFS finds the shallowest goal state.

❑ Uniform cost search modifies the BFS by expanding the lowest cost node First (as
measured by the path cost g(n))

❑ The cost of a path must never decrease as we traverse the path, i.e. no negative
cost should be in the problem domain
•Completeness: Yes
•Time complexity: # of nodes with path n cost g ≤ cost of optimal solution, O(b1
+ [C*/ε]) where C* is the cost of the optimal solution
•Space complexity: # of nodes with g ≤ cost of optimal solution, O(b1 + [C*/ε])
•Optimality: Uniform-cost search is always optimal as it only selects a path with the
lowest path cost.
UCS Example

Open list: C
UCS Example

Open list: B(2) T(1) O(3) E(2) P(5)

UCS Example

Open list: T(1) B(2) E(2) O(3) P(5)

UCS Example

Open list: B(2) E(2) O(3) P(5)

UCS Example

Open list: E(2) O(3) P(5)

UCS Example

Open list: E(2) O(3) A(3) S(5) P(5) R(6)

UCS Example

Open list: O(3) A(3) S(5) P(5) R(6)

UCS Example

Open list: O(3) A(3) S(5) P(5) R(6) G(7)

UCS Example

Open list: A(3) S(5) P(5) R(6) G(7)

UCS Example

Open list: A(3) I(4) S(5) N(5) P(5) R(6) G(7)

UCS Example

Open list: I(4) P(5) S(5) N(5) R(6) G(7)

UCS Example

Open list: P(5) S(5) N(5) R(6) Z(6) G(7)

UCS Example

Open list: S(5) N(5) R(6) Z(6) F(6) D(8) G(7) L(10)
UCS Example

Open list: N(5) R(6) Z(6) F(6) D(8) G(7) L(10)

UCS Example

Open list: Z(6) F(6) D(8) G(7) L(10)

UCS Example

Open list: F(6) D(8) G(7) L(10)

UCS Example
Improving DFS
• Depth-limited Search
• Iterative Deepening
4. Depth-Limited Search
• “Practical” DFS
• DLS avoids the pitfalls of DFS by imposing a cutoff on the maximum depth
of a path.
• However, if we choose a depth limit that is too small, then DLS is not even
complete.
• The time and space complexity of DLS is similar to DFS.

Completeness: Yes, if l >= d

Time complexity: bl
Space complexity: bl
Optimality: No (b-branching factor, l-depth limit) 62
5. Iterative Deepening Search

• The hard part about DLS is picking a good limit.

• IDS is a strategy that sidesteps the issue of choosing the best depth limit by trying
all possible depth limits: first depth 0, then depth 1, the depth 2, and so on.

• Iterative deepening is an interesting combination of breadth-first and depth-first

strategies:
• Space complexity for search depth n is O(n).
• Is guaranteed to find the shortest path to a solution
without searching unnecessarily deep.

• How does it work?

• The idea is to successively apply depth-first searches with increasing
depth bounds (maximum search depth).
63
Iterative deepening search L=0
Iterative deepening search L=1
Iterative deepening search L=2
Iterative Deepening Search L=3
Iterative deepening search

• Number of nodes generated in a depth-limited search to

depth d with branching factor b:
NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

• Number of nodes generated in an iterative deepening

search to depth d with branching factor b:
NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd
= O(bd)

• For b = 10, d = 5,
• NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
• NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450
O (b d )
5. Iterative Deepening Search
• IDS may seem wasteful, because so many states are expanded
multiple times.

• For most problems, however, the overhead of this multiple

expansion is actually rather small.

• IDS is the preferred search method when there is a large search

space and the depth of the solution is not known.

•Completeness: Yes
•Time complexity: bd
•Space complexity: bd
•Optimality: Yes
Comparison of Search Techniques
DFS BFS UCS IDS

Complete N Y Y Y

Optimal N N Y N

Heuristic N N N N

Time bm bd+1 Number of bd

nodes with
g(n) ≤ C*

Space bm bd+1 Number of bd

nodes with
g(n) ≤ C*

b: maximum branching factor of the search tree

d: depth of the optimal solution
m: maximum length of any path in the state space
C*: cost of optimal solution
g(n): cost of path from start state to node