ARTIFICIAL

INTELLIGENCE

Dr. Mohamed Khamiss Hussein

Lecture 2
 Missionaries and cannibals
 Three missionaries and three cannibals are on the left bank
of a river.

 There is one canoe which can hold one or two people.

Find a way to get everyone to the right bank, without ever leaving a group of
missionaries in one place outnumbered by cannibals in that place.
Missionaries and Cannibals
Initial State

3
Missionaries and Cannibals
Goal State

4
 Problem Formulation

A Problem Space consists of

 The current state of the world (initial state)

 A description of the actions we can take to transform one state of the world into another
(operators).

 A description of the desired state of the world (goal state),

 this could be implicit or explicit.

 A solution consists of the goal state, or a path to the goal state.

 Problem Formulation
 States: three numbers (i,j,k) representing the number of missionaries, cannibals,
and canoes on the left bank of the river.
 Initial state: (3, 3, 1)
 Operators: take one missionary, one cannibal, two missionaries, two cannibals,
one missionary and one cannibal across the river in a given direction (I.e. ten
operators).
 Goal Test: reached state (0, 0, 0)
 Path Cost: Number of crossings.
Missionaries and Cannibals
(3,3,1): Initial State

7
Missionaries and Cannibals
A missionary and cannibal cross

8
Missionaries and Cannibals
(2,2,0)

9
Missionaries and Cannibals
One missionary returns

10
Missionaries and Cannibals
(3,2,1)

11
Missionaries and Cannibals
Two cannibals cross

12
Missionaries and Cannibals
(3,0,0)

13
Missionaries and Cannibals
A cannibal returns

14
Missionaries and Cannibals
(3,1,1)

15
Missionaries and Cannibals
Two missionaries cross

16
Missionaries and Cannibals
(1,1,0)

17
Missionaries and Cannibals
A missionary and cannibal return

18
Missionaries and Cannibals
(2,2,1)

19
Missionaries and Cannibals
Two Missionaries cross

20
Missionaries and Cannibals
(0,2,0)

21
Missionaries and Cannibals
A cannibal returns

22
Missionaries and Cannibals
(0,3,1)

23
Missionaries and Cannibals
Two cannibals cross

24
Missionaries and Cannibals
(0,1,0)

25
Missionaries and Cannibals
A cannibal returns

26
Missionaries and Cannibals
(0,2,1)

27
Missionaries and Cannibals
The last two cannibals cross

28
Missionaries and Cannibals
(0,0,0) : Goal State

29
 Missionaries and Cannibals
Solution = the sequence of actions within the path :
[ (3,3,1)→ (2,2,0)→(3,2,1) →(3,0,0) →(3,1,1) →(1,1,0) →(2,2,1) →(0,2,0) →(0,3,1)
→(0,1,0) → (0,2,1) →(0,0,0)];
Cost = 11 crossings

30
 Summary
 Search: process of constructing sequences of actions that achieve a goal given a
problem.

 It is assumed that the environment is observable, deterministic, static and

completely known.

 Goal formulation is the first step in solving problems by searching. It facilitates

problem formulation.

 Formulating a problem requires specifying five components: State representation,

Initial state, Goal state, Operators (actions), and Path cost function.

31
Problem Solving by Searching

Search Methods :
Uninformed (Blind) search
 The River Problem
 The River Problem:
F=Farmer W=Wolf D=Duck C=Corn /=River

-/FWCD

FWCD/-

How can the farmer safely transport the wolf, the duck and
the corn to the opposite shore?
33
 The River Problem
 Problem Formulation
 State representation: location of farmer and items in both sides of river
[items in South shore / items in North shore] : (FWDC/-, FD/WC, C/FWD …)

 Initial State: farmer, wolf, duck and corn in the south shore FWDC/-

 Goal State: farmer, duck and corn in the north shore -/FWDC

 Operators: the farmer takes in the boat at most one item from one side to the
other side
(F-Takes-W, F-Takes-D, F-Takes-C, F-Takes-Self [himself only])

 Path cost: the number of crossings

34
 The River Problem
 Problem solution: (path Cost = 7)
While there are other possibilities here is one 7 step solution to the river problem
F D D F W D
F-Takes-D F-Takes-S F-Takes-W

F W D C W C F W C C
Initial State WC/FD FWC/D C/FWD

F-Takes-D

F W D C W C F W C W

