PENERAPAN METODE BFS DAN DFS DALAM PENCARIAN SOLUSI GAME WOLF, SHEEP, AND CABBAGE

PENERAPAN METODE BFS DAN DFS DALAM PENCARIAN SOLUSI GAME WOLF, SHEEP, AND CABBAGE

I.     ­PENDAHULUAN

1.1 LATAR BELAKANG

Dalam permainan logika Wolf, Sheep, and Cabbage. Diceritakan ada seorang petani yang hendak menyeberangi sungai membawa hasil belanjanya dari pasar, yaitu sekeranjang penuh kubis, juga seekor serigala dan seekor domba. Pemain diminta untuk menyeberangkan petani, serigala, domba, dan keranjang kubis menggunakan sebuah perahu yang hanya muat ditempati oleh dua penumpang. Yang dapat menggunakan perahu hanya sang petani. Permasalahnya adalah pada saat petani tidak ada, serigala akan memakan domba, dan domba akan memakan kubis.

Berikut adalah tampilan secara umum permainan ini.

Gambar 1. Tampilan awal permainan

Berikut  penjelasan  singkat  mengenai  teknis  permainan. Untuk  menaikkan  serigala, domba, dan kubis,  cukup mengklik pada menu gambar yang ada di bagian atas,  maka  serigala, domba, atau kubis,  akan otomatis  masuk  ke  perahu.  Begitu  pula  untuk mengeluarkannya  dari  perahu  tinggal  mengklik menu gambar serigala, domba, atau kubis yang ada di bagian atas. Untuk menjalankan perahu, cukup mengklik tombol  GO!  yang terletak di menu atas.  Dengan  aturan-aturan  di  atas,  permainan  ini  dapat diselesaikan  dengan  algoritma  Brute Force  yaitu  dengan metode  exhaustive  search.  Exhaustive  search  mencoba semua  kemungkinan  pilihan  pada  setiap  langkah  dalam permainan  ini  kemudian  mencoba  lagi  setiap kemungkinan  pada  setiap  langkah  yang  dipilih.  Begitu seterusnya sampai semua kemungkinan selesai ditelusuri.  Metode  ini  tentu  saja  akan  menemukan  solusi  karena setiap  kemungkinan  ditelusuri.  Namun,  karena  setiap kemungkinan  ditelusuri,  maka  dibutuhkan  waktu  yang cukup  lama  untuk  memproses  sampai  menemukan solusinya. Sehingga metode ini tidak efektif dan  jarang dipakai.  Oleh  karena  itu,  untuk  menyelesaikan  permainan  ini, digunakan algoritma BFS (Breadth First Search) dan DFS (Deep First Search).

1.2 RUMUSAN MASALAH

Bagaimana pencarian solusi permainan Wolf, Sheep, and Cabbage  dengan menggunakan algoritma BFS dan DFS.

1.3 TUJUAN DAN MANFAAT

Tujuan dari makalah ini adalah mambandingkan antara algoritma  Breadth First Search dan Depth First Search. Sehingga dapat digunakan untuk mengoptimalkan waktu dalam menyelesaikan permainan.

Manfaat dari makalah ini adalah menambah ragam  permainan yang telah ada sehingga dapat digunakan sebagai salah satu media alternatif untuk mengisi waktu senggang. Selain itu, permainan ini juga termasuk salah satu jenis permainan edukasi sehingga dapat digunakan untuk melatih kemampuan nalar dan logika seseorang.

  

1.4  BATASAN MASALAH

Penulis membatasi masalah pada makalah  ini sebagai berikut : Algoritma yang digunakan dalam pencarian solusi Wolf, Sheep, and Cabbage adalah BFS dan DFS.

II. DASAR TEORI

2.1. Algoritma Breadth-First Search (BFS)

