2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.

‫م‬

Lec-3

1. Breadth First Search(BFS):

In this algorithm, all nodes on one level of the tree are examined before any of the
nodes on the next level.
This algorithm is guaranteed to find a solution if one exists, and this search dose
not only provide a solution but the shortest path of nodes between the start and
goal state.

Level 0 1

Level 1 2 3 4

Level 2 5 6 7 8 9

10 11 12 13 14 15 16
Level 3
Goal

The advantages of BFS

1. It finds the shortest path of nodes.
2. No
backtracking.
3. It is good when the number of alternatives at the choosing points is not too
large.

The disadvantages of BFS

1. It requires a lot of memory, the number of nodes increases exponentially
with the level number.
2. It requires a lot of work if the shortest path is quit long,
the number of nodes increases exponentially with the long of path.

24
2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

3. In situation in which there are many paths that lead to solutions then DFS is
more suitable to apply than BPS.
‫) هو أكثر مالءمة لتطبيق من‬DFS( ‫في الحالة التي توجد فيها العديد من المسارات التي تؤدي إلى حلول إذن‬
.)BPS(
__________________________________________________________________

-Breadth First Search(BFS) method:

Step1: from a queue consisting of the root node at the beginning.
Step2: until the queue is empty or the goal node has been reached determine if the
first element in the queue is the goal node:
a. If the first element is a goal node, then exit with the solution.
b. Otherwise, remove it from the queue and add it's children, if any to the end
(back) of the queue.
Step3: if the goal has been found; then declare success, otherwise declare failure.

Breadth First Search(BFS) Algorithm:

Initialize: open = [start state], close = [];
While open <> [] do
Remove the first state from left of open, call it x.
If x is the goal then return (path)
Generate all children of x
Put x in close
Remove from open any children of x already in open.
Discard any child of x already in close
Add the remaining children of x to the right of open
Return (fail) % no states left
End
__________________________________________________________________

25
 2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

Ex: Find the Goal (G) using Breadth First Search(BFS) Algorithm to the
following tree.

B F C D

E J G

H I
Start state = A
Goal state = G
Iteration Open Close
0
0 [(A )] []
A A A A 0
1 [(B ), (F ), (C ), (D )] [(A )]
A A A B B
2 [(F ), (C ), (D ), (E ), (F )] [(B ), (A0)]
A

3 [(CA), (DA), (EB), (JF), (GF)] [(FA), (BA), (A0)]

4 [(DA), (EB), (JF), (GF) (FC), (GC)] [(CA), (FA), (BA), (A0)]
5 [(EB), (JF), (GF), (FC)] [(DA), (CA), (FA), (BA), (A0)]
6 [(JF), (GF), (FC), (HE), (IE)] [(EB), (DA), (CA), (FA), (BA), (A0)]
7 [(GF), (FC), (HE), (IE)] [(JF), (EB), (DA), (CA), (FA), (BA), (A0)]
8 G is Goal [(GF), (JF), (EB), (DA), (CA), (FA), (BA), (A0)]
.‫نقرأ من اليسار بشكل أفقي ونضع األبناء على اليمين‬
.‫) األحدث تواجد‬Node(‫نقوم بحذف الـ‬
State space: all nodes of graph
Search space: A, B, F, C, D, E, J, G
Solution path: A  F  G
)First In First Out( )FIFO( ‫) أي‬Queue(‫) مبدأ الـ‬BFS( ‫وتستخدم خوارزمية‬

)Queue( ‫أسلوب‬

A B F C D F C D E C D E J G

D E J G F E J G F J G F H I G F H I
26
2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

Comparison between DFS and BFS

DFS BFS
1. Depend on Stack (LIFO) 1. Depend on Queue (FIFO)
2. Used when the goal is far from the 2. When the goal is near from the
root or start state. root or start state.
3. The search is vertically in depth 3. The search is horizontally for all
from left until we reach the goal levels from left until we reach the
goal
4. Wasting time because it contains 4. No backtracking, so no waste time.
backtracking
5. Not always guaranteed converges. 5. Always guaranteed converges
6. It is less complex, it doesn't store 6. It is complex, because it needs a lot
all the nodes, so it needs less of memory.
memory.
__________________________________________________________________

3. Hybrid First Search (HFS) Algorithm:

Step l: set current depth bound = 1.
Step 2: put the initial node into open.
Step 3: while open <> empty and depth with in depth bound do
Begin
Remove left most state from open call it x;
If x is a goal then return (success)
Else begin
Generate children of x;
Put x on closed;
Eliminate children of x on open or closed;
Put reaming children on left of open;
End;
End;
Step 4: increment depth bound by 1 and repeat through 2.

27
 2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

Ex: Find the Goal (G) using Hybrid First Search (HFS) Algorithm to the
following tree: (bound = 2 for stopping)

Level 0 A

Level 1 B F C D

Level 2 E J G
G

Level 3 H I

Iteration Open Close

0
0 [(A )] []
1 [(BA), (FA), (CA), (DA)] 0
[(A )]
2 [(EB), (FA), (CA), (DA)] [(B ), (A0)]
A

3 [(FA), (CA), (DA)] [(EB), (BA), (A0)]

4 [(JF), (GF), (CA), (DA)] [(FA), (EB), (BA), (A0)]
5 [(GF), (CA), (DA)] [(JF), (FA), (EB), (BA), (A0)]
6 G is the Goal [(GF), (JF), (FA), (EB), (BA), (A0)]

State space: all node of tree

Search space: A, B, E, F, J, G
Solution path: A  F  G

28
 2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

Ex: Find the Goal (I) using Hybrid First Search (HFS) Algorithm to the
following Tree: (bound = 2 for stopping)

Level 0 A

Level 1 B F C D

Level 2 E J G

H I
Level 3

Iteration Open Close

0
0 [(A )] []
A A A A 0
1 [(B ), (F ), (C ), (D )] [(A )]
B B A A A
2 [(E ), (F ), (F ), (C ), (D )] [(B ),(A0)]
A

3 [(FB), (CA), (DA)] [(EB),(BA),(A0)]

4 [(JF), (GF), (CA), (DA)] [(FB),(EB),(BA),(A0)]
5 [(GF), (CA), (DA)] [(JF),(FB),(EB),(BA),(A0)]
6 [(CA), (DA)] [(GF),(JF),(FB),(EB),(BA),(A0)]
7 [(FC), (GC), (DA)] [(CA),(GF),(JF),(FB),(EB),(BA),(A0)]
8 [(GC), (DA)] [(FC),(CA),(GF),(JF),(FB),(EB),(BA),(A0)]
9 [(DA)] [(GC),(FC),(CA),(GF),(JF),(FB),(EB),(BA),(A0)]
10 [] [(DA),(GC),(FC),(CA),(GF),(JF),(FB),(EB),(BA),(A0)]
11 [(A0)] []
A A A A 0
12 [(B ), (F ), (C ), (D )] [(A )]
B B A A A
13 [(E ), (F ), (F ), (C ), (D )] [(B ),(A0)]
A

14 [(HE), (IE), (FB), (CA), (DA)] [(EB),(BA),(A0)]

15 [(IE), (FB), (CA), (DA)] [(HE),(EB),(BA),(A0)]
16 I is the GOAL [(IE),(HE),(EB),(BA),(A0)]

)bound = 2( ‫ بسبب تحديد‬,)Goal( ‫في هذه الحالة ال نحصل على‬

29
2024/ ‫ المرحلة الثالثة‬/ ‫قسم الشبكات‬ )AI( ‫الذكاء االصطناعي‬ ‫ أنسام نزار‬.‫م‬

)depth bound(‫ فسوف نزيد الـ‬,‫) بأي طريقة‬Goal( ‫أما عندما يكون المطلوب هو الوصول الى الهدف‬
‫) إلى أن نصل إلى‬root( ‫) ونبدأ بالحل من الجذر‬Iteration(‫) ونزيد الـ‬bound = 3( ‫بمقدار واحد ليصبح‬
.)Goal( ‫الهدف‬
__________________________________________________________________

Comparison between DFS and BFS and HES

Depth First Search Breadth First Search Hybrid First Search
(DFS) (BFS) (HFS)
Local converge Global converge Global converge
Less complexity High complexity Less complexity
With backtracking Without backtracking With backtracking
Non-admissible Admissible Admissible
Not optimal solution. Optimal solution Optimal solution

30