F-Takes-D F-Takes-S F-Takes-C

F D D F D C
Goal State FD/WC D/FWC FDC/W
35
Problem Formulation
 Problem formulation:

 State representation: location of farmer and items in both sides of river

[items in South shore / items in North shore] : (FWDC/-, FD/WC, C/FWD …)

 Initial State: farmer, wolf, duck and corn in the south shore FWDC/-

 Goal State: farmer, duck and corn in the north shore

-/FWDC

 Operators: the farmer takes in the boat at most one item from one side to
the other side
(F-Takes-W, F-Takes-D, F-Takes-C, F-Takes-Self [himself only])

 Path cost: the number of crossings

36
 Search Methods
 State space:
A problem is solved by moving from the initial state to the goal state by applying valid
operators in sequence. Thus the state space is the set of states reachable from a particular
initial state.
F WD C
Initial state

WD C D C W C WD

Dead ends
F F W F D F C

Illegal states
F W C F WD C
D

repeated state F
W
D
C
F WD
C
F
W
D C
intermediate state

F C F W C F D C F W F WD F W C
WD D W D C C D

D C C D WD D W
F W F WD F W C F C F W C F D C

F D F WD F D C
W C C W

F W
D
C F WD C Goal state 37
Search Methods
 Searching for a solution: F WD C

We start with the initial state and

keep using the operators to
WD C DC W C WD
F FW F D F C

expand the parent nodes till we

find a goal state. FW C
D
F WD C

W C C W

…but the search space might be

F D F WD F DC

large… F C FW C F DC FW F WD FW C
WD D W DC C D

 …really large… DC C D WD D W
FW F WD FW C F C FW C F DC

 So we need some systematic way

to search.
F D F WD F DC
W C C W

D
FW C F WD C

38
Search Methods
F WD C

 Problem solution:

A problem solution is simply the set

WD C DC W C WD
F FW F D F C

of operators (actions) needed to

reach the goal state from the initial
FW C F WD C
D

state:
W C C W
F D F WD F DC

F-Takes-D, F-Takes-Self, F-Takes-W, F

WD
C FW C
D
F
W
DC FW
DC
F WD
C
FW C
D

F-Takes-D, F-Takes-C, F-Takes-Self,

DC C D WD D W
FW F WD FW C F C FW C F DC

F D F WD F DC

F-Takes-D. W C C W

D
FW C F WD C

39
Search Methods
 Problem solution: (path Cost = 7)
While there are other possibilities here is one 7 step solution to the river problem

F D D F W D
F-Takes-D F-Takes-S F-Takes-W

F W D C W C F W C C
Initial State WC/FD FWC/D C/FWD

F-Takes-D

F W G C W C F W C W

F-Takes-D F-Takes-S F-Takes-C

F D D F D C
Goal State FD/WC D/FWC FDC/W
40
Problem Solving by searching

Basic Search Algorithms

Basic Search Algorithms
 uninformed( Blind) search: breadth-first, depth-first,
depth limited, iterative deepening, and bidirectional search

 informed (Heuristic) search: search is guided by an

evaluation function: Greedy best-first, A*, IDA*, and beam
search

 optimization in which the search is to find an optimal value

of an objective function: hill climbing, simulated annealing,
genetic algorithms, Ant Colony Optimization

 Game playing, an adversarial search: minimax algorithm,

alpha-beta pruning
42
What Criteria are used to Compare different
search techniques ?
As we are going to consider different techniques to search the
problem space, we need to consider what criteria we will use to
compare them.

 Completeness: Is the technique guaranteed to find an answer

(if there is one).

 Optimality/Admissibility : does it always find a least-cost

solution?
- an admissible algorithm will find a solution with minimum cost

 Time Complexity: How long does it take to find a solution.

 Space Complexity: How much memory does it take to find a

solution.
43
Time and Space Complexity ?
Time and space complexity are measured in terms of:

 The average number of new nodes we create when expanding a new node is the
(effective) branching factor b.

 The (maximum) branching factor b is defined as the maximum nodes created when a
new node is expanded.

 The length of a path to a goal is the depth d.

 The maximum length of any path in the state space m.

44
A Toy Example: A Romanian Holiday

 State space: Cities in Romania

 Initial state: Town of Arad
 Goal: Airport in Bucharest
 Operators: Drive between cities
 Solution: Sequence of cities
 Path cost: number of cities, distance,
time, fuel
45
The state Space

