Module Title
Topic 2:
Problem Solving using Search
© NCC Education Limited
Topic 2 Problem Solving with Search - 2.2
Scope and Coverage
This topic will cover:
• Problem representation in state space
• Strategies for state space search
• Uninformed Search (Blind Search)
• Informed Search (Heuristic Search)
Topic 2 Problem Solving with Search - 2.3
Learning Outcomes
By the end of this topic students will be able
to:
• Construct simple state spaces.
• Select and apply appropriate search techniques in
problem solving.
Topic 2 Problem Solving with Search - 2.4
Problem Solving
• Problem solving agent is a goal-based agent that
can decide what to do by finding sequences of
actions that lead to desirable states, and then
choosing the best sequence.
• Goal formulation is the first step in problem
solving based on the current situation and the
agent’s performance measure.
Topic 2 Problem Solving with Search - 2.5
Problem Solving
• Problem formulation is an important step in
problem solving to decide what actions and states
to consider achieving the formulated goal.
• After formulating a goal and a problem to solve, the
agent calls a search algorithm to solve it.
• Once a solution is found the actions it recommends
can be executed.
Topic 2 Problem Solving with Search - 2.6
Problem Solving
• Example: On holiday in Romania; currently you are in the
city of Arad. Flight leaves tomorrow from Bucharest.
Formulate goal:
– get to Bucharest on time
Formulate problem:
– states: various cities
– actions: traverse between cities
Find solution:
– sequence of cities
(e.g. AradSibiuFagarasBucharest)
(Russell & Norvig, 2016)
Topic 2 Problem Solving with Search - 2.7
Search
• Search is the process of looking for a sequence of
actions that reaches the goal.
• It is one of the common problem-solving techniques
used in AI that systematically explores a space of
problem states.
Topic 2 Problem Solving with Search - 2.8
State Space Search
• A real-world problem can be represented as a state
space graph.
(Luger, 2011) (Luger, 2011)
The city of Königsberg Graph of the Königsberg bridge system
Topic 2 Problem Solving with Search - 2.9
State Space Search
• The components of a state space search:
– Initial state: the start state of the agent towards its goal.
– Actions: the possible actions available to the agent.
– Transition model: describe what each action does.
– Goal test: it determines if the given state is a goal state.
– Path cost: function that assigns a numeric cost to each path
– Solution: an action sequence that leads from the start state to the
goal state.
– Optimal solution: a solution with the lowest cost among solutions
(optional).
Topic 2 Problem Solving with Search - 2.10
State Space Search
• Example: Travelling salesperson problem
The nodes of a
graph represent
discrete states and
the arcs represents
transitions
between states.
• States: Cities
(Luger, 2011)
• Initial state: A
• Actions: Travel from one city to another connected by a road
• Goal test: The trip visits each city only once that starts and ends at A
• Path cost: Traveling time
Topic 2 Problem Solving with Search - 2.11
State Space Search
• Example: The 8-puzzle
• States?
• Initial state?
• Actions?
• Goal test?
• Path cost?
(Luger, 2011)
Topic 2 Problem Solving with Search - 2.12
State Space Search
• Example: The 8-puzzle
• States: Locations of tiles
• Initial state: Any state
• Actions: move blank tile to
the left, right, up, down
• Goal test: given goal state
• Path cost: 1 per move
(Luger, 2011)
Topic 2 Problem Solving with Search - 2.13
State Space Search
• State space search can operate in the forward
direction (data-driven) or the backward direction
(goal-driven).
(Luger, 2011)
Topic 2 Problem Solving with Search - 2.14
Search Algorithms
• A search algorithm takes a problem as input and
returns a solution.
• A solution is an action sequence, search
algorithms work by considering various possible
action sequences.
• A search strategy is defined by picking the order
of node expansion.
– Uninformed search
– Informed search
Topic 2 Problem Solving with Search - 2.15
Uninformed vs. Informed Search
Uninformed Search Informed Search
A.k.a. Blind search, exhaustive Heuristic search
search, brute-force search
Strategy Use no additional Use problem-specific knowledge
information about states beyond the problem definition to
beyond that provided in the guide whether one non-goal state
problem definition to is “more promising” than another
distinguish a goal state from towards a goal state
a non-goal state
Performanc Time consuming and Faster, less computational required
e impractical to solve very and can handle large search
large problems problems
Solution Guarantee the best solution Does not guarantee a solution, but
(if exists) high probability of getting an
optimal solution
Example of • Breadth-first search • Best first search (Greedy
algorithms • Depth-first search search)
• Uniform cost search • A* search
Topic 2 Problem Solving with Search - 2.16
Breadth-First Search
• Breadth-first search (BFS) is a simple search
algorithm for traversing a tree or a graph.
• BFS expands the shallowest unexpanded node first
using a FIFO (First-in, First-out) queue.
• BFS algorithm starts searching from the root node,
and all adjacent nodes are expanded before
expanding the descendants nodes.
Topic 2 Problem Solving with Search - 2.17
Breadth-First Search
• Traversing of a tree (or graph) using BFS
The root node
(or start node) is 1
Traversed sequence: 1, 2, 3, 4, 5, 6,
7, 8
Topic 2 Problem Solving with Search - 2.18
Breadth-First Search
• Algorithm
Topic 2 Problem Solving with Search - 2.19
Breadth-First Search
• Example
(Luger, 2011)
Question: Show the traversing using BFS if O is the goal node.
Topic 2 Problem Solving with Search - 2.20
Breadth-First Search
A trace of breadth-first search on the tree
Iteration Open Closed
0 [A] []
1 [B, C, D] [A]
2 [C, D, E, F] [B, A]
3 [D, E, F, G, H] [C, B, A]
4 [E, F, G, H, I, J] [D, C, B, A]
5 [F, G, H, I, J, K, L] [E, D, C, B, A]
6 [G, H, I, J, K, L, M] [F, E, D, C, B, A]
(L is not added as already on open)
7 [H, I, J, K, L, M, N] [G, F, E, D, C, B, A]
8 [I, J, K, L, M, N, O, P] [H, G, F, E, D, C, B, A]
9 [J, K, L, M, N, O, P, Q] [I, H, G, F, E, D, C, B, A]
10 [K, L, M, N, O, P, Q, R] [J, I, H, G, F, E, D, C, B,
A]
Topic 2 Problem Solving with Search - 2.21
Breadth-First Search
A trace of breadth-first search on the tree
Iteration Open Closed
11 [K, L, M, N, O, P, Q, R] [J, I, H, G, F, E, D, C, B, A]
12 [L, M, N, O, P, Q, R, S] [K, J, I, H, G, F, E, D, C, B, A]
13 [M, N, O, P, Q, R, S, T] [L, K, J, I, H, G, F, E, D, C, B, A]
14 [N, O, P, Q, R, S, T] [M, L, K, J, I, H, G, F, E, D, C, B, A]
15 [O, P, Q, R, S, T] [N, M, L, K, J, I, H, G, F, E, D, C, B,
A]
16 RETURN SUCCESS,
GOAL O IS FOUND
• Open is a queue that records generated nodes but not yet expanded
• Closed records nodes already expanded
Topic 2 Problem Solving with Search - 2.22
BFS of the 8-puzzle
(Luger, 2011)
Breadth-first search of the 8-puzzle, showing order in which states were removed from open.
Topic 2 Problem Solving with Search - 2.23
Checkpoint Summary
• Before an agent can start searching for solutions, a goal
must be identified, and a well-defined problem must be
formulated. A state space represents the environment of
a problem.
• A state space search consists of five main components:
the initial state, a set of actions, a transition model
describing the results of those actions, a goal test
function, a path cost function, and a solution with a path
through the state space from the initial state to a goal
state.
Topic 2 Problem Solving with Search - 2.24
Depth-First Search
• Depth-first search (DFS) is a recursive algorithm
for traversing a tree or a graph.
• DFS expands the deepest unexpanded node first
using a LIFO (Last-in, First-out) queue.
• DFS algorithm starts searching from the root node,
and all descendants nodes are expanded before
expanding the adjacent nodes.
Topic 2 Problem Solving with Search - 2.25
Depth-First Search
• Traversing of a tree (or graph) using DFS
Traversed sequence: 1, 2, 5, 6, 3, 4,
7, 8
Topic 2 Problem Solving with Search - 2.26
Depth-First Search
• Algorithm
Topic 2 Problem Solving with Search - 2.27
Depth-First Search
• Example
(Luger, 2011)
Question: Show the traversing using DFS if O is the goal node.
Topic 2 Problem Solving with Search - 2.28
Depth-First Search
A trace of depth-first search on the
tree
Iteratio Open Closed
n
0 [A] []
1 [B, C, D] [A]
2 [E, F, C, D] [B, A]
3 [K, L, F, C, D] [E, B, A]
4 [S, L, F, C, D] [K, E, B, A]
5 [L, F, C, D] [S, K, E, B, A]
6 [T, F, C, D] [L, S, K, E, B, A]
7 [F, C, D] [T, L, S, K, E, B, A]
8 [M, C, D] [F, T, L, S, K, E, B, A]
(L is not added as already on closed)
9 continue until either O is found or open ……................................
=[]
....
Question: How many iterations you need to get to the goal?
Topic 2 Problem Solving with Search - 2.29
DFS of the 8-puzzle
(Luger, 2011)
Depth-first search of the 8-puzzle, showing order in which states were removed from open. A
depth bound of 5 was imposed on this search to keep it from getting lost deep in the space.
Topic 2 Problem Solving with Search - 2.30
Uniform-Cost Search
• Uniform-cost search (UCS) is a search algorithm
for traversing a weighted tree or a graph.
• UCS expands node with the lowest path cost (g(n)
≥ 0, a step-cost function) using a priority queue.
• The goal test is applied to a node when it is
selected for expansion rather than when it is first
generated. This ensure optimal path cost.
Topic 2 Problem Solving with Search - 2.31
Uniform-Cost Search
• Traversing of a tree (or graph) using UCS
The start node Total path cost:
is 1 and the (1, 2, 6) 1 + 5 = 6
goal node is 6 (1, 4, 6) 3 + 5 = 8
1 4 3
2 5 5 1
There are two paths to the goal, the optimal path cost is
(1, 2, 6)
Topic 2 Problem Solving with Search - 2.32
Best First Search
• Best-first search is an algorithm in which a
node is selected for expansion based on an
evaluation function, f(n).
• A best-first search using a heuristic function,
h(n) as the evaluation function, f(n) =
h(n) is called a greedy search.
h(n) = estimated cost of the cheapest path from
the state at node n to a goal state
Topic 2 Problem Solving with Search - 2.33
Greedy Search
• Example: Finding a path from Arad to Bucharest
(Russell & Norvig, 2016) h(n) = straight-line
distance from n to the goal
Topic 2 Problem Solving with Search - 2.34
Greedy Search
• Example: Finding a path from Arad to Bucharest
The initial state
After expanding Arad
After expanding Sibiu
After expanding Faragas
795=366+235+176+0
Not optimal. Is there a
(Russell & Norvig, 2016) better way?
Topic 2 Problem Solving with Search - 2.35
A* Search
• A* search is commonly known form of best-first
search. It combines the greedy search with the
uniform-search strategy.
• Using the evaluation function:
f(n) = g(n)+ h(n)
g(n) = estimated cost of the shortest path
from the start state to node n
Topic 2 Problem Solving with Search - 2.36
A* Search
• Example: Finding a path from Arad to Bucharest
(Russell & Norvig, 2016)
Topic 2 Problem Solving with Search - 2.37
Measuring Search Algorithms
Performance
• Search strategies are evaluated using the criteria:
– completeness: does it always find a solution if one exists?
– optimality: does it always find a least-cost solution?
– time complexity: the time taken to find a solution.
– space complexity: amount of memory required to perform a search.
• Time and space complexity are measured in terms of:
– b: maximum branching factor of the search tree
– d: depth of the least-cost solution
– m: maximum depth of the state space (may be ∞)
Topic 2 Problem Solving with Search - 2.38
Measuring Search Algorithms
Performance
Criterion Breadth Depth- Uniform Greedy A*
-First First -Cost Search
Search Search Search
Completeness Yes* No Yes* No Yes
Optimality Yes* No Yes No Yes
Time complexity O(bd+1) O(bm) ≈ O(bd) O(bd) O(bd)
Space O(bd+1) O(bm) ≈ O(bd) O(bd) O(bd)
complexity
Topic 2 Problem Solving with Search - 2.39
Summary
• Uninformed search methods have access only to the
problem definition.
• Informed search methods may have access to a
heuristic function h(n) that estimates the cost of a
solution from n.
• The performance of heuristic search algorithms
depends on the quality of the heuristic function.
• Search algorithms are judged on the basis of
completeness, optimality, time complexity, and space
complexity.
Topic 2 Problem Solving with Search - 2.40
References
• Russell, S., & Norvig, P. (2016). Artificial
Intelligence: A Modern Approach: Pearson
• Luger, G. F. (2011). Artificial Intelligence: Structures
and Strategies for Complex Problem Solving:
Pearson Education.
Topic 2 – Problem Solving using Search
Any Questions?
