Kamis, 06 Januari 2011

Penjelasan tentang BFS dan DFS

BFS dan DFS merupakan jenis dari metode pencarian solusi. 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 yang didapat apabila 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.
Sedangkan 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 yang didapat apabila menggunakan metode DFS ini yaitu:
- Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
- Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi.

Dan kekurangan dari metode DFS ini yaitu:
- Memungkinkan tidak ditemukannya tujuan yang diharapakan.
- Hanya akan menemukan 1 solusi pada setiap pencarian.

5 komentar:

  1. Bermanfaat informasi nya bang ,, suksma MWZ

    BalasHapus
  2. makasih gan sangat membantu, tapi sedikit masukan : mungkin jelaskan perbedaannya apalagi kn msh banyak tuh metodeny, sama contoh game yang memakai metode tersebut?? mksh, salam sukses (y)

    BalasHapus