46
Generic Search Algorithms

 Basic Idea: Off-line exploration of state space by

generating successors of already-explored states (also
known as expanding states).
Function GENERAL-SEARCH (problem, strategy)
returns a solution or failure
Initialize the search tree using the initial state of problem
loop do
if there are no candidates for expansion, then return failure
Choose a leaf node for expansion according to strategy
if node contains goal state then return solution
else expand node and add resulting nodes to search tree.
end
47
Representing Search
Arad

Zerind Sibiu Timisoara

Arad Oradea Fagaras Rimnicu Vilcea

Sibiu Bucharest

48
Solution

49
Implementation of Generic Search
Algorithm
function general-search(problem, QUEUEING-FUNCTION)
nodes = MAKE-QUEUE(MAKE-NODE(problem.INITIAL-STATE))
loop do
if EMPTY(nodes) then return "failure"
node = REMOVE-FRONT(nodes)
if problem.GOAL-TEST(node.STATE) succeeds then return solution(node)
nodes = QUEUEING-FUNCTION(nodes, EXPAND(node, problem.OPERATORS))
end

A nice fact about this search algorithm is that we can use a single algorithm to do
many kinds of search. The only difference is in how the nodes are placed in the
queue. The choice of queuing function is the m ain feature. 50
Key Issues of State-Space search
algorithm
 Search process constructs a “search tree”
• root is the start node
• leaf nodes are:
 unexpanded nodes (in the nodes list)
 “dead ends” (nodes that aren’t goals and have no successors because no operators were applicable)

 Loops in a graph may cause a “search tree” to be infinite even if the state space is small

 changing definition of how nodes are added to list leads to a different search strategy

 Solution desired may be:

• just the goal state
• a path from start to goal state (e.g., 8-puzzle)

51
Uninformed search strategies (Blind
search)
Uninformed (blind) strategies use only the information available in the problem definition.
These strategies order nodes without using any domain specific information

Contrary to Informed search techniques which might have additional information (e.g. a
compass).

 Breadth-first search
 Uniform-cost search
 Depth-first search
 Depth-limited search
 Iterative deepening search
 Bidirectional search

52
Basic Search Algorithms
Uninformed Search

Breadth First Search (BFS)

Breadth First Search (BFS)

54
Breadth First Search (BFS)

Main idea: Expand all nodes at depth (i) before expanding nodes at depth (i + 1)
Level-order Traversal.
Implementation: Use of a First-In-First-Out queue (FIFO). Nodes visited first
are expanded first. Enqueue nodes in FIFO (first-in, first-out) order.
• Complete? Yes.
• Optimal? Yes, if path cost is nondecreasing function of depth
• Time Complexity: O(bd)
• Space Complexity: O(bd), note that every node in the fringe is kept in the queue.
55
 Breadth First Search
 QUEUING-FN:- successors added to end
of queue Arad

Zerind Sibiu Timisoara

Arad
Arad Oradea
Oradea Fagaras
Arad Lugoj
Rimnicu Vilcea

Shallow nodes are expanded before deeper nodes.

56
Basic Search Algorithms
Uninformed Search

Uniform Cost Search (UCS)

 Uniform Cost Search (UCS)

5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
Goal state
4 5

[x] = g(n) [7] [8]

path cost of node n

58
Uniform Cost Search (UCS)

5 2
[5] [2]

59
Uniform Cost Search (UCS)

5 2
[5] [2]

1 7
[3] [9]

60
Uniform Cost Search (UCS)

5 2
[5] [2]

1 7
[3] [9]
4 5

[7] [8]

61
Uniform Cost Search (UCS)

5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
4 5

[7] [8]

62
 Uniform Cost Search (UCS)

5 2
[5] [2]
Goal state
1 4 1
path cost 7
g(n)=[6] [3] [9]
[9]
4 5

[7] [8]

63
Uniform Cost Search (UCS)

5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
4 5

[7] [8]

64
 Uniform Cost Search (UCS)
 In case of equal step costs, Breadth First search finds
the optimal solution.

 For any step-cost function, Uniform Cost search

expands the node n with the lowest path cost.

 UCS takes into account the total cost: g(n).

 UCS is guided by path costs rather than depths.

Nodes are ordered according to their path cost.
65
 Uniform Cost Search (UCS)
 Main idea: Expand the cheapest node. Where the cost is the path cost g(n).

 Implementation:
