Search Algorithms
Quick Recap
BFS DFS
Queue Stack
Uninformed Search / Blind Search
ALEX
• The uninformed search does not
contain any domain knowledge
such as closeness, the location of
the goal.
• Uninformed search applies a way
in which search tree is searched
without any information about
the search space.
• also called blind search
Informed Search / Heuristic Search
ALEX
• Informed Search algorithms use
domain knowledge
• In an informed search, problem
information is available which
can guide the search.
• Informed search strategies can
find a solution more efficiently
than an uninformed search
strategy.
Breadth First
Search
Uninformed
Search / Blind Depth First Search
Search
Uniform Cost
Search
Search Algorithms
A* Search
Informed Search /
Heuristic Search
Best First Search
Algorithm(Greedy
search)
Adversarial Search
Uniform Cost Search
Weighted Graph Unweighted Graph
Kindly Draw the
Uniform Cost Search graph in your
book
Expanding / Exploring the
Source Node
Source
1
3 5
1 A 3 B 5 C
Priority Queue:
[A(1), B(3), C(5)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
4 G
Exploring A
Priority Queue:
[B(3), C(5), G(4)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
3 5
4 G 8 F
Exploring B
Priority Queue:
[C(5), G(4), F(8)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
3 5
4 G 8 F
Exploring G
Priority Queue:
[C(5), F(8)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
3 5 2
4 G 8 F 7 E
Exploring C
Priority Queue:
[F(8), E(7)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
3 5 2
4 G 8 F 7 E
1
Exploring E
Priority Queue: 8 Goal
[F(8)]
Uniform Cost Search
Source
1
3 5
1 A 3 B 5 C
3 5 2
4 G 8 F 7 E
1
Path to reach Goal:
Source -> C -> E -> Goal 8 Goal
Total Cost : 8
G 2
D
1 2
1
Uniform Cost E F
5
Search C
3
4
B
1 A
Problem for you to solve!
Start Node A
Uniform Cost
Search
Problem for you to solve!
Start Node S
Uniform Cost Search
• Uniform Cost Search Algorithm is a uninformed search
algorithm in AI
• This algorithm uses the lowest cumulative cost to find
a path from the source node to the goal node
• The Uniform-cost search is implemented using a
Priority Queue
Breadth First
Search
Uninformed
Search / Blind Depth First Search
Search
Uniform Cost
Search
Search Algorithms
A* Search
Informed Search /
Heuristic Search
Best First Search
Algorithm(Greedy
search)
Adversarial Search
Informed Search / Heuristic Search
• Informed Search algorithms use ALEX
domain knowledge
• In an informed search, problem
information is available which
can guide the search.
• Informed search strategies can
find a solution more efficiently
than an uninformed search
strategy.
Heuristic Search
Heuristic Search
Spot the Difference!
A* algorithm
• We use the following equation to select the successor node:
f (n) = g (n) + h (n)
f (n) = estimated cost of the cheapest solution
g (n) = cost of the cheapest path from the initial state to node n
h (n) = cost of the cheapest path from node n to a goal state
A* Search Algorithm
• We use the following equation to select the successor node:
Source 11.5
f (n) = g (n) + h (n) 4
3
Source 11.5
10.1 A 3.5 B
f (a) = g (a) + h (a) f (b) = g (b) + h (b) 2 3.5
4+10.1 = 14.1
3+3.5 = 6.5
9.2 C 0 Goal
A B
A* Search Algorithm
• We use the following equation to select the successor node:
Source 11.5
f (n) = g (n) + h (n) 4
3
Source 11.5
10.1 A 3.5 B
f (a) = g (a) + h (a) f (b) = g (b) + h (b) 2 2
4+10.1 = 14.1
3+3.5 = 6.5
9.2 C 0 Goal
A B
f (g) = g (g) + h (g)
Why didn’t I explore Node C? Goal 3+2+0 = 5
A* algorithm Problem to be solved!
f (n) = g (n) + h (n) S
4+9.2 = 13.2 D A 3+10.1 = 13.1
4+2+7.1 =
13.1 E A 4+5+10.1 = 19.1
3+5+9.2 = 17.2 D B 3+4+5.8 = 12.8
B F 4+2+4+3.5 =
4+2+5+5.8 = 13.5
3+4+5+7.1 = 19.1 E C 3+4+4+3.4 = 14.4
16.8
4+2+4+3.5+0 = G
13.5
FRONT
1 2
10 B
C
3 5
4 D
Goal 5
A* algorithm Problem to be solved!
Solve it using A* algorithm
f (n) = g (n) + h (n) Solve it using A* algorithm
S
10+4 = 14 5+13 = 18 6+10 = 16
C B A
5+7+2=14 5+6+4 = 15
E 6+6+4 = 16
D
10+6 + 2 = 18 D E
5+6+4+1= 16
5+7+6+1 = 19 6+6+4+1 = 17
F F
F B F
10+6+6+1 = 23 6+6+6+13 = 31
5+6+4+3+0 = 18
6+6+4+3 = 19
G
G
5
Solve it using A* algorithm
Solve it using A* algorithm
Solve it using A* algorithm
Solve it using A* algorithm
Solve it using A* algorithm
Solve it using A* algorithm
Breadth First
Search
Uninformed
Depth First
Search / Blind
Search
Search
Uniform Cost
Search
Search
Algorithms A* Search
Informed Search
/ Heuristic
Search Best First Search
Algorithm
Adversarial
Search
Best First Search
f (n) = h (n)
Solve it using Best First
Search
Remember,
f (n) = h (n)
Constraint Satisfaction Problem (CSP)
Constraint?
something that controls what you do by
keeping you within particular limits
Satisfaction?
fulfilment of expectations,
or needs
Constraint Satisfaction Problem (CSP)
• Consists of three components:
• The set of variables X = {X1, X2, X3…….XN}
• The set of Domains D = {D1, D2, D3……DN}
• The set of Constraints = {C1, C2,C2 …….CN}
Example of CSP: Map Coloring
Problem: color each region
either red, green or blue in
such a way that no
neighboring regions have the
same color
Example of CSP: Map Coloring
Variable : WA, SA, NT, QL,
NSW, V, T
Domain : Red , Green, Blue
Constraints : adjacent regions
must have different colors
Example : SA ! = Q
Example of CSP: Sudoku
Variable : Each Square (open)
Domain : {1,2,……,9}
Constraints :
• All the values in each row should be
from 1-9 without repetitions.
• All the values in each column
should be from 1-9 without
repetitions.
• All the values in 3X3 should also be
from 1-9 without repetitions.
Example of CSP: Map Coloring
Problem: color each region
either red, green or blue in
such a way that no
neighboring regions have the
same color
We will use BACKTRACKING method
to solve Constraint Satisfaction
Problem (CSP)
Map Coloring using Backtracking Method
Variables?
WA, NT, SA, Q, NSW, V
Domains?
Red, Green, Blue
Constraints:
WA != NT, WA != SA, NT !=SA,
NT != Q, SA !=Q, Q !=NSW,
NSW !=SA, NSW != V, SA!=V
Map Coloring using Backtracking Method
Constraints:
Which Uninformed
Search method was WA != NT, WA != SA, NT !=SA,
used here? NT != Q, SA !=Q, Q !=NSW,
WA WA WA
NSW !=SA, NSW != V, SA!=V
NT NT NT
SA SA SA
Q Q Q
NT
Q
NSW NSW NSW
WA
V V V SA NSW
WA = Red, NT=Green, SA = Blue, Q= Red, NSW= Green, V = Blue V
