Algoritma pada games "Leap Frog"

Algoritma pada games "Leap Frog"

Algoritma DFS diimplementasikan pada game leap frog ini untuk menentukan langkah terbaik sehingga didapatkan suatu solusi, yaitu kedua kelompok katak bertukar posisi. Saat katak melakukan lompatan ke sebuah batu yang kosong, algoritma DFS mencari kemungkinan-kemungkinan posisi para katak selanjutnya dan melakukan pencarian kembali. Pemodelan masalahnya adalah :

·         Katak berwarna hijau              : h1 h2

·         Katak berwarna coklat            : k2 k1

·         Angka 0 ( nol ) merupakan ruang kosong yang terdapat pada permainan ini, yaitu batu yang tidak ditempati katak

·         Ruang keadaan awal               : [ h1 h2 0  k2 k1]

·         Ruang keadaan akhir              : [ kn kn 0  hn hn ]

Pohonpencarianpadapermainantukarposisikatak

Pada gambar pohon pencarian di atas, kotak pertama merupakan ruang keadaan yang menggambarkan kemungkinan posisi-posisi katak, dan kotak kedua yang berisi huruf abjad adalah kode simpul untuk mengidentifikasikan node pada pohon tersebut.  Solusi permainan terdapat pada simpul V.

Untuk memudahkan pencarian dengan algoritma DFS, digunakan struktur data stack berjumlah 2, yang bernama open, untuk menyimpan simpul yang sedang dikunjungi, dan closed untuk menyimpan simpul yang telah dikunjungi. Langkah - langkah penelusuran tersebut adalah :