Enqueue nodes in order of cost g(n).
QUEUING-FN:- insert in order of increasing path cost.
Enqueue new node at the appropriate position in the queue so that we
dequeue the cheapest node.

 Complete? Yes.
 Optimal? Yes, if path cost is nondecreasing function of depth
 Time Complexity: O(bd)
 Space Complexity: O(bd), note that every node in the fringe keep in the queue.

66
Basic Search Algorithms
Uninformed Search

Depth First Search (DFS)

Depth First Search (DFS)

68
 Depth First Search (DFS)
Main idea: Expand node at the deepest level (breaking ties left to right).

Implementation: use of a Last-In-First-Out queue or stack(LIFO). Enqueue

nodes in LIFO (last-in, first-out) order.

• Complete? No (Yes on finite trees, with no loops).

• Optimal? No

• Time Complexity: O(bm), where m is the maximum depth.

• Space Complexity: O(bm), where m is the maximum depth.

69
Depth First Search

70
 Depth-First Search (DFS)
 QUEUING-FN:- insert successors at
front of queue Arad

Zerind Sibiu Timisoara

Arad Oradea

Zerind Sibiu Timisoara

71
Basic Search Algorithms
Uninformed Search

Depth-Limited Search (DLS)

Depth-Limited Search (DLS)

Depth Bound = 3
73
 Depth-Limited Search (DLS)
It is simply DFS with a depth bound.
 Searching is not permitted beyond the depth bound.

 Works well if we know what the depth of the solution is.

 Termination is guaranteed.

 If the solution is beneath the depth bound, the search

cannot find the goal (hence this search algorithm is
incomplete).

 Otherwise use Iterative deepening search (IDS).

74
 Depth-Limited Search (DLS)
Main idea: Expand node at the deepest level, but limit depth to L.

Implementation:
Enqueue nodes in LIFO (last-in, first-out) order. But limit depth to L

•Complete? Yes if there is a goal state at a depth less than L

• Optimal? No

• Time Complexity: O(bL), where L is the cutoff.

• Space Complexity: O(bL), where L is the cutoff.

75
Basic Search Algorithms
Uninformed Search

Iterative Deepening Search (IDS)

 Iterative Deepening Search (IDS)

function ITERATIVE-DEEPENING-SEARCH():

for depth = 0 to infinity do

if DEPTH-LIMITED-SEARCH(depth) succeeds
then return its result
end
return failure

77
 Iterative Deepening Search (IDS)
 Key idea: Iterative deepening search (IDS) applies DLS repeatedly
with increasing depth. It terminates when a solution is found or no
solutions exists.

 IDS combines the benefits of BFS and DFS: Like DFS the memory
requirements are very modest (O(bd)). Like BFS, it is complete
when the branching factor is finite.

 The total number of generated nodes is :

N(IDS)=(d)b + (d-1) b2 + …+(1)bd

 In general, iterative deepening is the preferred uninformed search

method when there is a large search space and the depth of the
solution is not known. 78
 Iterative Deepening Search (IDS)

L=0

L=1

L=2

L=3
79
Iterative Deepening Search (IDS)

80
Iterative Deepening Search (IDS)

81
Basic Search Algorithms
Uninformed Search

Bi-Directional Search (BDS)

Bi-directional Search (BDS)
 Main idea: Start searching from
both the initial state and the goal
state, meet in the middle.

 Complete? Yes
 Optimal? Yes
 Time Complexity: O(bd/2), where
d is the depth of the solution.
 Space Complexity: O(bd/2), where
d is the depth of the solution.
83
Basic Search Algorithms

Comparison of search algorithms

Comparison of search algorithms

b: Branching factor
d: Depth of solution
m: Maximum depth

l : Depth Limit
85
Blind Search Algorithms

Tree Search:
BFS, DFS, DLS, IDS
Basic Search Algorithms

Breadth First Search

BFS
 Breadth First Search
 Application1:
Given the following state space (tree search), give the sequence
of visited nodes when using BFS (assume that the nodeO is the
goal state):
A

B C D E

F G H I J

K L M N

O
88
 Breadth First Search
 A,

B C D E

89
 Breadth First Search
 A,
 B,

B C D E

F G

90
 Breadth First Search
 A,
 B,C

B C D E

F G H

91
 Breadth First Search
 A,
 B,C,D

B C D E

F G H I J

