Contoh Breadth First Search dan Depth First Search

·  STUDI KASUS :
Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan srigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.

Permasalahannya adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala

·  DESKRIPSI:

P = Petani
Sy = Sayuran
K = Kambing
Sg = Serigala

·   RUANG KEADAAN
Untuk daerah asal dan daerah seberang
digambarkan.
(P, Sy, K, Sg)

·  KEADAAN AWAL
Daerah Asal = (P, Sy, K, Sg)
Daerah seberang = (0, 0, 0, 0)

·  TUJUAN
Daerah Asal = (0, 0, 0, 0)
Daerah seberang = (P, Sy, K, Sg)

·  METODE PENYELESAIAN :

Terdapat dua metode penyelesaian yang akan dibahas pada postingan kali ini. Metode pertama adalah metode breadth first search (BFS), dan metode kedua adalah metode Depth First Search (DFS). Berikut ini akan dijelaskan penyelesaian studi kasus diatas dengan kedua metode tersebut.

·   BFS (Breadth First Search)

adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada di dalam pohon. Berikut ini adalah algoritma BFS :

1.  Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.

2.   Jika Q kosong, tidak ada solusi. Stop.

3.   Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.

4.   Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.

·   GAMBAR BFS :

·     DFS (Depth First Search)

adalah sebuah algoritma pencarian yang digambarkan dengan struktur pohon seperti pada BFS. Penyelesaiannya dilakukan dengan mendalam. Pencarian solusi dilakukan secara menurun sesuai urutan yang ditentukan.

1.     Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.

2.    Jika Q kosong, tidak ada solusi. Stop.

3. Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2

4 .Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.

·                     GAMBAR DFS :

Daftar Pustaka :

https://creactiveit.wordpress.com/2015/05/08/halo-dunia/