Selasa, 08 Mei 2012

Algoritma Breath First Search (BFS) dalam Game Tebak Kata


Game Tebak Kata
Permainan kata merupakan salah satu jenis permainan yang menarik karena dapat menantang pemainnya untuk mengeluarkan kreativitasnya dalam mengolah kata. Rangkai kata merupakan salah satu contohnya. Rangkai kata merupakan kata acak yang dibentudari kata lain yang telah   diubah susunan atau jumlah karakter di dalamnya. Pada pengolahan kata  ini,  pemain  akan  memasukan  kata  awal  yang ingin  dibangkitkan  Rangkai  kata  nya. Kemudian pemain akan menebak kata yang merupakan Rangkai kata dari kata awal. Algoritma Breadth First Search yang mengeksplorasi setiap cabang   dari setiap node sangat tepat untuk diterapkan pada permasalahan ini. Algoritma ini akan membangkitkan pohon solusi secara dinamis bersamaan dengan  dilakukannya proses pencarian solusi.

Peraturan permainan
Pertama pemain akan diminta untuk memasukkan kata yang ingin dibangkitkan Kata Acaknya. Setelah itu pemain akan memasukkan tebakan kata yang diasumsikan sebagai kata yang dibangkitkan dari kata awal. Pemain akan mendapat nilai apabila kata tebakannya merupakan salah satu kata yang dibangkitkan oleh algoritma BFS. Nilai yang didapat bergantung dari jumlah karakter kata tebakan. Semakin  banyak karakter tebakan, semakin sulit dan apabila jawaban benar, pemain akan memperoleh nilai yang tinggi pula. Dalam implementasinya, diperlukan struktur data Queue dan pohon.

Graf Ruang Solusi
Agar lebih jelas, akan digunakan contoh untuk menentukan Graf Ruang Solusinya
Misal :
Kata awal yang ingin dibangkitkan  : katakana
Tebakan pemain  : anak
Setiap karakter dalam kata awal diwakili oleh satu symbol status. Dalam hal ini setiap karakter diberi penomoran sebagai berikut :
Tabel 1 Tabel pemetaan status karakter
K
A
T
A
K
A
N
A
1
2
3
4
5
6
7
8




 Dari penomoran status di atas dapat dibentuk graf ruang solusi sebagai berikut :
Setelah melihat graf tersebut, terdapat banyak sekali kemungkinan solusi, maka saya menggunakan algoritma Breadth First Search untuk mencari solusinya.

 











Penjelasannya adalah sebagai berikut
Fungsi Utama :
Prosedur WordUnscrambler(Tebakan : String, node: int)
Prekondisi :
Dalam prosedur ini kami mengambil asumsi bahwa setiap node telah merepresentasikan karakter yang diwakilinya, Perubahan dari status ke status (dari node ke anaknya) diasumsikan sebagai operasi string untuk membentuk kata. Kemudian kata tebakan harus lebih kecil dari kata awal.
  1. Masukkan node awal ke Queue
  2. Set Kedalaman dengan 0
  3. Ambil kepala Queue
  4. Bangkitkan semua anak
  5. Jika anak memenuhi syarat push ke Queue
  6. Jika memenuhi solusi stop, jika tidak ulangi langkah 3 sampai kedalaman maks
  7. Cetak solusi dan perhitungan skor berdasarkan kedalaman 


Fungsi Bantuan :
1.    Bangkitkan anak
Prosedur ini membangkitkan anak dari Node dengan elemen status yang tersisa
2.   Fungsi isBagian(input : String,String) Fungsi ini memeriksa apakah Node tersebut memenuhi syarat atau merupakan bagian kata dari tebakan
Sebagai contoh, Saya akan  menggunak contoh persoalan yang telah ada di atas. Secara umum pohoyang dibentuk adalah sebagai berikut


Pada kedalaman 1, anak yang memenuhi kriteria akan  dimasukan  ke dalam  queue.  Laldari  anayang masuk queue tadi dibangkitkan anaknya. Dalam gambar di atas status 2 akan dimasukkan ke queue karena memenuhi criteria. Namun sebenarnya yang dibangkitkan anaknya bukan  cuma  status 2, namun  jugstatus 4,6,8Namun karena status­status itu merepresentasikan hal yang sama, maka tidak saya gambarkan, karena saya anggap hasilnya akasama  dengan  anak­anak  yang  dibangkitkan  oleh status ke 2.Setiap kedalaman akan dilakukan operasi yang sama, sampai kedalaman maksimal atau saat CurrentNode adalah solusi.

Dengan melihat gambar di atas terlihat jelas keuntungan BFS dalam pencarian solusi ini, karena BFS mengunjungi anak secara melebar. Sehingga untuk kasus dimantebakan  yang  lebih  sedikit  dimasukkan  pohon statsu akan berhenti pada node tersebut tanpa harus melangkah lebih dalam.

sumber :  informatika.stei.itb.ac.id/~rinaldi.../MakalahSTMIK2007-084.pdf



Tidak ada komentar:

Posting Komentar