Implementasi Algoritma A* Pada Permasalahan Optimasi Solusi Dynamic Water Jug

1. PENDAHULUAN

Algoritma dapat dikatakan sebagai urutan langkah-langkah logis yang sistematis dalam mencari suatu solusi dari suatu permasalahan yang ada. Pada program komputer, algoritma terdiri dari sekumpulan langkah-langkah untuk mencapai suatu tujuan, seperti logika if-then-else maupun pengulangan suatu tindakan atau langkah dengan loop. Begitu pula jika kita ingin mensimulasikan penyelesaian masalah water jug di komputer, maka diperlukan juga algoritma yang tepat agar masalah dapat ditangani se-efisien mungkin.

Water jug merupakan salah satu permasalah klasik yang sudah ada sejak lama dan kadang-kadang masih terjadi dalam kehidupan manusia sekarang. Masalah water jug dapat dibayangkan dengan suatu tujuan mengisi sebuah wadah yang diketahui kapasitasnya dengan air secara tepat penuh menggunakan dua atau lebih wadah lain yang juga telah diketahui kapasitasnya tetapi tidak mempunyai ukuran takaran. Dalam implementasinya, mungkin tidak ada solusi atau bahkan akan ada lebih dari satu solusi untuk menyesaikan masalah water jug tersebut. Memang sering kali terdapat banyak cara untuk menyelesaikan suatu masalah, akan tetapi dari sekian cara tersebut, memilih manakah yang paling optimal akan memerlukan suatu cara tersendiri.

Misalkan kita ingin mengisi penuh wadah C yang berkapasitas 1 liter dengan air dari kolam dengan menggunakan dua wadah lainnya yaitu wadah A dan wadah B yang kapasitasnya masing-masing adalah 3 liter dan 4 liter. Maka akan ada beberapa alternatif cara yang diantaranya sebagai berikut:

1)   Alternatif 1

-  Awalnya semua wadah kosong

-  Isi air ke wadah A sampai penuh

-  Tuangkan semua air dari wadah A ke wadah B

-  Isi kembali wadah A sampai penuh

-  Tuangkan sebagian isi wadah A ke wadah B sampai wadah B penuh

-  Kosongkan wadah A

-  Tuangkan sebagian isi wadah B ke wadah A sampai wadah A penuh

-  Tuangkan sisa air di wadah B ke wadah C

-  Akan didapat tepat 1 liter pada wadah C

2)   Alternatif 2

-  Awalnya semua wadah kosong

-  Isikan air ke wadah B sampai penuh

-  Tuangkan sebagian isi wadah B ke wadah A sampai wadah A penuh

-  Tuangkan sisa air di wadah B ke wadah C

-  Akan didapat tepat 1 liter pada wadah C

Dari kedua alternatif tersebut manakah yang lebih optimal dari segi usaha yang kita lakukan? Dalam hal inilah algoritma A* diperlukan dalam mencari solusi dengan upaya seoptimal mungkin.

1.       LANDASAN TEORI

1.1 Sekilas tentang algoritma A*

Algoritma A* menyelesaikan masalah yang menggunakan graf untuk perluasan ruang statusnya. Dengan menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan. Algoritma A* membangkitkan simpul yang paling mendekati solusi. Simpul ini kemudian disimpan suksesornya ke dalam list sesuai dengan urutan yang paling mendekati solusi terbaik. Kemudian, simpul pertama pada list diambil, dibangkitkan suksesornya dan kemudian suksesor ini disimpan ke dalam list sesuai dengan urutan yang terbaik untuk solusi.

Algoritma ini akan mengunjungi secara mendalam (mirip DFS) selama simpul tersebut merupakan simpul yang terbaik. Jika simpul yang sedang dikunjungi ternyata tidak mengarah kepada solusi yang diinginkan, maka akan melakukan runut balik ke arah simpul akar untuk mencari simpul anak lainnya yang lebih menjanjikan dari pada simpul yang terakhir dikunjungi. Bila tidak ada juga, maka akan terus mengulang mencari ke arah simpul akar sampai ditemukan simpul yang lebih baik untuk dibangkitkan suksesornya. Strategi ini berkebalikan dengan algoritma DFS yang mencari sampai kedalaman yang terdalam sampai tidak ada lagi suksesor yang bisa dibangkitkan sebelum melakukan runut balik, dan BFS yang tidak akan melakukan pencarian secara mendalam sebelum pencarian secara melebar selesai. A* baru berhenti ketika mendapatkan solusi yang dianggap solusi terbaik.

