Chapter3: Problem solving through

uninformed and informed search

Course Title:Introduction to Artificial Intelligence

Course Code: ITec3151

Credit hour:3

Instructor Name: Akalu Assefa (MSc)

04/21/2024 Chapte2: Search Algorithm 1

 Search Algorithms
Search Algorithm
Uniformed search Informed search

BFS Ao* search

DFS
Hill A* search
8-puzzle Generate
climbing Constraint
problem and test
satisfaction

04/21/2024 Chapte2: Search Algorithm 2

 Uniformed search
• It is also called blind of exhaustive search
• two types : BFS(Breadth First search) and
DFS(depth first search)
1) BFS(Breadth First search): this is
blind/exhaustive search algorithm in which
search start from initial node and searches
level by level up to goal node found.
• Search terminates when a solution is found,

04/21/2024 Chapte2: Search Algorithm 3

 Uniformed search…
Example:
let Initial state= A goal state = J and M
leve0

leve1

leve2

leve3

Fig1: BFS leve4

04/21/2024
Chapte2: Search Algorithm
 Uniformed search…

Nodes are explored in the level like

leve0,level1,level2,level3,level as follows
ABCDEFGHIJKLM
I G1 G2

• The goal node J will be found before the goal node M.

• Search requires considerable memory resource.
• Similar to BFS, DFS search requires considerable memory
space
04/21/2024 Chapte2: Search Algorithm 5
 Uniformed search…
2) DFS(Depth First Search):is also
blind/exhaustive search algorithm in which
search starts at initial node and searches up to
some depth in one direction.
• If goal node is found, it stop the search
process, otherwise you can do backtracking.

04/21/2024 Chapte2: Search Algorithm 6

 Uniformed search…
Example:
Let initial node=A and goal node=M and J

Fig2: DFS
04/21/2024 Chapte2: Search Algorithm 7
 Uniformed search…
• Nodes are explored as A B D E H L M I N O F GJ
I G1 G2

•The goal node M will be found before J the goal node

•Similar to BFS, DFS also requires considerable memory space

04/21/2024 Chapte2: Search Algorithm 8

 Informed Search
• It is also called heuristic/intelligent search
• It is technique that improve the efficiency of search
process.
• For complex problems, traditional algorithms are unable to
find the solution with some limits of time & space.
• Hence heuristic techniques are used to solve complex
problems.
 types of informed search:
8-puzzle problem
Generate and test
A* search
AO* search
04/21/2024
Hill climbing Chapte2: Search Algorithm
9
 Informed Search:8-puzzle problem:

• State space: Configuration of 8-tiles on the

board.
• Action:“Move tiles towards blank spaces”
• Direction: Left, Right, Up, Down

04/21/2024 Chapte2: Search Algorithm 10

 Informed Search:8-puzzle problem …

Approaches to solve 8-puzzle problem

Approach1: count correct position of tiles when compared with
goal state.
• In this approach the highest heuristic value is the best it is
and other values are ignored
Approach2: count incorrect position tiles when compared with
goal state
• In this approach the lowest heuristic value is the best it is and
other values are ignored
• Approach3: count how far away each tile from its position
when compared with goal state.
• In this approach the lowest heuristic value the best it is and
other values are ignored.
• This method is preferable when there is ambiguities.
04/21/2024 Chapte2: Search Algorithm 11
 Informed Search:8-puzzle problem …

Compute the following 8-puzzle problem using three approaches?

Given

Initial state Goal state

04/21/2024 Chapte2: Search Algorithm 12

method1: Solution

Initial state Goal state

04/21/2024 Chapte2: Search Algorithm 13

method2: Solution

Initial state Goal state

04/21/2024 Chapte2: Search Algorithm 14

method3: Solution
Initial state Goal state

04/21/2024 Chapte2: Search Algorithm 15

• Assignment2:
Compute the following 8-puzzle problem using
three approaches?

04/21/2024 Chapte2: Search Algorithm 16

 Informed Search : Generate and Test algorithm
• Acceptable for simple problems.
• There is the problem state space.
• Inefficient for problems with large space.
• This is disadvantage of generate and test search
algorithm

Fig3: problem state space

04/21/2024 Chapte2: Search Algorithm 17
 2. Generate and Test
Algorithm for Generate and Test
1.start with initial state
2.Apply technique
1.Produce a new state
3.Chech a new state
4. If new state is goal state search stop,
otherwise return to step2

