Artificial Intelligence

Md. Zasim Uddin, PhD

Associate professor, Dept. Computer Science & Engineering
Begum Rokeya University, Rangpur
Content of previous lecture

Formulate goal: Be in
Bucharest.

Formulate problem: states

are cities, operators drive
between pairs of cities

Find solution: Find a

sequence of cities (e.g.,
Arad, Sibiu, Fagaras,
Bucharest) that leads from
the current state to a state
meeting the goal condition

2
Searching for a solution: Key concepts in
search
 Set of states
 Including an initial state and goal states
 For every state, a set of actions
 Each action results in a new state
 Typically defined by successor function
 Cost function that determines the cost of each
action (path, sequence of actions)
 Solution: path from initial state to a goal state
 Optimal solution: solution with minimal cost
Measuring problem-solving
performance
 Completeness: is the algorithm guaranteed to
find a solution ?
 Optimality: does the strategy find optimal solution
?
 Time complexity: how long does it takes to find a
solution?
 Space complexity: how much memory is needed
to perform solution ?

4
8-puzzle

1 2 1 2 3
4 5 3 4 5 6
7 8 6 7 8
goal state
8-puzzle
1 2
4 5 3
7 8 6

1 2 1 2 1 5 2
4 5 3 4 5 3 4 3
7 8 6 7 8 6 7 8 6

.. ..
. .
Recall: State-space formulation
 Intelligent agents: problem solving as search

 Search consists of
 state space
 operators
 start state
 goal states

 A Search Tree is an effective way to represent the search process

 There are a variety of search algorithms, including

 Depth-First Search
 Breadth-First Search

8
Uninformed search strategies
 Uninformed: While searching we have no clue
whether one non-goal state is better than any
other. The search is blind.

 Various blind strategies:

 Breadth-first search
 Uniform-cost search
 Depth-first search
 Iterative deepening search

9
Breadth-first search
 Expand shallowest unexpanded node
 Fringe: nodes waiting in a queue to be explored, also
called OPEN
 Implementation:
 fringe is a first-in-first-out (FIFO) queue, i.e., new
successors go at end of the queue.

Is A a goal state?

10
Breadth-first search

 Expand shallowest unexpanded node

 Implementation:
 fringe is a FIFO queue, i.e., new successors
go at end

Expand:
fringe = [B,C]

Is B a goal state?

11
Breadth-first search

 Expand shallowest unexpanded node

 Implementation:
 fringe is a FIFO queue, i.e., new successors go at
end

Expand:
fringe=[C,D,E]

Is C a goal state?

12
Breadth-first search

 Expand shallowest unexpanded node

 Implementation:
 fringe is a FIFO queue, i.e., new successors go at
end

Expand:
fringe=[D,E,F,G]

Is D a goal state?

13
Example: map navigation

A B C

S G

D E F

S = start, G = goal, other nodes = intermediate states, links = legal transitions

14
What is the complexity of Breadth-first
search?
• Time Complexity
– assume (worst case) that there is 1
goal leaf at the RHS d=0
– so BFS will expand all nodes
d=1
= 1 + b + b 2+ ......... + bd
= O (bd) d=2
G

• Space Complexity
– how many nodes can be in the queue d=0
(worst-case)?
– at depth d there are bd unexpanded d=1
nodes in the Q = O (bd)
d=2
– Time and space of number of generated G
nodes is O (b^(d+1))
15
Examples of time and memory requirements for
the Breadth-first search

Depth of Nodes
Solution Expanded Time Memory

0 1 1 millisecond 100 bytes

2 111 0.1 seconds 11 kbytes

4 11,111 11 seconds 1 megabyte

8 108 31 hours 11 giabytes

12 1012 35 years 111 terabytes

Assuming b=10, 1000 nodes/sec, 100 bytes/node

16
Depth-first search
1. Put the start node s on OPEN
2. If OPEN is empty exit with failure.
3. Remove the first node n from OPEN and place it on
CLOSED.
4. If n is a goal node, exit successfully with the solution
obtained by tracing back pointers from n to s.
5. Otherwise, expand n, generating all its successors
attach to them pointers back to n, and put them at the
top of OPEN in some order.
6. Go to step 2.

17
Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = Last In First Out (LIPO) queue, i.e., put
successors at front

Is A a goal state?

18
Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[B,C]

Is B a goal state?

19
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[D,E,C]

Is D = goal state?

20
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[H,I,E,C]

Is H = goal state?

21
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[I,E,C]

Is I = goal state?

22
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[E,C]

Is E = goal state?

23
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[J,K,C]

Is J = goal state?

24
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[K,C]

Is K = goal state?

25
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[C]

Is C = goal state?

26
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[F,G]

Is F = goal state?

27
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[L,M,G]

Is L = goal state?

28
 Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = LIFO queue, i.e., put successors at front

queue=[M,G]

Is M = goal state?

29
What is the complexity of Depth-first search?

d=0
 Time Complexity
 assume (worst case) that there is 1
goal leaf at the RHS d=1
 so DFS will expand all nodes
d=2
(m is cutoff)
=1 + b + b2+ ......... + b^m G

= O (b^m)
d=0

d=1
 Space Complexity
 how many nodes can be in the d=2
queue (worst-case)?
 at depth l < d we have b-1 nodes d=3
 at depth d we have b nodes
 total = (m-1)*(b-1) + b = O(bm) d=4

30
Comparing DFS and BFS
 Same worst-case time Complexity, but
 In the worst-case BFS is always better than DFS
 Sometime, on the average DFS is better if:
• many goals, no loops and no infinite paths
 In general
• BFS is better if goal is not deep, if infinite paths, if many
loops, if small search space
• DFS is better if many goals, not many loops,
• DFS is much better in terms of memory

31