=== p1 ===
Introduction to 
Artificial Intelligence
Chapter 3
Solving Problems by Searching
Wei-Ta Chu (朱威達)
1

=== p2 ===
• Goal-based agents consider future actions and the desirability of 
their outcomes. This chapter describes one kind of goal-based 
agent called a problem-solving agent. 
• In this chapter, we limit ourselves to the simplest kind of task 
environment (PEAS: Performance, Environment, Actuators, 
Sensors), for which the solution to a problem is always a fixed 
sequence of actions. 
Introduction
2

=== p3 ===
• The process of looking for a sequence of actions that reaches the 
goal is called search. A search algorithm takes a problem as input 
and returns a solution in the form of an action sequence. Once a 
solution is found, the actions it recommends can be carried out. 
This is called the execution phase. 
Problem-Solving Agents
3

=== p4 ===
• An example problem: moving from Arad to Bucharest
Problem-Solving Agents
4

=== p5 ===
• A problem can be defined formally by five components
• Initial state – In(Arad)
• A description of the possible actions -- {Go(Sibiu), Go(Timisoara), 
Go(Zerind)}
• A description of what each action does (transition model) -- 
RESULT(In(Arad), Go(Zerind)) = In(Zerind)
• The goal test, which determines whether a given state is a goal state -- 
In(Bucharest)
• A path cost function that assigns a numeric cost to each path
• A solution to a problem is an action sequence that leads from the initial state 
to a goal state. Solution quality is measured by the path cost function.
Well-Defined Problems and Solutions
5

=== p6 ===
• 8-puzzle problem
Formulating Problems
6

=== p7 ===
• 8-queens problem
• A queen attacks any piece in the same row, column 
or diagonal.
Formulating Problems
7

=== p8 ===
• Touring problems – route-finding problem
• Traveling salesperson problem – route-finding problem
• VLSI layout problem
• Robot navigation -- – route-finding problem
• …
Real-World Problems
8

=== p9 ===
• Search algorithms work by considering various possible action sequences. The 
possible action sequences starting at the initial state form a search tree with 
the initial state at the root; the branches are actions and the nodes correspond 
to states in the state space of the problem. 
Searching for Solutions
9

=== p10 ===
Infrastructure for Search Algorithms
10
• For each node n of the tree, we have a structure containing four 
components

=== p11 ===
We can evaluate an algorithm’s performance in four ways:
• Completeness: Is the algorithm guaranteed to find a solution when there is 
one? 
• Optimality: Does the strategy find the optimal solution? 
• Time complexity: How long does it take to find a solution?
• Space complexity: How much memory is needed to perform the search?
Measuring Problem-Solving Performance
11

=== p12 ===
• Uninformed search (also called blind search) 
• The strategies have no additional information about states beyond that 
provided in the problem definition. All they can do is generate successors and 
distinguish a goal state from a non-goal state. 
• All search strategies are distinguished by the order in which nodes are 
expanded. 
• Strategies that know whether one non-goal state is “more promising” than 
another are called informed search or heuristic search strategies.  
Uninformed Search Strategies
12

=== p13 ===
• Breadth-first search (BFS)
• The root node is expanded first, 
then all the successors of the 
root node are expanded next, 
then their successors, and so on.
Uninformed Search Strategies
13

=== p14 ===
• Breadth-first search (BFS)
• Imagine searching a uniform tree where every state has b successors. 
The root of the search tree generates b nodes at the first level, each of 
which generates b more nodes, for a total of b2 at the second level. 
Each of these generates b more nodes, yielding b3 nodes at the third 
level, and so on. 
• Suppose that the solution is at depth d. The total number of nodes 
generated is
Uninformed Search Strategies
14

=== p15 ===
• Breadth-first search (BFS)
Uninformed Search Strategies
15

=== p16 ===
• Uniform-cost search (AI) or Dijkstra’s algorithm (Theoretical CS)
• Uniform-cost search expands the node n with the lowest path cost g(n). 
• The algorithm tests for goals only when it expands a node, not when it 
generates a node
Uninformed Search Strategies
16
(1)
expanded
generated
(2)
expanded
generated
(3)
expanded
(1) 80+97=177
(2) 99+211=310
(3) 80+97+101=278
uninformed 的意思不是「完全沒有任何資
訊」，而是「沒有使用任何關於goal 還有多
遠的額外估計資訊」。

=== p17 ===
• Uniform-cost search (AI) or Dijkstra’s algorithm (Theoretical CS)
• Uniform-cost search is optimal in general. Uniform-cost search 
expands nodes in order of their optimal path cost. 
• Uniform-cost search is guided by path costs rather than depths.
• When all step costs are the same, uniform-cost search is similar to 
breadth-first search. 
Uninformed Search Strategies
17

=== p18 ===
• Depth-first search (DFS)
• Expands the deepest node in the current frontier of the search tree.
Uninformed Search Strategies
18

=== p19 ===
• Depth-first search (DFS)
• Time complexity: The time complexity of depth-first graph 
search is bounded by the size of the state space. A depth-
first tree search, on the other hand, may generate all of the          
nodes in the search tree, where m is the maximum depth of 
any node. m can be much larger than d (the depth of the 
shallowest solution).  
Uninformed Search Strategies
19

