1.1.
Breadth-First
Search (BFS)
Breadth-first
search (BFS) melakukan proses searching pada semua
node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum
melanjutkan proses searching pada node di level berikutnya. Urutan proses
searching BFS ditunjukkan dalam Gambar 2.1 adalah: A,B,C,D,E,F, ...
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
simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk
pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum
simpul-simpul pada ras d+1.
Algoritma
ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.
Simpulsimpul 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 te lah dikunjungi sehingga tidak ada simpul yang
dikunjungi lebih dari satu kali.
1.1.1. 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:
1.
Masukkan simpul ujung
(akar) ke dalam antrian
2.
Ambil simpul dari awal
antrian, lalu cek apakah simpul merupakan solusi
3.
Jika simpul merupakan
solusi, pencarian selesai dan hasil dikembalikan.
4.
Jika simpul bukan
solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul
anak) ke dalam antrian
5.
Jika antrian kosong dan
setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi
tidak ditemukan
6.
Ulangi pencarian dari
langkah kedua
Contohnya
terlihat dibawah ini:
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
1.1.2. Contoh Pencarian
Lintasan Terpendek Dengan BFS
Adapun contoh
untuk mencari lintasan terpendek dengan menggukan algoritma BFS adalah sebagai
berkut:
Diketahui sebuah
kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar
kota dibentuk dengan sebuah graph terlihat dibawah:
Pertanyaan:
sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal
perjalanan adalah kota no. 1. Gunakan algoritma BFS!
Maka dengan
menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut:
1 – 2 – 3 – 4 –
5 – 6 – 7 – 8
Rute tersebut
didapat dari pencarian secara melebar. Hal; tersebut dapat dijabarkan sebagai
berikut:
·
Pertama-tama, pointer
menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2)
·
Setelah itu, proses
dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada
tetangga terdekat, yakni no.4 (1-2-3-4).
·
Pointer mencari
teteangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan
masuk ke daun berikutnya, yakni no.5.
·
Proses diulang hingga
pointer menunjuk angka 8
1.2.
Depth-First
search (DFS)
Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi
sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi
terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai
menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS
akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut
memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS
akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat
dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching
terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan
penyelesaian masalah. Urutan proses searching DFS ditunjukkan dalam Gambar 1.5
adalah: A, B, E,F, G, C, ... Figure
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).
1.2.1.
Kelebihan
dan Kelemahan DFS
Kelebihan
DFS adalah:
• Pemakain
memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node
yang pernah dibangkitkan.
• Jika
solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan
menemukannya secara cepat.
Kelemahan DFS adalah:
• Jika
pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak
ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika
terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal)..
1.2.2.
Cara
Kerja DFS
Pencarian
rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik
awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari
tujuan atau sebagai simpul yang dicari.
Dalam
algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan
(stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi
sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses
runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman
maksimal).
Untuk
memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya,
berikut langkah-langkah algoritma DFS:
1. Masukkan
simpul ujung (akar) ke dalam tumpukan
2. Ambil
simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
3. Jika
simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika
simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul
tersebut (simpul anak) ke dalam tumpukan
5. Jika
tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan
mengembalikan hasil solusi tidak ditemukan
6. Ulangi
pencarian dari langkah kedua
Tidak ada komentar:
Posting Komentar