Algoritma A* menggabungkan jarak estimasi/heuristik [h(n)] dan jarak sesungguhnya/cost [g(n)] dalam membantu penyelesaian persoalan. Heuristik adalah nilai yang memberi harga pada tiap simpul yang memandu A* mendapatkan solusi yang diinginkan. Dengan heuristik, maka A* pasti akan mendapatkan solusi (jika memang ada solusinya). Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih baik dari pada algoritma lainnya. Namun heuristik masih merupakan estimasi/perkiraan biasa saja. Sama sekali tidak ada rumus khususnya. Artinya, setiap kasus memiliki fungsi heuristik yang berbeda-beda.

1.2 Analisis Penyelesaian Water Jug

Sebelum masuk ke penyelesaian, perlu diingat bahwa kondisi awal persoalan water jug ini adalah sebagai berikut:

-          Terdapat 3 wadah, yaitu wadah 3 liter, 4 liter, dan 1 liter

-          Diminta untuk mengisikan air ke wadah yang 1 liter secara tepat penuh dengan menggunakan dua wadah lainnya.

-          Diasumsikan sumber air dari kolam tidak terbatas

Umumnya sering kali terdapat lebih dari satu solusi di dalam penyelesaian suatu kasus water jug, tetapi dalam konteks kali ini, yang diminta adalah solusi terbaik dari sekian solusi yang ada. Jadi pada dasarnya adalah memilih satu dari seluruh kemungkinan solusi yang ada. Hal ini berkaitan dengan ekspansi node-node suksesor dari node atau status yang sekarang sedang terjadi, yang melibatkan sejumlah aturan yang khusus yang akan dijalankan jika kondisi sekarang memenuhi. Aturan tersebut dapat diibaratkan sebagai suatu tindakan yang mungkin untuk dilakukan seandainya suatu kondisi terjadi, sebagai contoh, semisalkan sekarang semua wadah sedang kosong maka berlaku aturan berikut, “Saat wadah A kosong, maka isi ulang sampai penuh” atau “Isi wadah B sampai penuh”. Begitu pula semisal kondisi lainnya sekarang sedang terjadi, seperti sekarang wadah B penuh dan wadah A kosong, maka akan ada sejumlah aturan atau rule yang digunakan untuk meng-expand state-state selanjutnya yang mungkin bisa dilakukan.

Berikut adalah sejumlah aturan yang mungkin terjadi dalam kasus water jug kali ini, yang akan digunakan sebagai aturan untuk meng-expand suksesor suatu state:

No	State	Next state	Deskripsi
1	(x,y) if x = 0	(3, y, z)	isi wadah A sampai penuh
2	(x,y) if y = 4	(x, 4, z)	isi wadah B sampai penuh
3	(x, y) if x <= 1 and x != 0	(0, y, (x))	Tuangkan seluruh isi wadah A ke wadah C
4	(x, y) if y <= 1 and y != 0	(x, 0, (y))	Tuangkan seluruh isi wadah B ke wadah C
5	(x,y) if x+y >= 3 and y >0	(3, y-(3-x), z)	Tuangkan isi wadah B ke wadah A sampai wadah A penuh
6	(x, y) if x+y >= 4 and x>0	(x-(4-y), 4, z)	Tuangkan isi wadah A ke wadah B sampai wadah B penuh
7	(x, y) if x+y <= 3 and y>0	(x+y, 0, z)	Tuangkan seluruh isi wadah B ke wadah A
8	(x, y) if x+y <= 4 and x>0	(0, x+y, z)	Tuangkan seluruh isi wadah A ke wadah B
9	(x,y) if x= 3	(0, y, z)	kosongkan wadah A
10	(x,y) if y = 4	(x, 0, z)	kosongkan wadah B

Tabel 1 Aturan Produksi Water Jug

Sebagai gambaran dalam bentuk tree-search adalah sebagaimana yang akan ditunjukkan oleh gambar berikut:

Advertisement