92
 Breadth First Search
 A,
 B,C,D,E

B C D E

F G H I J

93
 Breadth First Search
 A,
 B,C,D,E,
 F,
A

B C D E

F G H I J

94
 Breadth First Search
 A,
 B,C,D,E,
 F,G
A

B C D E

F G H I J

K L

95
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H
A

B C D E

F G H I J

K L

96
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I
A

B C D E

F G H I J

K L M

97
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
A

B C D E

F G H I J

K L M N

98
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
 K, A

B C D E

F G H I J

K L M N

99
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
 K,L A

B C D E

F G H I J

K L M N

O
100
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
 K,L, M, A

B C D E

F G H I J

K L M N

O
101
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
 K,L, M,N, A

B C D E

F G H I J

K L M N

O
102
 Breadth First Search
 A,
 B,C,D,E,
 F,G,H,I,J,
 K,L, M,N, A
 Goal state: O
B C D E

F G H I J

K L M N

O
103
 Breadth First Search
 The returned solution is the sequence of operators in the path:
A, B, G, L, O

B C D E

F G H I J

K L M N

O
104
Basic Search Algorithms

Depth First Search

DFS
 Depth First Search (DFS)
 Application2:
Given the following state space (tree search), give the sequence
of visited nodes when using DFS (assume that the nodeO is the
goal state):
A

B C D E

F G H I J

K L M N

O
106
 Depth First Search
 A,

B C D E

107
 Depth First Search
 A,B,

B C D E

F G

108
 Depth First Search
 A,B,F,

B C D E

F G

109
 Depth First Search
 A,B,F,
 G,

B C D E

F G

K L

110
 Depth First Search
 A,B,F,
 G,K,

B C D E

F G

K L

111
 Depth First Search
 A,B,F,
 G,K,
 L,
A

B C D E

F G

K L

O
112
 Depth First Search
 A,B,F,
 G,K,
 L, O: Goal State
A

B C D E

F G

K L

O
113
 Depth First Search
The returned solution is the sequence of operators in the path:
A, B, G, L, O

B C D E

F G

K L

O
114
Basic Search Algorithms

Depth-Limited Search
DLS
 Depth-Limited Search (DLS)
 Application3:
Given the following state space (tree search), give the sequence
of visited nodes when using DLS (Limit = 2):

Limit = 0 A

Limit = 1 B C D E

Limit = 2 F G H I J

K L M N

O
116
 Depth-Limited Search (DLS)
 A,

B C D E

Limit = 2

117
 Depth-Limited Search (DLS)
 A,B,

B C D E

Limit = 2 F G

118
 Depth-Limited Search (DLS)
 A,B,F,

B C D E

Limit = 2 F G

119
 Depth-Limited Search (DLS)
 A,B,F,
 G,

B C D E

Limit = 2 F G

120
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,
A

B C D E

Limit = 2 F G H

121
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
A

B C D E

Limit = 2 F G H

122
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
 D, A

B C D E

Limit = 2 F G H I J

123
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
 D,I A

B C D E

Limit = 2 F G H I J

124
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
B C D E

Limit = 2 F G H I J

125
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
 E B C D E

Limit = 2 F G H I J

