Topic 2 – Problem Solving using Search Artificial Intelligence
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.
V 1.0 Visuals Handout – Page 1
Topic 2 – Problem Solving using Search Artificial Intelligence
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)
V 1.0 Visuals Handout – Page 2
Topic 2 – Problem Solving using Search Artificial Intelligence
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).
V 1.0 Visuals Handout – Page 3
Topic 2 – Problem Solving using Search Artificial Intelligence
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
10
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)
11
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)
12
V 1.0 Visuals Handout – Page 4
Topic 2 – Problem Solving using Search Artificial Intelligence
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)
13
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
14
Topic 2 Problem Solving with Search - 2.15
Uninformed vs. Informed Search
Uninformed Search Informed Search
A.k.a. Blind search, exhaustive search, Heuristic search
brute-force search
Strategy Use no additional information Use problem-specific knowledge beyond
about states beyond that provided the problem definition to guide whether
in the problem definition to one non-goal state is “more promising”
distinguish a goal state from a non- than another towards a goal state
goal state
Performance Time consuming and impractical to Faster, less computational required and can
solve very large problems handle large search problems
Solution Guarantee the best solution Does not guarantee a solution, but high
(if exists) probability of getting an optimal solution
Example of • Breadth-first search • Best first search (Greedy search)
algorithms • Depth-first search • A* search
• Uniform cost search
15
V 1.0 Visuals Handout – Page 5
Topic 2 – Problem Solving using Search Artificial Intelligence
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.
16
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
17
Topic 2 Problem Solving with Search - 2.18
Breadth-First Search
• Algorithm
18
V 1.0 Visuals Handout – Page 6
Topic 2 – Problem Solving using Search Artificial Intelligence
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.
19
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]
20
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
21
V 1.0 Visuals Handout – Page 7
Topic 2 – Problem Solving using Search Artificial Intelligence
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.
22
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.
23
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.
24
V 1.0 Visuals Handout – Page 8
Topic 2 – Problem Solving using Search Artificial Intelligence
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
25
Topic 2 Problem Solving with Search - 2.26
Depth-First Search
• Algorithm
26
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.
27
V 1.0 Visuals Handout – Page 9
Topic 2 – Problem Solving using Search Artificial Intelligence
Topic 2 Problem Solving with Search - 2.28
Depth-First Search
A trace of depth-first search on the tree
Iteration Open Closed
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?
28
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.
29
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.
30
V 1.0 Visuals Handout – Page 10
Topic 2 – Problem Solving using Search Artificial Intelligence
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)
31
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
32
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
33
V 1.0 Visuals Handout – Page 11
Topic 2 – Problem Solving using Search Artificial Intelligence
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?
34
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
35
Topic 2 Problem Solving with Search - 2.36
A* Search
• Example: Finding a path from Arad to Bucharest
(Russell & Norvig, 2016)
36
V 1.0 Visuals Handout – Page 12
Topic 2 – Problem Solving using Search Artificial Intelligence
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 ∞)
37
Topic 2 Problem Solving with Search - 2.38
Measuring Search Algorithms
Performance
Criterion Breadth- Depth-First Uniform- Greedy A*
First Search Search Cost 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 complexity O(bd+1) O(bm) ≈ O(bd) O(bd) O(bd)
38
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.
39
V 1.0 Visuals Handout – Page 13
Topic 2 – Problem Solving using Search Artificial Intelligence
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.
40
Topic 2 – Problem Solving using Search
Any Questions?
41
V 1.0 Visuals Handout – Page 14
