Lecture 3 of Artificial Intelligence

Simple Search Algorithms

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/1

 Topics of this lecture
• Random search
• Search with closed list
• Search with open list
• Depth-first and breadth-first search again
• Uniform-cost search

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/2

State space representation of AI problems
The maze problem

• Initial state: (0,0) y

• Target state: (2,2)

• Available operations:

door
2
– Move forward Exit

door
door

door
– Move backward

door
1
– Move left

door

door
– Move right

door
door
0
• Depends on the current state, the Entrance
same operation may have different x
0
results. 1 2

• Also, an operation may not be

executed for some states.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/3

 State space → search graph

• To find the solution, we

can just traverse the graph,
(2,2)
starting from (0,0), and
(0,2) (1,2)
stop when we visit (2,2).
• The result is a path from
(0,1) (1,1) (2,1)
the initial node to the
target node.
(0,0) (1,0) (2,0) • The result can be different,
depends on the order of
graph traversal.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/4

 Basic considerations
for solving a problem
• Many problems can be formulated using the state space
representation.
• Each state corresponds to a candidate solution.
• Problem solving is to find the best solution via state
transition, which is equivalent to finding a desired node
via traversing a search graph.
• Example: In system theory, the state (a vector) usually
contains “parameters” of a “system”, and the target state
corresponds to the system we want.
• When the problem space is not discrete (i.e. continuous),
we need more sophisticated search algorithms.
Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/5
 Random search
• Step 1: Current node x=initial node;
• Step 2: If x=target node, stop with success;
• Step 3: Expand x, and get a set S of child nodes;
• Step 4: Select a node x’ from S at random;
• Step 5: x=x’, and return to Step 2.

ノードの展開：指定ノードの子ノードを求めること
Node expansion: find the child node(s) of a given node.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/6

 Random search is not good
• At each step, the next
node is determined at I wanna
go home!
random.
• We cannot guarantee to
reach the target node.
• Even if we can, the path so
obtained can be very
redundant (extremely long).

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/7

 Search with a closed list
Do not visit the same node more than once!

• Step 1: Current node x=initial node;

• Step 2: If x=target node, stop with
success;
• Step 3: Expand x, and get a set S of
child nodes. If S is empty or if all
members of S are in the closed list,
stop with failure. Add x to the closed
list.
• Step 4: Select from S a new node x’
that is not in the closed list.
• Step 5: x=x’, and return to Step 2.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/8

 Closed list is not enough!
• Using a closed list, we can guarantee termination of
search in finite steps.
• However, we may never reach the target node!

(0,2) (1,2) (2,2)

(0,1) (1,1) (2,1)

(0,0) (1,0) (2,0)

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/9

 Search with open list
Keep all “un-visited” nodes in another list!

• Step 1: Add the initial node to the open list.

• Step 2: Take a node x from the open list from the top. If
the open list is empty, stop with failure; on the other
hand, if x is the target node, stop with success.
• Step 3: Expand x to obtain a set S of child nodes, and
put x into the closed list.
• Step 4: For each node x’ in S, if it is not in the closed
list, add it to the open list along with the edge (x, x’).
• Step 5: Return to Step 2.

See Algorithm 1 in the textbook, p. 19

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/10
 Property of Algorithm 1
• It is easy to understand that search based on the open
list (and closed list) is complete in the sense that we can
always find the solution in a finite number of steps if the
search graph is finite.
• The edge (x, x’) is kept in the search process for
“restoring” the search path via “back-tracking”.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/11

 Depth-first search and
breadth-first search
• Algorithm I is a depth-first search if we implement the
open list using a stack.
• Algorithm I becomes the breadth-first search if the open
list is implemented using a queue.
• It is known the breadth-first search is better because
even for an infinite search graph, we can get the solution
in finite steps, if the solution exists.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/12

 Example 2.4
(p. 20 in the textbook)
Step Open List Closed List

0 (0,0) --

1 (1,0) (0,1) (0,0)

2 (2,0) (1,1) (0,1) (0,0) (1,0)

3 (1,1) (0,1) (0,0) (1,0) (2,0)

4 (2,1) (1,2) (0,1) (0,0) (1,0) (2,0) (1,1)

5 (2,2) (1,2) (0,1) (0,0) (1,0) (2,0) (1,1) (2,1)

