Solving Problems By
Searching
Lecture # 07 & 08
Monday, February 17, 2020
Spring 2020
FAST – NUCES, Faisalabad Campus
Zain Iqbal
zain.iqbal@nu.edu.pk
Search tree
A node is having five components:
⚫ STATE: which state it is in the state space
⚫ PARENT-NODE: from which node it is generated
⚫ ACTION: which action applied to its parent-node
to generate it
⚫ PATH-COST: the cost, g(n), from initial state to
the node n itself
⚫ DEPTH: number of steps along the path from the
initial state
17-Feb-20 64
17-Feb-20 65
17-Feb-20 66
Measuring problem-solving performance
The evaluation of a search strategy
⚫ Completeness:
⚫ is the strategy guaranteed to find a solution when
there is one?
⚫ Optimality:
⚫ does the strategy find the highest-quality solution
when there are several different solutions?
⚫ Time complexity:
⚫ how long does it take to find a solution?
⚫ Space complexity:
⚫ how much memory is needed to perform the search?
17-Feb-20 67
Measuring problem-solving performance
In AI, complexity is expressed in
⚫ b, branching factor, maximum number of
successors of any node
⚫ d, the depth of the shallowest goal node.
(number of steps along the path from the root)
⚫ m, the maximum length of any path in the state
space
Time and Space is measured in
⚫ number of nodes generated during the search
⚫ maximum number of nodes stored in memory
17-Feb-20 68
Measuring problem-solving performance
For effectiveness of a search algorithm
⚫ we can just consider the total cost
⚫ The total cost = path cost (g)of the solution
found + search cost
⚫ search cost = time necessary to find the solution
Tradeoff:
⚫ (long time, optimal solution with least g)
⚫ vs. (shorter time, solution with slightly larger
path cost g)
17-Feb-20 69
Search Types
17-Feb-20 70
3.4 Uninformed search strategies
Uninformed search
⚫ no information about the number of steps
⚫ or the path cost from the current state to
the goal
⚫ search the state space blindly
Informed search, or heuristic search
⚫ a cleverer strategy that searches toward
the goal,
⚫ based on the information from the current
state so far
17-Feb-20 71
Uninformed search strategies
Breadth-first search
⚫ Uniform cost search
Depth-first search
⚫ Depth-limited search
⚫ Iterative deepening search
⚫ Iterative lengthening search
17-Feb-20 72
Breadth-first search
The root node is expanded first (FIFO)
All the nodes generated by the root
node are then expanded
And then their successors and so on
17-Feb-20 73
Breath-first search
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
17-Feb-20 74
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (1)
4 5 6 7
17-Feb-20 75
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (2, 3)
4 5 6 7
17-Feb-20 76
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (3, 4, 5)
4 5 6 7
17-Feb-20 77
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (4, 5, 6, 7)
4 5 6 7
17-Feb-20 78
Breadth-First Strategy
17-Feb-20 79
Breadth-first search (Analysis)
Breadth-first search
⚫ Complete – find the solution eventually
⚫ Optimal, if step cost is 1
The disadvantage
⚫ if the branching factor of a node is large,
⚫ for even small instances (e.g., chess)
⚫ the space complexity and the time complexity
are enormous
17-Feb-20 80
Properties of breadth-first search
Complete? Yes (if b is finite)
Time? 1+b+b2+b3+… +bd = O(b^d)
Space? O(bd+1) (keeps every node in
memory)
Optimal? Yes (if cost = 1 per step)
Space is the bigger problem (more than time)
17-Feb-20 81
Breadth-first search (Analysis)
assuming 1 million nodes can be processed per second, each
with 1000 bytes of storage
17-Feb-20 82
BFS
17-Feb-20 83
BFS
17-Feb-20 84
BFS
17-Feb-20 85
Uniform cost search
Breadth-first finds the shallowest goal state
⚫ but not necessarily be the least-cost solution
⚫ work only if all step costs are equal
Uniform cost search
⚫ modifies breadth-first strategy
⚫ by always expanding the lowest-cost node
⚫ The lowest-cost node is measured by the path
cost g(n)
Uniform cost search
the first found solution is guaranteed to be the cheapest
⚫ least in depth
⚫ But restrict to Cheapest path cost
⚫ Unsuitable for operators with negative cost
Uniform cost search
17-Feb-20 88
Uniform cost search
80+97+101= 278.
99+211=310
17-Feb-20 89
Uniform-cost search
Uniform-cost search is guided by path costs rather than depths,
so its complexity is not easily characterized in terms of b and d.
Instead, let C∗ be the cost of the optimal solution, and assume
that every action costs at least ε.
Then the algorithm’s worst-case time and space complexity is
O(b1+C∗/ ε), which can be much greater than b ^d.
This is because uniform cost search can explore large trees of
small steps before exploring paths involving large and perhaps
useful steps.
When all step costs are equal, b 1+C∗/ ε is just b^d+1.
When all step costs are the same, uniform-cost search is
similar to breadth-first search,
17-Feb-20 90
Uniform-cost search
Expand least-cost unexpanded node
Implementation:
⚫ fringe = queue ordered by path cost
⚫
Equivalent to breadth-first if step costs all equal
Complete? Yes, if step cost ≥ ε
Time? # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε)) where C* is the cost of the optimal
solution
Space? # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε))
Optimal? Yes – nodes expanded in increasing order of
g(n)
Uniform cost search
• Blue Color represents added paths
• Underline paths are chosen for extension.
17-Feb-20 92
Uniform cost search
17-Feb-20 93
Uniform cost search
17-Feb-20 94
Uniform cost search
17-Feb-20 95
Uniform cost search
17-Feb-20 96
Uniform cost search
*Strikethrough nodes are discarded
17-Feb-20 97
Depth-first search
Always expands one of the nodes at the
deepest level of the tree
Only when the search hits a dead end
⚫ goes back and expands nodes at shallower levels
⚫ Dead end → leaf nodes but not the goal
Backtracking search
⚫ only one successor is generated on expansion
⚫ rather than all successors
⚫ fewer memory
17-Feb-20 98
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
17-Feb-20 99
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
17-Feb-20 100
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 101
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 102
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 103
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 104
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 105
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 106
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 107
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 108
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 109
Depth-first search
Expand deepest unexpanded node
Implementation:
⚫ fringe = LIFO queue, i.e., put successors at front
⚫
17-Feb-20 110
Depth-first search
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
17-Feb-20
G 25 111
DFS
17-Feb-20 112
DFS
17-Feb-20 113
DFS
17-Feb-20 114
Depth-first search (Analysis)
Not complete
⚫ because a path may be infinite or looping
⚫ then the path will never fail and go back try
another option
Not optimal
⚫ it doesn't guarantee the best solution
It overcomes
⚫ the time and space complexities
17-Feb-20 115
Properties of depth-first search
Complete? No: fails in infinite-depth spaces,
spaces with loops
⚫ Modify to avoid repeated states along path
⚫ → complete in finite spaces
⚫
Time? O(bm): terrible if m is much larger than d
⚫ but if solutions are dense, may be much faster
than breadth-first
Space? Stores only O(bm) nodes, i.e., linear
space!
Optimal? No
17-Feb-20 116
Advantages over BFS
The depth first search would require 156 kilobytes instead
of 10 Exabyte at depth d=16, a factor of 7 trillion times
less space.
117
Depth-Limited Strategy
Depth-first with depth cutoff k (maximal
depth below which nodes are not
expanded)
Three possible outcomes:
⚫ Solution
⚫ Failure (no solution)
⚫ Cutoff (no solution within cutoff)
Depth-limited search
It is depth-first search
⚫ with a predefined maximum depth
⚫ However, it is usually not easy to define the
suitable maximum depth
⚫ too small → no solution can be found
⚫ too large → the same problems are
suffered from
Anyway the search is
⚫ complete
⚫ but still not optimal
Depth-limited
S
search
depth = 3
A D 3
6
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
Depth-limited search
17-Feb-20 121
Depth-limited search
17-Feb-20 122
Iterative deepening search
No choosing of the best depth limit
It tries all possible depth limits:
⚫ first 0, then 1, 2, and so on
⚫ combines the benefits of depth-first and
breadth-first search
Iterative deepening search
17-Feb-20 124
Iterative deepening search
Iterative deepening search
(Analysis)
optimal
complete
Time and space complexities
⚫ reasonable
suitable for the problem
⚫ having a large search space
⚫ and the depth of the solution is not known
Properties of iterative deepening
search
Complete? Yes
Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd
= O(bd)
Space? O(bd)
Optimal? Yes, if step cost = 1
Contd..
To Avoid repetition you can use a
hybrid approach
That runs breadth-first search until
almost all the available memory is
consumed, and then runs iterative
deepening from all the nodes in the
frontier.
In general, iterative deepening is the
preferred uninformed search method
when the search space is large and the
depth of the solution is not known.
17-Feb-20 128
Iterative lengthening search
IDS is using depth as limit
ILS is using path cost as limit
⚫an iterative version for uniform cost search
has the advantages of uniform cost search
⚫ while avoiding its memory requirements
⚫ but ILS experiences substantial overhead
⚫ compared to uniform cost search
Bidirectional search
Run two simultaneous searches
⚫ one forward from the initial state another
backward from the goal
⚫ stop when the two searches meet
However, computing backward is difficult
⚫ A huge amount of goal states
⚫ at the goal state, which actions are used to
compute it?
⚫ can the actions be reversible to computer its
predecessors?
Bidirectional Strategy
2 fringe queues: FRINGE1 and FRINGE2
Time and space complexity = O(bd/2) << O(bd)
Bidirectional
S search
Forward
A D Backwards
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
Comparing search strategies
Avoiding repeated states
for all search strategies
⚫ There is possibility of expanding states
⚫ that have already been encountered and expanded
before, on some other path
⚫ may cause the path to be infinite → loop forever
⚫ Algorithms that forget their history
⚫ are doomed to repeat it
Avoiding repeated states
Three ways to deal with this possibility
⚫ Do not return to the state it just came from
⚫ Refuse generation of any successor same as its
parent state
⚫ Do not create paths with cycles
⚫ Refuse generation of any successor same as its
ancestor states
⚫ Do not generate any generated state
⚫ Not only its ancestor states, but also all other
expanded states have to be checked against
Avoiding repeated states
We then define a data structure
⚫ closed list:
a set storing every expanded node so far
⚫ If the current node matches a node on the
closed list, discard it.
Reading Material
Russell & Norvig Chapter # 3
17-Feb-20 151