126
 Depth-Limited Search (DLS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
 E, Failure B C D E

Limit = 2 F G H I J

127
 Depth-Limited Search (DLS)
 DLS algorithm returns Failure (no solution)
 The reason is that the goal is beyond the limit (Limit =2): the
goal depth is (d=4)
A

B C D E

Limit = 2 F G H I J

K L M N

O
128
Basic Search Algorithms

Iterative Deepening Search

IDS
 Iterative Deepening Search (IDS)
 Application4:
Given the following state space (tree search), give the sequence
of visited nodes when using IDS:

Limit = 0 A

Limit = 1 B C D E

Limit = 2 F G H I J

Limit = 3 K L M N

Limit = 4 O
130
Iterative Deepening Search (IDS)

DLS with bound = 0

 Iterative Deepening Search (IDS)
 A,

Limit = 0 A

132
 Iterative Deepening Search (IDS)
 A, Failure

Limit = 0 A

133
Iterative Deepening Search (IDS)

DLS with bound = 1

 Iterative Deepening Search (IDS)
 A,

Limit = 1 B C D E

135
 Iterative Deepening Search (IDS)
 A,B,

Limit = 1 B C D E

136
 Iterative Deepening Search (IDS)
 A,B,
 C,

Limit = 1 B C D E

137
 Iterative Deepening Search (IDS)
 A,B,
 C,
 D,
A

Limit = 1 B C D E

138
 Iterative Deepening Search (IDS)
 A,B
 C,
 D,
 E, A

Limit = 1 B C D E

139
 Iterative Deepening Search (IDS)
 A,B,
 C,
 D,
 E, Failure A

Limit = 1 B C D E

140
 Iterative Deepening Search (IDS)
 A,

B C D E

Limit = 2

141
 Iterative Deepening Search (IDS)
 A,B,

B C D E

Limit = 2 F G

142
 Iterative Deepening Search (IDS)
 A,B,F,

B C D E

Limit = 2 F G

143
 Iterative Deepening Search (IDS)
 A,B,F,
 G,

B C D E

Limit = 2 F G

144
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,
A

B C D E

Limit = 2 F G H

145
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
A

B C D E

Limit = 2 F G H

146
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
 D, A

B C D E

Limit = 2 F G H I J

147
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
 D,I A

B C D E

Limit = 2 F G H I J

148
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
B C D E

Limit = 2 F G H I J

149
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
 E B C D E

Limit = 2 F G H I J

150
 Iterative Deepening Search (IDS)
 A,B,F,
 G,
 C,H,
 D,I A
 J,
 E, Failure B C D E

Limit = 2 F G H I J

K L M N

O
151
Iterative Deepening Search (IDS)

DLS with bound = 3

 Iterative Deepening Search (IDS)
 A,

B C D E

Limit = 3

153
 Iterative Deepening Search (IDS)
 A,B,

B C D E

F G

Limit = 3

154
 Iterative Deepening Search (IDS)
 A,B,F,

B C D E

F G

Limit = 3

155
 Iterative Deepening Search (IDS)
 A,B,F,
 G,

B C D E

F G

Limit = 3 K L

156
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,

B C D E

F G

Limit = 3 K L

157
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
A

B C D E

F G

Limit = 3 K L

158
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C, A

B C D E

F G H

Limit = 3 K L

159
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A

B C D E

F G H

Limit = 3 K L

160
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,
B C D E

F G H I J

Limit = 3 K L

161
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,
B C D E

F G H I J

Limit = 3 K L M

162
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,M,
B C D E

F G H I J

Limit = 3 K L M

163
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,M,
 J, B C D E

F G H I J

Limit = 3 K L M N

164
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,M,
 J,N, B C D E

F G H I J

Limit = 3 K L M N

165
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,M,
 J,N, B C D E
 E,
F G H I J

Limit = 3 K L M N

166
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
 C,H, A
 D,I,M,
 J,N, B C D E
 E,Failure
F G H I J

Limit = 3 K L M N

O
167
Iterative Deepening Search (IDS)

DLS with bound = 4

 Iterative Deepening Search (IDS)
 A,

B C D E

Limit = 4
169
 Iterative Deepening Search (IDS)
 A,B,

B C D E

F G

Limit = 4
170
 Iterative Deepening Search (IDS)
 A,B,F,

B C D E

F G

Limit = 4
171
 Iterative Deepening Search (IDS)
 A,B,F,
 G,

B C D E

F G

K L

Limit = 4
172
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,

B C D E

F G

K L

Limit = 4
173
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L,
A

B C D E

F G

K L

Limit = 4 O
174
 Iterative Deepening Search (IDS)
 A,B,F,
 G,K,
 L, O: Goal State
A

B C D E

F G

K L

Limit = 4 O
175
 Iterative Deepening Search (IDS)
The returned solution is the sequence of operators in the path:
A, B, G, L, O

B C D E

F G

K L

O
176
Summary
 Search: process of constructing sequences of actions that achieve a goal given a
problem.
 The studied methods assume that the environment is observable, deterministic,
static and completely known.
 Goal formulation is the first step in solving problems by searching. It facilitates
problem formulation.
 Formulating a problem requires specifying four components: Initial states,
operators, goal test and path cost function. Environment is represented as a
state space.
 A solution is a path from the initial state to a goal state.
 Search algorithms are judged on the basis of completeness, optimality, time
complexity and space complexity.
 Several search strategies: BFS, DFS, DLS, IDS,…

 All uninformed searches have an exponential time complexity – hopeless as a

viable problem solving mechanism (unless you have a quantum computer!)
177
Thank you