Pemecahan masalah: THREE-GLASSES PROBLEM

Aturan

Terdapat tiga buah gelas dengan volume maksimal yang berbeda. Masing-masing berukuran 7 liter, 13 liter, dan 19 liter. Saat ini gelas berukuran 7 liter dan 13 liter terisi penuh dengan air, sedangkan gelas terakhir (gelas berukuran 19 liter) kosong. Tujuan dari permainan ini adalah memperoleh tepat 10 liter air pada gelas berukuran 13 liter dan 19 liter. Dalam menyelesaikan permainan ini, hal yang diperbolehkan adalah memindah-mindahkan isi satu gelas ke gelas lainnya. Gelas yang digunakan hanyalah ketiga gelas yang telah disebutkan sebelumnya.

Air yang digunakan hanyalah air dari gelas berukuran 7 liter dan 13 liter pada awal permainan (total 20 liter). Air tidak boleh dipindahkan kecuali ke salah satu dari dua gelas lainnya, atau dengan kata lain, air tidak boleh dibuang. Dari bentuk masing-masing gelas, kita sama sekali tidak bisa mengetahui dengan tepat (tanpa menggunakan alat bantu) volume air yang ada pada saat itu kecuali pada saat suatu gelas terisi penuh, yang berarti bahwa volume air adalah volume maksimal dari gelas penampungnya.

*Penyelesaian

Dalam menyelesaikan permainan ini dapat digunakan suatu algoritma, yang dalam hal ini algoritma yang digunakan adalah algoritma backtracking.

 

Algoritma Runut-balik

Algoritma runut-balik (backtracking) sangat erat hubungannya dengan pembentukan pohon ruang status. Pencarian solusi akan dilakukan dengan menelusuri simpul-simpul dalam pohon tersebut. Algoritma runut-balik melibatkan algoritma DFS (depth-first search) dalam penelusuran simpul-simpul pada pohon sehingga penelusuran dilakukan sampai simpul terdalam terlebih dahulu.

Secara umum, langkah-langkah dalam algoritma runutbalik

adalah sebagai berikut.

1.Simpul yang sudah dibangkitkan dinamai simpul hidup, sedangkan simpul yang sedang diperluasdinamai simpul-E. Pencarian solusi dilakukan denganmembentuk simpul akar sebagai simpul-E terlebihdahulu (simpul akar merupakan keadaan awal).

 

2. Perluas setiap simpul-E dengan menelusuri simpulsimpul anaknya sampai ditemukan simpul yang tidak mengarah ke solusi. Simpul tersebut dinamakan simpul mati. Sebuah fungsi yang digunakan untuk menandai sebuah simpul adalah simpul mati bernama fungsi pembatas. Simpul mati tidak akan diperluas lagi.

3. Jika menemukan simpul mati, proses perluasan dilakukan dengan membangkitkan simpul anak pada simpul bapak dari simpul mati yang ditemukan. Jika pada awal tahap 3 ini tidak ada lagi simpul yang dapat dibangkitkan, maka perluasan dilakukan pada simpul

pada aras setingkat di atasnya.

4. Pencarian selesai jika ditemukan sebuah solusi atau seluruh simpul sudah dibangkitkan.

Berikut adalah penjabarannya dalam notasi algoritma. procedure RunutBalikI(input n:integer)

{Mencari semua solusi persoalan dengan algoritma backtracking-iteratif.

Input: n (panjang vektor solusi)

Output: solusi = (x[1], x[2],…, x[n])}

Kamus

k : integer

Algoritma

k ← 1

while (k > 0) do

if (x[k] belum dicoba sedemikian

sehingga x[k]←T(k)) and

(B(x[1], x[2], … ,x[k])= true)

then

if (x[1],x[2],…,x[k]) adalah

lintasan dari akar ke daun then

CetakSolusi(x)

{endif}

k←k+1

else {x[1], x[2], …, x[k] tidak mengarah ke simpul solusi}

k←k-1 {runut-balik ke anggota

tupple sebelumnya}

{endif}

{endwhile; k = 0 }

 

Untuk memudahkan, selanjutnya gelas dengan volume maksimal 7 liter disebut dengan gelas pertama, gelas 1 liter gelas kedua, dan gelas 19 liter dengan gelas ketiga. Status pada state space tree menyatakan volume air yang ditampung masing-masing gelas pada saat itu. Status

tersebut dituliskan dengan format (v1, v2, v3), di mana v1 menunjukkan volume air pada gelas pertama, v2 pada gelas kedua, dan v3 pada gelas ketiga. Sebagai contoh, (0, 10, 10) berarti pada saat itu gelas pertama berisi 0 liter (kosong), gelas kedua dan ketiga berisi 10 liter. Dalam menentukan fungsi pembatas, penulis menemukan bahwa selama algoritma ini “bekerja”, sangat mungkin nantinya ditimbulkannya kembali suatu status (repeated-state). Status ini tentunya tidak dibangkitkan (atau kita anggap sebagai simpul mati). Oleh karena itu, dalam hal ini, fungsi pembatas akan memeriksa apakah status yang akan dibangkitkan sudah pernah dibangkitkan sebelumnya. Berarti, adanya penanganan untuk menampung status apa saja yang sudah pernah dibangkitkan. Selain itu, fungsi pembatas juga harus memeriksa apakah status yang dibangkitkan menunjukkan volume air yang melebihi dari volume maksimal masing-masing gelas. Terakhir, fungsi ini juga memeriksa apakah gelasdari pada saat itu kosong. Busur (edge) pada pohon dilabeli dengan pemindahan isi air yang dilakukan, yang dituliskan dengan format (cs, cf), di mana cs menunjukkan gelas mana yang isinya akan dipindahkan (atau gelas-dari) dan cf menunjukkan ke gelas mana isi dari gelas-dari akan dipindahkan (atau gelas-ke). Sebagai contoh, (1, 3) berarti dilakukan pemindahan isi gelas pertama ke gelas ketiga.

Berikut adalah ilustrasi dalam bentuk graf yang menunjukkan bagaiman algoritma runut-balik bekerja.

 

Ilustrasi proses pada saat algoritma “bekerja”

 

Simpul berwarna merah adalah simpul mati. Salah satu perluasan dari simpul (0, 1, 19) adalah (0, 1, 19). Ternyata ini adalah simpul mati karena telah dibangkitkan sebelumnya. Selanjutnya, perluasan dilanjutkan sampai dibangkitkannya simpul (7, 1, 12). Simpul inilah selanjutnya yang diperluas, hingg didapatkan simpul (0, 8, 12). Solusi yang ingin dicapai adalah (0, 10, 10). Dalam perluasan simpul-simpulnya, harus ditentukan prioritas busurnya. Pada contoh di atas, prioritasnya adalah (terurut dari busur dengan prioritas tertinggi) (1,2)-(1,3)-(2,1)-(2,3)-(3,1)-(3,2). Prioritas busur ini juga akan menentukan bagaimana proses yang akan berlangsung, baik itu mempengaruhi kedalaman solusi maupun banyaknya simpul yang harus dibangkitkan. Penentuan prioritas busur ini juga akan menentukan keoptimalan solusi yang akan dihasilkan Berikut adalah ilustrasi proses sampai tercapainya solusi. Ilustrasi berikut tidak menampilkan percabangan yang berujung pada simpul mati.

13

19

7

Ilustrasi hingga diperolehnya  solusi dari gelas berukuran 19 liter ,13 liter dan 7 liter

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s