=== p20 ===
• Depth-first search (DFS)
• Space complexity: A depth-first tree search needs to store 
only a single path from the root to a leaf node, along with 
the remaining unexpanded sibling nodes for each node on 
the path. 
• For a state space with branching factor b and maximum 
depth m, DFS requires storage of only             nodes.
Uninformed Search Strategies
20

=== p21 ===
• Depth-limited search
• Supply depth-first search with a predetermined depth limit 
• Incompleteness
• Nonoptimal  
• Sometimes, depth limits can be based on knowledge of the problem. 
For example, if we check carefully, we would discover that any city 
can be reached from any other city in at most 9 steps, i.e., 
leads to a more efficient depth-limited search. 
Uninformed Search Strategies
21

=== p22 ===
• Iterative deepening DFS
• Iterative deepening search (or iterative deepening depth-first search) is 
a general strategy, often used in combination with depth-first tree 
search, that finds the best depth limit.
• It does this by gradually increasing the limit—first 0, then 1, then 2, 
and so on—until a goal is found.
• Iterative deepening combines the benefits of depth-first and breadth-
first search. Like DFS, its memory requirements are modest: O(bd) to 
be precise. Like BFS, it is complete when the branching factor is finite 
and optimal when the path cost is a nondecreasing function of the depth.
Uninformed Search Strategies
22

=== p23 ===
• Iterative deepening DFS
• 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. 
Uninformed Search Strategies
23

=== p24 ===
• Iterative deepening DFS
• Iterative deepening search may seem wasteful because states are 
generated multiple times. It turns out this is not too costly. 
• The reason is that in a search tree with the same (or nearly the same) 
branching factor at each level, most of the nodes are in the bottom level, 
so it does not matter much that the upper levels are generated multiple 
times. 
Uninformed Search Strategies
24

=== p25 ===
• Bidirectional search
• Run two simultaneous searches—one forward from the initial state and 
the other backward from the goal—hoping that the two searches meet 
in the middle. 
• The motivation is that                      is much less than 
• Bidirectional search is implemented by replacing the goal test with a 
check to see whether the frontiers of the two searches intersect; if they 
do, a solution has been found.
Uninformed Search Strategies
25

=== p26 ===
• Bidirectional search
• How to search backward? This is not easy. 
• Let the predecessors of a state x be all those states that have x as a 
successor. Bidirectional search requires a method for computing 
predecessors. When all the actions in the state space are reversible, the 
predecessors of x are just its successors.
• For the 8-puzzle and for finding a route in Romania, there is just one 
goal state, so the backward search is very much like the forward search.
• If the goal is an abstract description, such as the goal that “no queen 
attacks another queen”, then bidirectional search is difficult to use.
Uninformed Search Strategies
26

=== p27 ===
• Informed search strategy—one that uses problem-specific 
knowledge hints about the location of goals—can find 
solutions more efficiently than can an uninformed strategy. 
• The hints come in the form of a heuristic function, denoted 
h(n):
• h(n) = estimated cost of the cheapest path from the state at 
node n to a goal state. 
Informed (Heuristic) Search Strategies
27

=== p28 ===
• Greedy best-first search
• Expand the node that is closest to the goal, on the grounds that this is 
likely to lead to a solution quickly. Thus, it evaluates nodes by using just 
the heuristic function; that is, f(n) = h(n). 
• In this example, use the straight-line distance heuristic
Informed (Heuristic) Search Strategies
28

=== p29 ===
• Greedy best-first search
• Greedy best-first search using 
hSLD finds a solution without 
ever expanding a node that is 
not on the solution path; 
hence, its search cost is 
minimal. 
• However, this solution is not 
optimal
Informed (Heuristic) Search Strategies
29

=== p30 ===
• Greedy best-first search
• This solution is not optimal, however: the path via Sibiu and Fagaras to 
Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea 
and Pitesti. 
• Greedy best-first tree search is complete in finite state spaces, but not 
in infinite ones. 
• With a good heuristic function, the complexity can be reduced 
substantially. 
Informed (Heuristic) Search Strategies
30

=== p31 ===
• A* search
• The most widely known form of best-first search
• It evaluates nodes by combining g(n), the cost to reach the node, and 
h(n), the cost to get from the node to the goal. 
• g(n) gives the path cost from the start node to node n, and h(n) is the 
estimated cost of the cheapest path from n to the goal. 
• f(n) = g(n) + h(n) is the estimated cost of the cheapest solution through 
n. 
Informed (Heuristic) Search Strategies
31

=== p32 ===
• A* search: conditions for optimality – admissibility and 
consistency
• The first condition we require for optimality is that h(n) be 
an admissible heuristic. An admissible heuristic is one that 
never overestimates the cost to reach the goal. 
• Example: straight-line distance that we used in getting to 
Bucharest
Informed (Heuristic) Search Strategies
32

=== p33 ===
• A* search: conditions for optimality – admissibility and consistency
• A second, slightly stronger condition called consistency (or sometimes 
monotonicity) is required only for applications of A* to graph search.
• A heuristic h(n) is consistent if, for every node n and every successor n’ 
of n generated by any action a, the estimated cost of reaching the goal 
from n is no greater than the step cost of getting to n’ plus the estimated 
cost of reaching the goal from n’
This is a form of the general triangle inequality. 
Informed (Heuristic) Search Strategies
33

=== p34 ===
• A* search
Informed (Heuristic) Search Strategies
34

=== p35 ===
• A* search
Informed (Heuristic) Search Strategies
35