Hai, setelah sekian lama vakum akhirnya website ini update. Kali ini kami akan membagian sebuah tutorial untuk membuat algoritme penyelesaian water jug problem atau yang lebih dikenal sebagai Die Hard Problem.

Water Jug problem atau Die Hard problem adalah suatu permasalahan mengenai berapa langkah yang perlu dilakukan untuk memindahkan sebuah air menjadi tepat n liter, awalnya terdapat 2 buah ember dengan isi kosong dan sebuah kolam berisi air yang tak terbatas, masing-masing ember mempunyai dan liter air, dan diinginkan minimal salah satu ember berisi liter air yang diinginkan.

Peraturan dalam teka-teki ini sangatlah simpel, ember boleh diisi air hingga penuh dari kolam, atau memindahkan semua air ke ember yang lain ataupun memindah beberapa air ke ember yang lain selama ember tersebut belum penuh dan juga boleh untuk membuang salah satu isi ember.

Teka-Teki ini dipopulerkan oleh sebuah film Hollywood pada tahun 1995 yang berjudul Die Hard With A Vengeance, pada film tersebut diceritakan bahwa tokoh utama menemukan sebuah bom dan untuk mematikan bom tersebut diharuskan memberikan tepat 4 liter air pada sebuah timbangan. seperti pada cuplikan dibawah ini:

Untuk menyelesaikan permasalahan tersebut ternyata dapat kita aplikasikan pada sebuah bahasa pemrograman dengan sedikit bumbu Artificial Inteligence, pada kali ini saya mengimplementasikan dengan bahasa pemrograman java dan menggunakan pendekatan algoritme Iterative Deepening Search, untuk lebih jelasnya silakan lihat kode dibawah ini.

Pertama kali kita membuat sebuah class yang mengabstraksi objek dari Ember dengan nama ember_obj, Class ini memiliki beberapa variabel yaitu history dengan tipe HashMap , balik dengan tipe stack dan path dengan tipe stack, count, find , max1, max2, sc, dan maxlv dengan tipe integer semua variabel diatas memiliki identifier static. Selain itu Class ini juga memiliki beberapa variabel non static seperti st1, st2 dan lv dengan tipe data integer , lalu variabel token dan parent dengan tipe data String dan 4 objek dengan tipe data ember_obj dengan nama child1,child2,child3 dan child4. Variabel history berguna untuk menyimpan data node/child yang sudah pernah diexpand, lalu variabel balik berguna untuk menyimpan data child dari setiap node untuk di tampilkan, lalu path yang berguna untuk menyimpan jalur/path dari root ke tujuan.

Kemudian ada variabel count yang berguna untuk mengetahui jumlah node yang sudah diexpand, lalu find untuk mengetahui apakah tujuan sudah ditemukan, max1 dan max2 berguna untuk menyimpan ukuran dari masing-masing ember 1&2, sc untuk menyimpan nilai yang akan dicari(tujuan) , maxlv berguna untuk mengetahui jumlah max level yang boleh diexpand, lalu st1 dan st2 yang menyimpan nilai isi dari ember 1&2, lv untuk menyimpan nilai dari level suatu node, lalu token untuk menyimpan nilai unik dari node sehingga tidak terjadi expand 2 x untuk node yang sama untuk ,parent yang menyimpan nilai dari parent dari node tersebut, lalu ada 4 child untuk menyimpan semua kemungkinan node yang ada untuk diexpand.

Didalam class tersebut memiliki beberapa method seperti method yang dijelaskan dibawah ini,

Method check_me berguna untuk mengecek apakah tujuan sudah tercapai, dengan membandingkan nilai dari st1 dan st2 dengan nilai sc, jika ditemukan maka akan memanggil method get_ancestor untuk memulai proses penelusuran sumber dari node yang ditemukan.

Method init berguna untuk mencari/mengekspand semua child jika tujuan belum diketahui, pertama kali akan mengecek apakah history mengandung nilai token jika mengandung berarti node tersebut pernah diexpand sehingga expansi tidak akan dilakukan, hal ini berguna untuk mempercepat pencarian, jika tidak ditemukan maka nilai dari token akan disimpan di history dan dimulai expand dimulai dari child1 dengan method expand_1 hingga child4 menggunakan method expand_4, pada method ini juga diperlakukan penyimpanan data urutan ke variabel balik.

Pada method ini diperlakukan ekspansi pada child ke 1, jika level masih 1 maka nilai dari child1 pada st1 adalah max1 dan nilai st2 adalah 0, jika tidak maka diperlakukan nilai lain seperti st1 adalah max1 dan st2 adalah max2 jika kedua nilai ember tersebut bukan max, dan lain lain.

Pada method ini diperlakukan ekspansi pada child ke 2, jika level masih 1 maka nilai dari child3 pada st1 adalah 0 dan nilai st2 adalah max2, diperlakukan nilai lain seperti st1 adalah st1(tetap) dan st2 adalah 0 (Air dibuang).

Pada method ini diperlakukan ekspansi pada child ke 3, jika level masih 1 maka nilai dari child3 tidak diexpand, jika tidak maka nilai dari st1 adalah 0(Air dibuang) dan st2 adalah st2(tetap)

Pada method ini diperlakukan ekspansi pada child ke 4, jika level masih 1 maka nilai dari child4 tidak diexpand, jika tidak maka nilai akan diseleksi lagi jika st2 belum max dan st1>st2 maka dilakukan perpindahan air dari ember 1 ke 2 dengan method atob, jika tidak maka dilakukan kebalikanya yaitu memindah air ember 2 ke 1 dengan method btoa.

Method atob berguna memindah air dari ember 1 ke 2 melalui beberapa seleksi jika isi ember 1 lebih dari kekurangan ember 2 untuk maksimal maka jumlah air yang dipindah hanya sebagian, jika tidak maka semua air akan dipindah.

Method btoa berguna memindah air dari ember 2 ke 1 melalui beberapa seleksi jika isi ember 2 lebih dari kekurangan ember 1 untuk maksimal maka jumlah air yang dipindah hanya sebagian, jika tidak maka semua air akan dipindah.

Method cetak berguna untuk mengembalikan string nilai dari 4 child sebuah node

Method get_ancestor berguna untuk mengetahui asal usul dari parent dari sebuah node hingga root.

Kemudian kita membuat class IDSv3 yang digunakan untuk menjalankan program dan juga sebagai boundary class yang langsung berhubungan dengan pengguna.

Didalam class IDSv3 hanya terdapat satu method yaitu main yang  berguna untuk membuat CLI dari class ember_obj , fungsi dari method ini juga untuk memberikan kemudahan bagi user untuk menentukan ukuran dari ember1,dan 2 dan juga nilai yang dicari, selain itu pada program ini dibelakukan Iterative dari Search pada class ember_obj hingga ditemukan, sehingga pada program ini cara pencarian menggunakan Iterative Deepening Search, selain itu pada method ini juga diberikan informasi statistik yaitu dilevel berapa nilai ditemukan, lalu path dari pencarian ini kemudian jumla operasi penjelajahan yang dilakukan selain itu juga ada informasi tambahan berupa running time dari program dan memmory yang digunakan pada pencarian.

Screenshot dari Program tersebut :

Water Jug 1
Water Jug 2

Sekian Penjelasan dari saya, jika ada pertanyaan atau request kode bisa disampaikan dalam kolom komentar dibawah ini, sekian dan jangan lupa bagikan artikel ini ke teman anda karena dengan membagikan ini anda sudah membantu kami dalam mengembangkan website ini. Terimakasih.

Artikel Ini juga diposting pada laman labs.faathin.com.

Tinggalkan Balasan