6 (2,2)=Target node (0,0) (1,0) (2,0) (1,1) (2,1)

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/13

 Uniform-cost search
• Usually, the solution is not unique.
It is expected to find the BEST one.
• For example, if we want to travel
around the world, we may try to
find the fastest route; the most
economic route; or the route in
which we can visit more friends.
• The uniform-cost search algorithm
is a method for solving this problem.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/14

 Uniform-cost search
• Step 1: Add the initial node x0 and its cost C(x0)=0 to the
open list.
• Step 2: Get a node x from the top of the open list. If the
open list is empty, stop with failure. If x is the target node,
stop with success.
• Step 3: Expand x to get a set S of child nodes, and move
x to the closed list.
• Step 4: For each x’ in S but not in the closed list, find its
accumulated cost C(x’)=C(x)+d(x,x’); and add x’, C(x’),
and (x, x’) to the open list. If x’ is already in the open list,
update its cost and link if the new cost is smaller.
• Step 5: Sort the open list based on the node costs, and
return to Step 2.
Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/15
 Uniform-cost search
• During uniform-cost search, we can always find
the best path from the initial node to the current
node. That is, when search stops with success,
the solution must be the best one.
• In the algorithm, c(x) is the cost of the node x
accumulated from the initial node; and d(x,x’) is
the cost for state transition (e.g. the distance
between to adjacent cities).
• If we set d(x,x’)=1 for all edges, uniform-cost
search is equivalent to the breadth-first search.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/16

Example 2.5: Search a path with
the minimum cost
１
(0,2) (1,2) (2,2)

２ １ １
３
(0,1) (1,1) (2,1)

２ ３
５
１
(0,0) (1,0) (2,0)

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/17

Example 2.5: Search the path with
the minimum cost
Step Open List Closed List
0 {(0,0),0} --
1 {(0,1),2}, {(1,0),5} (0,0)
2 {(0,2),4}, {(1,0),5} (0,0) (0,1)
3 {(1,0),5}, {(1,2),5} (0,0) (0,1) (0,2)
4 {(1,2),5},{(2,0),6}, {(1,1),8} (0,0) (0,1) (0,2) (1,0)
5 {(2,0),6}, {(1,1),6} (0,0) (0,1) (0,2) (1,0) (1,2)
6 {(1,1),6} (0,0) (0,1) (0,2) (1,0) (1,2) (2,0)
7 {(2,1),9} (0,0) (0,1) (0,2) (1,0) (1,2) (2,0)
(1,1)
8 {(2,2),10} (0,0) (0,1) (0,2) (1,0) (1,2) (2,0)
(1,1) (2,1)
9 (2,2)=Target node (0,0) (0,1) (0,2) (1,0) (1,2) (2,0)
(1,1) (2,1)

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/18

 Homework for lecture 3
-- programming assignment
• Down-load the skeleton, and make a program for depth-first search
and breadth-first search.
• The graph is given below. The initial node is A, and the target node
is E. The costs of the edges are also given.

B 4 C 8 D
3 2

A 5 3 8 3 E

4 H G F
2 4

• Differences between this program and the one of last class:

– Input the node using alphabets;
– Stop when the target node is found; and
– Output the costs during search.
Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/19
 Homework for lecture 3
-- algorithm assignment
• For the maze problem
shown in left figure (Fig. (0,2) (1,2) (2,2)
2.2, p. 14 in the textbook),
find a path from (0,0) to
(2,2) using breadth-first (0,1) (1,1) (2,1)

search.
• Summarize the results (0,0) (1,0) (2,0)
using a table similar to
slide 13 (or Table 2.3, p.
20 in the textbook).

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/20

 How to write and submit the report?

• The file “summary_03.txt” should contain the following

contents:
– What are the algorithms used in this project?
– Describe the algorithms briefly based on your understanding.
– Explain the meaning of the results obtained by running the
completed program.
• Put the result of the “algorithm assignment” and the
contents written in the file “summary_03.txt” together into
one file (in MS-Word or other form), convert the file to
pdf-form, and submit it before the specified deadline.

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/21

 Quizzes
• What is the main problem of “random search” ?

• What is the main problem of “search with closed list”?

• How to implement the open list if we want to do breadth-first search?

• What is the relation of uniform-cost search and breadth-first search?

Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/22