Scribd
Importer
36 vues6 pages

Tugas Kecerdasan Buatan BFS

Le document décrit l'algorithme de recherche en largeur d'abord (BFS) pour parcourir un arbre de recherche. Il montre les étapes de l'algorithme BFS pour trouver le chemin le plus court entre la racine et la cible dans l'arbre donné.

Transféré par

Aries Stark
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
36 vues6 pages

Tugas Kecerdasan Buatan BFS

Le document décrit l'algorithme de recherche en largeur d'abord (BFS) pour parcourir un arbre de recherche. Il montre les étapes de l'algorithme BFS pour trouver le chemin le plus court entre la racine et la cible dans l'arbre donné.

Transféré par

Aries Stark
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
Vous êtes sur la page 1/ 6

TUGAS KECEDERDASAN BUATAN

BREADTH-FIRST SEARCH (BFS)

OLEH:

Muhamad Reza Kurniawan


09021281823051
IF REG C

JURUSAN TEKNIK INFORMATIKA


FAKULTAS ILMU KOMPUTER
UNIVERSITAS SRIWIJAYA
GANJIL 2020/2021
TUGAS-2

Search Tree

B1 C1 D1 E1 F1 G1 H1

B2
H2

B3 C3 D3 F3 G3 H3

D4 F4

B5 C5 D5 F5 G5 H5

B6 H6

B7 F7 G7 H7

B8 C8 D8 E8 F8
Root Suksesor 1. Langah-1
H1 G1,H2 • Q1 = (H1)
G1 F1 • Q2 = (NULL)
H2 H3 2. Langah-2
F1 E1 • Q1 = (G1,H2)
H3 G3 • Q2 = (H1)
E1 D1 3. Langah-3
G3 F3 • Q1 = (H2, F1)
D1 C1 • Q2 = (H1, G1)
F3 F4 4. Langah-4
C1 B1 • Q1 = (F1,H3)
F4 F5 • Q2 = (H1,G1,H2)
B1 B2 5. Langah-5
F5 G5 • Q1 = (H3,E1)
B2 B3 • Q2 = (H1,G1,H2,F1)
G5 H5 6. Langah-6
B3 C3 • Q1 = (E1,G3)
H5 H6 • Q2 = (H1,G1,H2,F1,H3)
C3 D3 7. Langah-7
H6 H7 • Q1 = (G3,D1)
D3 D4 • Q2 = (H1,G1,H2,F1,H3,E1)
H7 G7 8. Langah-8
D4 D6 • Q1 = (D1,F3)
G7 F7 • Q2 = (H1,G1,H2,F1,H3,E1,G3)
D5 C5 9. Langah-9
F7 F8 • Q1 = (F3,C1)
C5 B5 • Q2 = (H1,G1,H2,F1,H3,E1,G3,D1)
F8 E8 10. Langah-10
B5 B6 • Q1 = (C1,F4)
E8 D8 • Q2 =
B6 B7 (H1,G1,H2,F1,H3,E1,G3,D1,F3)
D8 C8 11. Langah-11
B7 B8 (TARGET) • Q1 = (F4,B1)
C8 B8 (TARGET) • Q2 =
(H1,G1,H2,F1,H3,E1,G3,D1,F3,C1)

12. Langah-12
• Q1 = (B1,F5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4)
13. Langah-13
• Q1 = (F5,B2)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1)
14. Langah-14
• Q1 = (B2,G5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5)
15. Langah-15
• Q1 = (G5,B3)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2)
16. Langah-15
• Q1 = (B3,H5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2,G5)
17. Langah-17
• Q1 = (H5,C3)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3)
18. Langah-18
• Q1 = (C3,H6)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5)
19. Langah-19
• Q1 = (H6,D3)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3)
20. Langah-20
• Q1 = (D3,H7)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6)
21. Langah-21
• Q1 = (H7,D4)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3)
22. Langah-22
• Q1 = (D4,G7)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7)
23. Langah-23
• Q1 = (G7,D5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7, D4)
24. Langah-24
• Q1 = (D5, F7)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7)
25. Langah-25
• Q1 = (F7,C5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5)
26. Langah-26
• Q1 = (C5,F8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7)
27. Langah-27
• Q1 = (F8,B5)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5)
28. Langah-28
• Q1 = (B5, E8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8)
29. Langah-29
• Q1 = (E8,B6)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5)
30. Langah-30
• Q1 = (B6, D8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8)
31. Langah-31
• Q1 = (D8,B7)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8,B6)
32. Langah-32
• Q1 = (B7,C8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8,B6, D8)
33. Langah-33
• Q1 = (C8,B8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8,B6, D8, B7)
34. Langah-33
• Q1 = (B8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8,B6, D8, B7, C8)
35. Langah-33
• Q1 = (B8)
• Q2 = (H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2, G5, B3, H5,C3, H6, D3, H7,
D4,G7, D5, F7, C5, F8, B5, E8,B6, D8, B7, C8, B8)
Backtracking Queue-2 (Q2) Suksesor Root
B8 B7,C8
• Q2 =
B7 B6
(H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2,
B6 B5
G5, B3, H5,C3, H6, D3, H7, D4,G7, D5, F7, C5,
B5 C5
F8, B5, E8,B6, D8, B7, C8, B8)
C5 D5
• Q2 =
D5 D4
(H1,G1,H2,F1,H3,E1,G3,D1,F3,C1,F4,B1,F5,B2,
D4 D3
G5, B3, H5,C3, H6, D3, H7, D4,G7, D5, F7, C5,
D3 C3
F8, B5, E8,B6, D8, B7, C8, B8)
C3 B3
Jadi, jarak terpendek adalah : B3 B2
B2 B1
• H1→G1→F1→E1→D1→C1→B1→B2→B3→C B1 C1
3→D3→D4→D5→C5→B5→B6→B7→B8 C1 D1
D1 E1
E1 F1
F1 G1
G1 H1

Vous aimerez peut-être aussi