BFS adalah sebuah algoritma pencarian yang digunakan dalam sebuah struktur pohon. Pada algoritma ini pencarian dilakukan dimulai dari simpul akar, dan kemudian pencarian dilakukan secara menyebar sesuai dengan tingkat dari masing-masing simpul di dalam pohon.

       

Ilustrasi pencarian pada pohon dengan BFS

Kelebihan dari algoritma ini adalah jawaban yang dihasilkan selalu merupakan solusi optimal. Karena pencarian dilakukan dengan melihat ketinggian simpul. Sayangnya pencarian optimal ini harus dibayar dengan jumlah memori yang diperlukan untuk komputasi  yang akan  banyak mengikuti jumlah simpul yang disimpan di memori.

2.2  Algoritma DFS( Depth First Search)

DFS adalah sebuah algoritma pencarian yang digunakan dalam sebuah struktur pohon seperti BFS. Hanya saja pada algoritma ini setelah pencarian dilakukan di simpul akar,, pencarian kemudian dilakukan secara menurun sesuai urutan yang telah ditentukan (prioritas kiri ke kanan atau kanan ke kiri). Jika menemukan daun, pencarian dikembalikan ke simpul yang belum dikunjungi di atasnya mengikuti urutan tadi.

Ilustrasi pencarian pada pohon dengan DFS

Kelebihan DFS terletak pada jumlah memori yang diigunakan untuk melakukan komputasi sedikit, karena cukup satu simpul yang diingat untuk menjelajah isi pohon, yaitu simpul yang sedang digunakan.

Pencarian dengan Algoritma DFS juga memiliki kelemahan, yaitu solusi yang ditemukan tidak selalu optimal, karena yang didahulukan dalam pencarian adalah menuruni pohon.

III.  ANALISA DAN PEMBAHASAN

Untuk memfasilitasi pemecahan masalah Wolf, Sheep, dan Cabbage menggunakan algoritma pencarian BFS dan DFS kita akan mendefinisikan permasalahan ini sebagai sebuah  struktur pohon. Serta berikut adalah representasi permasalahan  Wolf, Sheep, and Cabbage  yang  telah disesuaikan dengan struktur pohon yang dibangun :

1.  Setiap  role  dalam permasalahan ini akan diwakilkan dengan sebuah karakter. Petani direpresentasikan dengan  huruf F, serigala dengan huruf W, domba dengan huruf S, dan kubis dengan huruf C,  kecuali perahu yang tidak perlu direpresentasikan karena sudah dapat diwakilkan oleh petani.

2.  Kondisi awal  permainan  adalah  state  dengan semua role berada di sebelah kanan sungai.

3.  Kondisi akhir  permainan  adalah  state  dengan semua  role  berada di sebelah kiri sungai  tanpa ada satu pun role yang hilang karena dimakan.

4.  Setiap state untuk role di sisi sungai disimpan ke dalam sebuah simpul dengan notasi berikut

    

   <{role di kiri}, {role di kanan}>* 

Contoh:

Kondisi awal permainan

<{}, { F,W,S,C }>

Konsisi akhir permainan

<{ F,W,S,C }, {}>

*notasi {} menunjukkan sebuah himpunan, maka {F,W} = {W,F}

5.  Petani yang membawa hewan dan barang akan dimasukkan ke dalam himpunan di mana sisi perahu menepi.

6.  State  yang terdapat salah satu dari {W,S} atau {S,C} akan dianggap tidak valid.

Berikut adalah batasan yang digunakan dalam pembangunan pohon :

1.  Simpul yang berulang  akan digambarkan tetapi tidak akan diteruskan

2.  Simpul yang tidak valid tidak akan digambarkan

Perlu diperhatikan bahwa pohon yang didapat pada bagian BFS dan DFS  adalah pohon dengan simpul yang dilewati oleh pencarian BFS atau DFS.

3.1  Pemecahan dengan BFS

Algoritma BFS yang digunakan :

1.   Masukkan state awal ke dalam antrian

