tugas penerapan metode pencarian dfs dan bfs

Penerapan metode pencarian bfs (breadh first search) dan dfs (dept first search)

contoh masalah:

Petani, Sayur, Kambing dan Serigala

  Seorang petani akan menyeberangkan seekor kambing, seekor serigala, dan sayur-sayuran dengan sebuah perahu yang melalui sungai.

  Boat hanya bisa memuat petani dan satu penumpang yang lain (kambing, serigala atau sayur-sayuran).

  Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh serigala.   

 

Penyelesaian masalah secara umum 

  Mendefinisikan suatu ruang keadaan;

  Menetapkan satu atau lebih keadaan awal;

  Menetapkan satu atau lebih tujuan;

  Menetapkan kumpulan aturan.

 

Dengan aturan sebagai berikut :

1.petani dan kambing menyeberang

2.petani dan serigala menyeberang

3.petani dan sayur menyeberang

4.petani dan sayur kembali

5.petani dan srigala kembali

6.petani an kambing kembali

7.petani kembali

                Langkah pertama kita akan menganalisa masalah tersebut dengan metode pencarian bfs (breadth first seach ) dengan menguji semua kemungkinan yang ada

                                Keterangan :

1.petani = (p)

2.sayuran = (sy)

3.serigala = (sr(

4.kambing = (k)

Dengan keadaan awal (p,sr,sy,k = 1,1,1,1)

Dengan tujuan /goal   (p,sr,sy,k = 0,0,0,0)

1. Breadth First Search (BFS)

Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

untuk masalah petani tersebut bisa kita gunakan pola sebagai berikut :
 

Keuntungan

  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

  Kelemahannya

  Membutuhkan memori yang cukup banyak

  Membutuhkan waktu yang cukup lama

2. Dept First Search (DFS)

Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

untuk masalah petani tersebut bisa kita gunakan pola sebagai berikut :

Keuntungan

  Memori yang relatif kecil

  Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

Kekurangan

  Memungkinkan tidak ditemukannya tujuan yang diharapkan

  Hanya akan mendapatkan 1 solusi pada setiap pencarian