04/21/2024 Chapte2: Search Algorithm 18

 2. Generate and Test…
Start

Initial
state

Apply technique

Produce
new state
YES
NO
New sate is goal state

Fig4: Flow chart for generate and test algorithm

STOP

04/21/2024 Chapte2: Search Algorithm 19

 3. Hill climbing
• Generate and test + direction toward the goal
state.
• Searching for goal=climbing to the top of hill

Fig5: Example of hill climbing

04/21/2024 Chapte2: Search Algorithm 20

• Algorithm:
1. Evaluate the initial state. If it is goal state, then return and
quit. Otherwise make initial state as the current state.
2. Loop until a solution is found
3) Select and apply operator on current sate to produce a
new state.
4) Evaluate the new state.
i) If it is goal state, then return & quit.
ii) If it is not goal state, but it is better than the current state, then
make it as new current state.
iii) If it is not better than current state, then go to step2

04/21/2024 Chapte2: Search Algorithm 21

 Types of hill climbing

1. Simple hill climbing

•It will produce only one successor at a time.
Example let S=initial node and G= goal node

=5

Figure6: example of simple hill climbing

04/21/2024 Chapte2: Search Algorithm 22

 2. Steepest-Ascent Hill climbing
Produce multiple successor at a time.
The best of successor produces further
successors.

S D
E

C 8
3
B
A
7 F
6
5 2

Fig7: Example of steepest Ascent hill climbing

04/21/2024 Chapte2: Search Algorithm 23
 Limitation of hill climbing
1. Local Maxima
• A state that is better than all of its neighbor states, but not better than some other
• For example In figure below , node C have better value than neighbor node A and B but it is not
better than node E, F and G
• This represents local maxima.
• You will not see other node in search space for goal state
• So search will see local maxima as goal state and stops search process without reaching
goal node .
• This is limitation of local maxima
Goal state

Local maxima

starts
04/21/2024
Fig9: Local Maxima Chapte2: Search Algorithm 24
 Limitation of hill climbing…
2. Plateau
•A plat area of search space in which all neighboring states have the same value
•So in plateau search stops at particular point because of plat value will found at
particular point.
•This is limitation of hill climbing
•Fore example, in figure below , node A,B And C have the same value.
•The equality represents plateau.

Goal state

Plateau

starts

04/21/2024
Fig10: Plateau Chapte2: Search Algorithm 25
3.Ridge: is special kind of local maxima. The
difference is it has sharp slope.
• When search find sharp slope, it detects that
Sharp slope as goal state and stop search
process
Ridge Goal state

starts

Fig11: ridge
04/21/2024 Chapte2: Search Algorithm 26
 Summary of limitation of hill climbing
Global
maxima
Local maxima

Ridge

plateau

limitation of hill climbing

Fig: limitation of hill climbing

•From global maxima you can stand and see all the other cases.
•The is only one global maxima but their may be multiple local maxima

04/21/2024 Chapte2: Search Algorithm 27

 4. A* search
•Also called Best First Search
•The lowest heuristic function value is called most
promising node and that node is expanded in
next level
• A* search has three function such as f(n), g(n) and h(n)
Law: f(n)= g(n)+h(n)
g(n)= edge cost
h(n)= estimated cost from node n to goal node
f(n)= estimated total cost of path from node n to goal node
•It has 2lists:
 {OPEN} and {CLOSE} lists.
 Initially the OPEN list contains initial node and CLOSE list
contains empty.
28
Example: Find shortest path and show which node expanded next and list for figure below
from initial node A to goal node J using A* search algorithm
Edge cost=1

Fig13: A* algorithm search

04/21/2024 Chapte2: Search Algorithm 29
 A* search…
