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 i dan j liter air, dan diinginkan minimal salah satu ember berisi n 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 |
package com.faathin.artificialintillegence; import java.util.HashMap; import java.util.Stack; /** * * @author Riyadh */ public class ember_obj { public static HashMap<String, ember_obj> history = new HashMap(); public static Stack balik = new Stack(); public static Stack path=new Stack(); public static int count; public static boolean find; public static int max1; public static int max2; public static int maxlv; public static int sc; int st1; int st2; int lv; String token; String parent; ember_obj child1; ember_obj child2; ember_obj child3; ember_obj child4; public ember_obj(int max1, int max2, int sc, int maxlv) { ember_obj.max1 = max1; ember_obj.max2 = max2; ember_obj.sc = sc; ember_obj.maxlv = maxlv; run_me(); } public ember_obj(int st1, int st2, int lv, String parent) { this.st1 = st1; this.st2 = st2; this.lv = lv; this.token = "(" + st1 + "," + st2 + ")"; this.parent = parent; if (lv < maxlv) { if (check_me()) { find = true; } else { this.lv++; init(); } } } private void run_me() { ember_obj ember_obj = new ember_obj(0, 0, 0, "ROOT"); } private boolean check_me() { if (this.st1 == sc || this.st2 == sc) { history.put(token, this); get_ancestor(token); } return this.st1 == sc || this.st2 == sc; } final void init() { count++; if (!history.containsKey(token)) { history.put(token, this); if (!find) { expand_1(); } if (!find) { expand_2(); } if (!find) { expand_3(); } if (!find) { expand_4(); } balik.add(cetak(" | Anak Dari " + parent)); check_me(); } else { balik.add(token + " NO EXPAND | Anak Dari " + parent); } } void expand_1() { if (lv == 1) { child1 = new ember_obj(max1, 0, lv, token); } else { if (st1 != max1) { if (st2 == max2) { child1 = new ember_obj(max1, max2, lv, token); } else { if (max1 > max2) { child1 = new ember_obj(max1, st2, lv, token); } else { child1 = new ember_obj(st1, max2, lv, token); } } } else { child1 = new ember_obj(max1, max2, lv, token); } } } void expand_2() { if (lv == 1) { child2 = new ember_obj(0, max2, lv, token); } else { child2 = new ember_obj(st1, 0, lv, token); } } void expand_3() { if (lv != 1) { child3 = new ember_obj(0, st2, lv, token); } } void expand_4() { if (lv != 1) { if (st2 != max2 && st1 > st2) { atob(); } else { btoa(); } } } void atob() { if (st1 > (max2 - st2)) { child4 = new ember_obj(st1 - (max2 - st2), st2 + (st1 - (st1 - (max2 - st2))), lv, token); } else { child4 = new ember_obj(0, st1 + st2, lv, token); } } void btoa() { if (st2 > (max1 - st1)) { child4 = new ember_obj(st1 + (st2 - (st2 - (max1 - st1))), st2 - (max1 - st1), lv, token); } else { child4 = new ember_obj(st1 + st2, 0, lv, token); } } String cetak(String komentar) { String hasil = ""; if (this.child1 == null && this.child2 == null && this.child3 == null && this.child4 == null) { } else { hasil += token + "->"; if (this.child1 != null) { hasil += child1.token; } if (this.child2 != null) { hasil += child2.token; } if (this.child3 != null) { hasil += child3.token; } if (this.child4 != null) { hasil += child4.token; } hasil += (komentar); } return hasil; } void get_ancestor(String token) { path.add(token); while (!history.get(token).parent.equalsIgnoreCase("root")) { path.add(history.get(token).parent); token=history.get(token).parent; } } } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
package com.faathin.artificialintellegence; /** * * @author Riyadh */ import java.util.Scanner; public class IDSv3 { public static double memory; public static void main(String args[]) { Scanner baca = new Scanner(System.in); System.out.print("Nilai MAX Ember 1 : "); int max1 = baca.nextInt(); baca.nextLine(); System.out.print("Nilai MAX Ember 2 : "); int max2 = baca.nextInt(); baca.nextLine(); System.out.print("Nilai Dicari : "); int cari = baca.nextInt(); baca.nextLine(); int i = 0; long startTime = System.nanoTime(); ember_obj cx = new ember_obj(max1, max2, cari, i); while (!ember_obj.find) { if (!ember_obj.find) { memory+=(double) (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024*1024); i++; ember_obj.history.clear(); cx = new ember_obj(max1, max2, cari, i); while (!ember_obj.balik.isEmpty()) { ember_obj.balik.pop(); } ember_obj.history.clear(); } } long endTime = System.nanoTime(); System.out.println("ANGKA " + cari + " Sudah ditemukan pada Level " + (i - 2)); System.out.print("PATH : "); while (!ember_obj.path.isEmpty()) { System.out.print(ember_obj.path.pop() + "->"); } System.out.println("[SUKSES DITEMUKAN]"); System.out.println("JUMLAH OPERASI PENJELAJAHAN NODE: " + ember_obj.count); System.out.println("\nSTATISTIK"); System.out.println("Memmory Digunakan : " +(int)memory+" MB"); System.out.println("Waktu Eksekusi : "+(endTime - startTime)/1000000+" ms"); //divide by 1000000 to get milliseconds. } } |
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 :
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.