2.  Cek apakah sudah memenuhi state akhir  jika ya kembalikan solusi, jika tidak masukkan state yang mungkin dari state sebelumnya ke dalam antrian.

3.  Cek antrian, jika kosong pencarian berakhir dengan dengan solusi kosong.

4.  Kembali lagi ke 2.

Berikut adalah pohon yang dihasilkan dari pencarian dengan algoritma BFS :

Jumlah penelusuran yang dilakukan oleh algoritma BFS adalah 14  (empat belas) kali. Jumlah state yang diperlukan untuk mencapai state akhir adalah delapan. Hasil yang didapatkan dari pencarian ini adalah optimal.

3.2  Pemecahan dengan DFS

Algoritma DFS yang digunakan :

1.      Masukkan state awal ke dalam tumpukan

2.      Cek apakah sudah memenuhi state akhir  jika ya kembalikan solusi, jika tidak masukkan state yang mungkin dari state sebelumnya ke dalam antrian.

3.      Cek tumpukan, jika kosong pencarian berakhir dengan dengan solusi kosong.

4.      Kembali lagi ke 2.

Berikut adalah pohon yang dihasilkan dari pencarian dengan algoritma DFS  dengan prioritas yang digunakan adalah kiri ke kanan :

Jumlah penelusuran yang dilakukan oleh algoritma DFS adalah tujuh kali.  Jumlah state yang diperlukan untuk mencapai state akhir adalah delapan. Hasil yang didapatkan dari pencarian ini  sama dengan hasil yang didapatkan pencarian BFS.

3.3  Analisis

Pada penggunaan algoritma pencarian DFS dan BFS di atas  ditemukan hasil yang sama dan optimal. Tentu saja hal ini tidak selalu terjadi  pada pencarian BFS dan DFS pada implementasinya. Mengapa  sampai terjadi  kemunculan hasil yang sama untuk algoritma  pencarian BFS dan DFS? Hal ini hanya akan terjadi pada saat  state  akhir  yang dituju terletak di pinggiran  dalam  dari pohon  yang dibentuk.  Sehingga pada saat pencarian DFS tidak akan mencari terlalu jauh ke bawah. 

Hal ini juga dipengaruhi oleh  batasan yang diberlakukan yaitu  pengulangan  state  tidak  perlu dilanjutkan.  Jika  misalnya  state    tujuh pada pohon pencarian  DFS dilanjutkann maka tentu  DFS akan melanjutkan pencarian ke bawah dan hasil yang didapatkan berada di kedalaman yang lebih besar.

3.4  Penerapan Solusi

VI. KESIMPULAN

Algoritma pencarian  Breadth First Search  dan Depth First Search  digunakan dalam penelusuran pohon, dan dengan memodelkan sebuah persoalan ke dalam sebuah pohon kita dapat mencari solusi yang mungkin dari persoalan tersebut menggunakan BFS dan DFS. Dan kita telah melihat bahwa permainan logika Wolf, Sheep, and Cabbage dapat diselesaikan dengan algoritma BFS dan DFS.

Berikut adalah tahapan yang dilakuan untuk mencapai state akhir. Baik BFS dan DFS memberikan solusi yang sama, yaitu:

 1.  Kondisi awal

2.  Bawa domba ke kiri sungai

3.  Kembali ke kanan

4.  Bawa serigala ke kiri

5.  Kembali ke kanan bersama domba

6.  Bawa kubis ke kiri

7.  Kembali ke kanan

8.  Bawa domba ke kiri (selesai)

Pencarian dengan DFS dan BFS bisa mengembalikan solusi yang sama dan  tentunya  optimal. Hal ini  dapat terjadi karena solusi terdapat pada sebelah pinggir pohon yang sesuai dengan prioritas yang digunakan. Pengeliminasian  state  yang  redundan  terbukti dapat mengurangi  jumlah pencarian dalam pohon pencarian dengan algoritma BFS dan DFS.