LAPORAN TUGAS ARTIFICIAL INTELEGENT
MENGENAI METODE BFS
Oleh ;
Reza Nursyamsa Siroja ( 2003010022 )
Rizki Nugraha ( 2003010029 )
Inra Maulana ( 2003010012 )
PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS PERJUANGAN
TASIKMALAYA
2022
DAFTAR ISI
KATA PENGANTAR…………………………………………………….……….
DAFTAR ISI……………………………………………………………….….......
BAB I PENDAHULUAN………………………………...……………………….
A. Latar Belakang…….………………………………………………………….
B. Rumusan Masalah…...………………………………...……………………......
C. Tujuan...……………………………………………………………………....…
BAB II LANDASAN TEORI…………………………………….…………...……
A. Pembahasan Metode.…….……………………………………………………..
B. Pembahasan Problem…………………………………………………………....
BAB III ANALISIS DAN IMPLEMENTASI…………………………….…………
BAB IV PENUTUP ………………………………………………………………...…
A. Kesimpulan…..……………………...…………………………………….…
DAFTAR PUSTAKA
BAB 1 PENDAHULUAN
A. Latar Belakang
Artificial Intelligence atau yang biasa disingkat AI merupakan teknologi yang
sebenarnya sudah dikembangkan sejak lama dan seiring perkembangannya sudah
mempengaruhi manusia di segala aspek kehidupan. Menurut Russel dan Norvig
“Kecerdasan Buatan adalah Suatu program komputasi yang dapat membuat mesin
bekerja layaknya kecerdasan manusia; seperti mengambil keputusan, memecahkan
masalah, dan melakukan prediksi. Karena AI memiliki kemampuan yang hampir sama
dengan manusia, maka AI disebut juga Kecerdasan Eksternal atau External
Intelligence.
Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah
sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan
sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa
kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer
adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah
disebut ruang pencarian. algortima pencarian ( search ) brute-force atau pencarian
naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang
pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk
menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha
mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun dalam metode
pencarian blind atau buta digunakan karena memang tidak ada informasi awal yang
digunakan dalam proses pencarian. Algoritma Pencarian ini menggunakan Metode BFS,
DFS, dll.
Algoritma Depth-First Search (DFS) atau algoritma pencarian mendalam juga
merupakan pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri.
Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian
dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika
pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan
pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi
ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk
mendapatkan jalur yang dinginkan.
Algoritma Breadth-First Search (BFS) atau algoritma pencarian melebar
merupakan pencarian dilakukan pada semua node dalam setiap level secara berurutan
dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian
dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi.
Dengan strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah
yang paling baik (Optimal). Algoritma BFS memerlukan sebuah antrian (queue)
untuk menyimpan simpul yang telah dikunjungi.
BAB 2 LANDASAN TEORI
A. Pembahasan Teori
1. BFS ( BREADTH FIRST SEARCH )
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar
yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian
mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu.
Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul
yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka
semua simpul pada arah d dikunjungi lebih dahulu sebelum simpul-simpul pada arah
d+1.
Algoritma ini memerlukan sebuah antrian untuk menyimpan simpul yang telah
dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-
simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke
dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk
menyimpan simpul yang telah dikunjungi sehingga tidak ada simpul yang dikunjungi
lebih dari satu kali.
a. CARA KERJA ALGORITMA BFS
Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu
antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga
dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk
memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut
langkah-langkah algoritma BFS:
• Masukkan simpul ujung (akar) ke dalam antrian.
• Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.
• Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan..
• Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul
tersebut (simpul anak) ke dalam antrian.
• Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan
mengembalikan hasil solusi tidak ditemukan.
• Ulangi pencarian dari langkah kedua.
b. Contoh Metode Pencarian BFS (Breadth First Search)
Maka penyelesaiannya adalah:
Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.
Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1
Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9
c. Implementasi ( BFS ) Breadth First Search
Penjelasan :
Pencarian rute dengan BFS, yaitu dengan mengecek setiap level mulai dari level n
atau level 1, baru dilanjutkan ke level n+1 hingga target atau goalnya ditemukan.
Meski demikian, yang dihitung pada akhirnya bukanlah jarak yang ditempuh selama
mencari target, namun rute yang dipilih adalah rute yang terhubung ke target (yaitu A
S F B). Oleh karena itu, BFS membutuhkan banyak memori untuk menyimpan semua
simpul dalam satu pohon dan ini menjadi salah satu kekurangan BFS.
DAFTAR PUSTAKA
[1] Hakim Agung Ramadhan, Big Data, Kecerdasan Buatan, Blockchain, dan Teknologi
Finansial di Indonesia, CIPG (Centrefor Innovation Policy and Governance), Working
Paper, Juli 2018, hal. 1- 49.
[2] Bawafi, S. H. (2012, Maret 24). ANALISA TEKNIK SEARCHING DALAM
ARTIFICIAL INTELLIGENCE. Retrieved Oktober 21, 2017, from blind.
[3] Pasaribu, E. S. (2013). Penerapan Algoritma BFS, DFS, dan IDS pada Penyelesaian
Permainan Bubble Blast 2, 2.
[4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001)
[1990]. "22.2 Breadth-first search". Introduction to Algorithms (2nd ed.). MIT Press and
McGraw-Hill. pp. 531–539. ISBN 0-262-03293-7.