• Solution:
• F(n)=g(n) +h(n Expanded next

Nodes Heuristic
A->A=0+10=10 A 10
B 3
A->B=1+3=4 C 5
A->C=1+5=6 D 1
E 4
A->D=1+1=2 F 6
G 6
A->D->E=1+1+4=6 H 5

A->D->F=1+1+6=8 I 2
J 0
A->D->E-I=1+1+1+2=5
Expanded Next
A->D->E->J=1+1+1+0=3 Best path
 A* search…
OPEN CLOSE
A {}
BCD A
BCEF AD
GHCEF ADB
GHCIJF ADBE

GOAL STATE

04/21/2024 Chapte2: Search Algorithm 31

• Exercise: Find shortest path and show which node
expanded next for figure below from initial node S to
goal node K using A* search algorithm?
Nodes Heuristic value

S 10
A 5
B 6
C 4
D 5
E 7
F 5
G 1
H 3
I 2
J 6
K 5
L 4
M 9
N 0

04/21/2024 Chapte2: Search Algorithm 32

 5. AO* Search(Problem Reduction)
•When a problem is divided into set of sub problems where each sub problems
can be solved separately and combination of these is solution.
•Also call And-Or graph algorithm.
•Fore example Blow figure shows that if you want to acquire TV, then you earn
some money and by Tv or get TV directly.
In this figure getting TV is problem one, Earning some money is problem two and buy Tv
is problem three and all of them Require solution.

Goal : acquire TV

GET TV
BUY TV
Earn some
money

Fig14: Example of And-Or graph

04/21/2024 Chapte2: Search Algorithm 33

 • In AO* search algorithm the best heuristic value
node is expanded next from initial node using
uniform cost.
• Example:
1) 2) 18 A
A
38
(9) B C D
(3) B D (5)
(4) C 17 9 27
E F G H I J
(5) (10) (3) (4) (15) (10)
04/21/2024 Chapte2: Search Algorithm 34
 6. Constraint satisfaction or crypt
arithmetic problem.
• The General problem that is used to find a
solution that satisfies a set of constraint.
Rule :
1.No two alphabets should have a single digit
2.Every alphabet will be given a single digit
3.If you add two digit you may or may not get carry
4.If at all carry occur it should be one
4. If at all carry is one the top most input could be
eight or nine
35
 Constraint satisfaction or crypt arithmetic
problem…
• Example: represent each of the following letters with a unique
digit from 0 to 9 using Constraint satisfaction or crypt
arithmetic problem solving rule?.
C R O S S
R O A D S
D A N G E R

04/21/2024 Chapte2: Search Algorithm 36

 Constraint satisfaction or crypt arithmetic problem…

• Solution
C could be 8 or 9 since it is top most alphabet.
At column 1 S+S=R which implies R is even number.
1. Let C=9 and S=2
S+S=R = 2+2=4 there fore R=4
Substitute;
94O22
4 O 3 1 2 incorrect because this equation implies that A=E=3 which violets rule2
13??34
DANGE R

04/21/2024 Chapte2: Search Algorithm 37

 Constraint satisfaction or crypt arithmetic problem...

2.Let S=3 ,S+S=R = 3+3=6 there fore R=6

Substitute;
96O33
6 O 5 1 3 correct
15 ? ? 4 6
D ANGER
Now the remaining letters are O,N,G.
And the remaining digits are 0,2,7,8
3. Let O=0
Substitute;
Substitute;
9 6033
6 0513
1 5 6 5 4 6 incorrect because this implies R=N=6 and A=G=5 which violets rule2
DA N G E R

04/21/2024 Chapte2: Search Algorithm 38

 Constraint satisfaction or crypt arithmetic problem…

3. Let O=2

Substitute;
9 6233
6 2513
1 5 8 7 4 6 correct
DA N G E R

There fore the alphabets are represented as

follows.
C R O S A D N G E
9 6 2 3 5 1 8 7 4
04/21/2024 Chapte2: Search Algorithm 39
 Constraint satisfaction or crypt arithmetic problem...

• Exercise: represent each of the following

letters with a unique digit from 0 to 9 using
Constraint satisfaction or crypt arithmetic
problem solving rule?.
T O M
N A G
G O A T

04/21/2024 Chapte2: Search Algorithm 40

 Backward and Forward Reasoning

Forward reasoning
• In forward reasoning the search start from initial
state and reaching to goal state.
Backward reasoning:
In back ward reasoning the search start from goal state
to reach initial node

Backward
reasoning Goal state

Forward
Initial state reasoning
 Problem Tree and Graph
• Tree is a graph in which any two vertices are connected by
exactly one simple path.
• In other words, tree is any connected graph
without cycles is a tree.
• Graph is any connected graph with cycle
Tree vs Graph
• In tree having only one path In graph there can be more than one
path
between any two vertices. In Graph, no. of edges depend
• In tree no. of edge is n-1 on the graph.
• In trees, there is parent child In Graph there is no parent child
relationship. relationship
 Problem Tree and Graph

Figure a: example of tree Figure b: example of graph