Tanggal :September 27, 2020

Merancang Algoritma Berbasis Aturan (Rules) DFS dan BFS

Spread the love

Depth-First-Search (DFS)

DFS merupakan metode pencarian solusi dimana Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.
Keuntungan menggunakan metode DFS ini yaitu:
– Membutuhkan memori yang relative kecil, karena hanya node-node ada lintasan yang aktif saja yang disimpan.
– Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi.
Kekurangan dari metode DFS ini yaitu:
– Memungkinkan tidak ditemukannya tujuan yang diharapakan.
– Hanya akan menemukan 1 solusi pada setiap pencarian.
Contoh kasus pada multistep graph berikut :
Rules : R1 = cari solusi menggunakan jalur kanan
R2 = cari solusi menggunakan jalur tengah
R3 = cari solusi menggunakan jalur kiri
Bagan graf :

      Breadth-First-Search (BFS)

BFS merupakan metode pencarian solusi dimana semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan.
Keuntungan menggunakan metode BFS ini yaitu:
·       Tidak akan menemui jalan buntu.
·       Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.
·       Jika ada satu solusi maka bread-first search akan menemukannya.
Dan kekurangan dari metode BFS ini yaitu:
·       Membutuhkan memori yang cukup banyak.
·       Membutuhkan waktu yang cukup lama.
Pada kasus yang sama pada DFS, maka pencarian solusi dengan BFS dapat dilihat dari bagan di bawah ini.
 
 
 
 
Share

Leave a Reply

Your email address will not be published. Required fields are marked *