Scribd Logo
Importer

Bienvenue sur Scribd !

  • 21 vues

    Tugas Kecerdasan Buatan BFS

    Transféré par

    Aries Stark
    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é.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Tugas Kecerdasan Buatan BFS

    Transféré par

    Aries Stark
    21 vues6 pages
    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é.

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    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é.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    21 vues6 pages

    Tugas Kecerdasan Buatan BFS

    Transféré par

    Aries Stark
    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é.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 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