Contoh Perbandingan Metode Pencarian
dengan cara BREADTH FIRST SEARCH (BFS)
atau pencarian melebar dan DEPTH FIRST SEARCH (DFS) atau pencarian kebawah
·
Penjelasan
tentang BPS dan DSP
BREADTH FIRST SEARCH (BFS) Algoritma
Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian
melebar 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 pad aras d+1.
Algoritma
ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.
Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang
bertetanggaan dengannya. Tiap simpul yang telah dikunjungi 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.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.
DEPTH FIRST SEARCH (DFS)
atau sering disebut juga pencarian mendalam. dilakukan pada suatu simpul dalam
setiap level dari yang paling kiri. Jika pada level yang paling dalam tidak
ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan
simpul 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.
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).
·
Contoh
penggunaan metode pencarian BFS dan DFS
Contoh :
PENYELESAIAN
MENGGUNAKAN PENCARIAN MELEBAR(BFS) :
Pada
BFS teknik pencarian pesoalannya adalah dengan membuka node (titik) per
levelnya.. sehingga pada persoalan diatas penyelesaian pada BFS adalah.
Jadi
urutan node yang di lalui pada pencarian BFS adalah. a,b,c,d,e,f,g,h.
PENYELESAIAN
MENGGUNAKAN PENCARIAN KEBAWAH(DFS) :
Jadi
solusi node yang di lalui pada DFS adalah a,b,e,h.
Sumber
:
