FINAL REPORT TUGAS I ARTIFICIAL INTELLIGENCE

DYNAMIC WATER JUG DENGAN MENGGUNAKAN ALGORITMA A*

Kelompok 23 (WaterJug...Oh…WaterJug) Kelas IF-29-05

OLEH :

NIM NAMA NILAI 113050243 Dhilla Rahadian M 113050252 Radityo Basith 113050258 James Rukka EB

INSTITUT TEKNOLOGI TELKOM

DEPARTEMEN TEKNIK INFORMATIKA BANDUNG

2008

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.

Gambaran kasus water jug sederhana dan alternatif penyelesaiannya adalah sebagai

berikut:

Gambar 1: Gambaran kasus water jug

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:

         Wadah A   Wadah B  Wadah C 

Kolam air  

 

3 l 

 

4 l   1 l

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 a

selanjut

Beryang ak

No 1 2

3

4

5

6

7

8

9 10

Se

oleh gam

Pro

Pro

ada sejumla

tnya yang m

rikut adalahkan digunak

S(x,y(x,y

(x, y) if x

(x, y) if y

(x,y) if x+

(x, y) if x+

(x, y) if x+

(x, y) if x+

(x,y(x,y

ebagai gamb

mbar beriku

oses 1 :

oses 2 :

ah aturan

mungkin bis

h sejumlah kan sebagai

State y) if x = 0 y) if y = 4

<= 1 and x

<= 1 and y

+y >= 3 and

+y >= 4 and

+y <= 3 and

+y <= 4 and

y) if x= 3 y) if y = 4

baran dalam

ut:

atau rule

sa dilakukan

aturan yanaturan untu

Nex(3(x

x != 0 (0,

y != 0 (x,

y >0 (3, y-

d x>0 (x-(4

d y>0 (x+

d x>0 (0,

(0(x

Tabel 1 Atu

m bentuk tre

3

yang digu

n.

ng mungkinuk meng-exp

xt state , y, z)

x, 4, z)

y, (x))

0, (y))

-(3-x), z)

4-y), 4, z)

+y, 0, z)

x+y, z)

0, y, z) x, 0, z)

uran Produks

ee-search ad

0,0,0

0,0,0

3,0,0 0,4,0

unakan un

n terjadi dapand sukses

isi wisi w

Tuang

Tuang

Tuangkasam

Tuangkasam

Tuang

Tuang

kk

si Water Jug

dalah sebag

0

ntuk meng-

alam kasus sor suatu sta

Deskripwadah A samwadah B samgkan seluruh

ke wadagkan seluruh

ke wadaan isi wadahmpai wadahan isi wadahmpai wadahgkan seluruh

ke wadagkan seluruh

ke wadakosongkan wkosongkan w

aimana yan

-expand sta

water jug ate:

psi mpai penuh mpai penuh h isi wadah ah C h isi wadah ah C h B ke wadah A penuh h A ke wadah B penuh h isi wadah ah A h isi wadah ah B wadah A wadah B

ng akan ditu

ate-state

kali ini,

A

B

ah A

ah B

B

A

unjukkan

Pro

Pro

Pro

Pro

Pro

oses 3:

oses 4 :

oses 5 :

oses 6 :

oses 7 :

3

3

3,4,0

3,4,0

3,0,

3,4,0 0,0,

3,0,0

3,4,0 0,0,

3,0,0

3,4,0

3,0,0

0,0,0 0,

3,0,0

0,0,0

,0 0,4,0

0

3,0,0

,0

0,4,0 3

3,0,0

,0

0,4,0 3

0,0,0

3,0,0

0,0,0

0,0,0

,3,0 3,4,

0,0,0

,3,0 3,4,0

0,0,0

0,3,0

,3,0 3,0,0

0,0,0

0,3,0

,3,0 3,0,0

0

0,3,0

0,4,0

0,4,0

,0 0,0,0

0,4,0

0 0,0,0

0

0,4

3,4,0 0,0

0

0,4

3,4,0 0,0

3,0,0

3,1,0

3,1,0

4,0

0,0 3,1,0

4,0

0,0

0,4,0

3,1,0

0

0

Pro

Pro

Jad

kondisi

dengan

keadaan

Bia

heuristi

pemban

baru ya

kecil ya

berikutn

Di

masalah

goalnya

oses 8 :

oses 9 :

di, setiap kit

node mana

demikian a

n yang seka

aya yang dik

iknya [h(n)

nding dalam

ang masuk.

ang mungk

nyalah yang

halaman s

h water jug

a masih men

3,4,0 0,0

3,0,0

3,4,0 0,0

3,0,0

Gamb

ta menjump

a yang sesu

akan diketah

arang.

keluarkan [

)]. Hasil p

m penguruta

Kemudian

kin akan me

g akan dicob

selanjutnya

g yang diim

ngikuti atur

3,0,0

0,0

0,4,0 3

3,0,0

0,0

0,4,0 3

bar 2: Tree Se

pai suatu sim

uai dengan r

hui kondisi

g(n)] akan

penjumlahan

an pada frin

dari fringe

engantarkan

ba untuk dip

adalah gam

mplementas

ran sebelum

0,0

0,3,0

3,3,0 3,0,

0,0

0,3,0

3,3,0 3,0,

earch dalam p

mpul dalam

rule atau atu

i-kondisi ap

selalu di-up

n kedua n

nge. Fringe

e tersebut, d

n ke node tu

proses.

mbaran pro

sikan dalam

mnya.

0,0

0

3,4,0 0,

3,0,0

0,0

0

3,4,0 0,

3,0,0

proses algorit

m tree-searc

uran produk

pa saja yang

pdate serta a

nilai tersebu

e akan diuru

diambil nod

ujuan. Apa

oses algorit

m bentuk ta

0,4,0

,0,0

0,4,0

0,4,0

,0,0

0,4,0

tma A*

ch akan dila

ksi water ju

g mungkin a

akan dijuml

ut [f(n)] a

utkan setiap

de yang ber

abila tidak,

tma A* un

abel. Untuk

3,1

0,1,0 0,4

3,1

0,1,0 0,4

akukan pen

ug di atas, s

akan terjadi

lahkan deng

akan menja

p kali ada

rbiaya [f(n)

maka nilai

ntuk menye

k kondisi aw

1,0

4,0 3,0,1

1,0

4,0 3,0,1

ngecekan

sehingga

i setelah

gan nilai

adi nilai

keadaan

)] paling

terkecil

lesaikan

wal dan

Tabel 1: Proses algoritma A* untuk menyelesaikan masalah water jug

Jalur yang terbentuk: (0,0,0) → (0,4,0) → (3,1,0)→ (3,0,1)

Pada dasarnya, algoritma A* menggunakan tree-search sebagai penyimpan kondisi dan

nilai node-node yang mungkin memberikan nilai terbaik dalam ruang pencarian. Selain itu

digunakan pula struktur link-list dengan algoritma deleteFirst dan sortList sebagai fringe atau

buffer. Akan tetapi, dapat pula diimplementasikan dalam bentuk array yang berisi banyak

state dari water jug sebagaimana yang diterapkan dalam tugas besar kali ini.

2. SIAPA MENGERJAKAN APA

Berikut adalah pembagian tugas dalam pembangunan software simulasi water jug dari

perancangan sampai pengujian:

1. Dhilla Rahadian M (113050243)

o User Interface Designer

merancang dan mengerjakan semua tata letak komponen program, alur program,

sampai latar belakang aplikasi.

o Software Programmer

bekerjasama dengan James sebagai programmer utama dengan menyesuaikan

pada rancangan User Interface dan rancangan program

o Software Tester

mengetest sejauh mana daya tahan dan tingkat kebenaran program di tiap tahap

2. James Rukka EB (113050258)

o Programmer Designer

merancang algoritma dan mekanisme kerja aplikasi serta mengenalisa masalah

water jug dan solusinya

o Software Programmer

bekerjasama dengan Dhila RM sebagai programmer utama dengan menyesuaikan

pada rancangan User Interface dan rancangan program.

o Software Tester

mengetest sejauh mana daya tahan dan tingkat kebenaran program di tiap tahap

3. Radityo Basith (113050252)

o Project Manager

melakukan manajemen jadwal pengerjaan, menyediakan referensi, serta

memanajemen pendokumentasian program

o System Analyzer

analisa terhadap rancangan algoritma maupun user interface program

o Sofware Tester

mengetest kebenaran program pada tahap akhir dan usul perbaikan

4. RANCANGAN STRUKTUR DATA & ALGORITMA

Dalam pembuatan program Water Jug kali ini, kelompok kami menggunakan aplikasi

pemrograman Delphi 2007 dengan bahasa pemrograman yang digunakan sama dengan bahasa

pemrograman Pascal. Alasan pemilihan bahasa dan aplikasi pemrograman tersebut yaitu

bahwa bahasa pemrogramannya lebih mudah dimengerti dan bisa memenuhi semua

requirement dari spesifikasi tugas besar yang diberikan (interface harus berbasis GUI).

4.1 Struktur Data, Fungsi Cost dan Aturan Produksi

Untuk struktur datanya sendiri, kelompok kami menggunakan tabel sebagai media

penyimpanan semua informasi mengenai status node baik yang telah di-expand maupun yang

akan segera di-expand. Sedangkan cara menggambarkan kondisi/status node yaitu dengan

notasi {jug1, jug2, jug3}, dimana tiap variabel disimpan dalam suatu field tersendiri pada

tabel. Tabel yang digunakan ada 3 buah tabel yaitu :

a) Tabel1 : berfungsi untuk menyimpan data status node yang menyangkut parent,

g(n), h(n), dan f(n). Record yang digunakan untuk pembentukkan Tabel1

yaitu Rec1.

i jug1 jug2 jug3 parent g(n) h(n) f(n)

.. ... ... ... ... ... ... ...

b) Tabel2 : untuk menyimpan semua informasi node yang telah di-expand dengan

kondisi terurut secara ascending berdasarkan f(n). Record yang digunakan

untuk membentuk Tabel2 yaitu Rec2

i jug1 jug2 jug3 f(n)

.. ... ... ... ...

Ket : isi dari field i tergantung dari nilai field i di Tabel1 yang menunjuk

ke suatu status node.

c) Result : digunakan jika proses expanding node telah selesai dilakukan dan

ditemukan solusi. Tabel ini digunakan untuk mengambil semua index

parent dari node tujuan dengan tracing mundur sampai ke kondisi awal

(node awal).

in in-1 in-2 ... 1

Hal penting berikutnya yaitu bagaimana mencari nilai heuristik cost dan nilai real cost

untuk kasus Water Jug.? Untuk menghitung nilai heurisitik cost, kami menggunakan fungsi

sebagai berikut :

dimana : xi , yi = adalah usaha yang telah dikeluarkan untuk mencapai state tersebut

Zmax-zn = kondisi kekurangan jug goal saat itu untuk ke tujuan (goal state)

h(n) = nilai heuristic cost, dimana return value = hasil pembagian yang

dibulatkan ke atas dengan fungsi ‘Ceil’ (bukan sisa pembagian).

Fungsi h(n) tersebut dapat diartikan sebagai perbandingan usaha yang dilakukan saat itu

terhadap kurangnya air saat itu juga untuk mencapai goal yang diinginkan. Jadi misalkan kita

mengisi suatu jug A sampai penuh maka usaha yang dilakukan adalah xi dan karena jug

kedua tidak dilakukan apa-apa, maka yi = 0, lalu usaha yang telah dilakukan tersebut

dibandingkan dengan tujuan yang ingin dicapai saat itu. Sedangkan untuk menghitung nilai

real cost, kami menggunakan besarnya usaha yang digunakan untuk memasukkan air ke

suatu jug, membuang air dari suatu jug, ataupun untuk memindahkan air dari jug satu ke jug

yang lain dengan ditambah real cost sebelumnya. Misal: kapasitas masing-masing jug yaitu

{4,3,1}, current state {0,0,0}, dan next-state {4,0,0}, maka nilai real cost = 4+0 = 4.

Hal berikutnya yang harus didefinisikan yaitu mengenai aturan-aturan produksi yang

merupakan rule dalam meng-expand suatu node. Dalam program, semua aturan produksi ini

diletakkan dalam satu procedure ExpandNode(j1, j2, gol : Integer), dimana secara

keseluruhan aturan produksi tersebut dapat dilihat pada tabel berikut :

h(n) = Ceil( (xi + yi ) / Abs( Zmax-zn ))

No State Next state Deskripsi

1 (x,y) if x = 0 (3, y, z) isi wadah A

2 (x,y) if y = 0 (x, 4, z) isi wadah B

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) 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 

Mengingat tidak semua kombinasi jug/wadah yang diinputkan user memiliki solusi,

maka diperlukan suatu fungsi khusus yang berperan untuk mengecek apakah inputan user

tersebut memiliki solusi dan valid untuk dikerjakan atau tidak. Dalam algoritma kami, fungsi

tersebut disebut fungsi CekJug() dengan hasil Boolean yang mengembalikan nilai True jika

valid dan False jika tidak valid/tidak mungkin ada solusi. Prinsip yang kami gunakan, bahwa

suatu kombinasi untuk 3 buah jug akan, misal A, B, dan C dimana jug C adalah goal, akan

valid dan akan ada solusi jika memenuhi kalimat berikut:

A or B or (A+B) or abs(A-B) or (A mod B) or (B mod A) € factor-faktor C

dengan adanya fungsi ini, maka dapat dihindari loop pencarian tak hingga (karena tak ada

solusi) yang dapat menyebabkan program mengalami crash.

Di samping itu, masih ada procedur/function pendukung lain seperti InsertTabel1,

InsertTabel2, SortTabel2, berbagai atribut global dan lain-lain yang akan ditunjukkan

kegunaannya dalam penjelasan algoritma program berikut ini.

4.2 Algoritma Program

Algortima program yang kami buat, tidak jauh beda dengan yang telah diajarkan

diperkuliahan mengenai A* search. Alur jalannya program yaitu sebagai berikut:

a) Pada kondisi awal, akan di-assign status awal {0,0,0}, dimana setelah menghitung

nilai heuristic cost dan real cost, maka informasi tersebut akan langsung diinsertkan

ke dalam Tabel1 dan Tabel2.

Di Tabel2 akan dilakukan pengurutan ascending berdasarkan nilai f(n). Kemudian,

informasi yang berada di nomor urut 1 (index2=1) akan di delete yang dilakukan oleh

procedure DelFirstTabel2(), dimana nilai yang di-delete tersebut dimasukkan dalam

variabel global i, node, f. Pada saat goal_state dicapai, informasi mengenai goal_state

yang dicapai dapat dilihat pada variabel global ini.

Di program juga disediakan variabel global jug_1, jug_2, jug_goal yang akan di-

update nilainya setiap kali proses insert ke tabel akan dilakukan. Proses ini dilakukan

oleh procedure KondisiJug(a, b, c : Integer).

b) Setelah itu, proses akan berlanjut ke perulangan (looping) meng-expand node

berdasarkan variabel i, node, f, yang terdiri dari proses-proses seperti pada langkah 1.

Looping terus dijalankan selama index2 (index untuk Tabel2) <> 1 dan jug_gol <>

gol_maks.

c) Pada saat kondisi looping tidak terpenuhi (program running succesfully), maka akan

dilakukan procedure GetParent(), yang menjalankan proses insert ke tabel Result

untuk semua index di Tabel1 yang menjadi jalur dari goal_state ke state {0,0,0}

berdasarkan informasi parent goal_state yang ada di variabel global i.

d) Langkah terakhir yaitu membaca tabel Result dari index terakhir ke index 1 untuk

memperoleh informasi bagaimana air dipindahkan dari satu jug ke jug lain hingga

memenuhi jug_gol (mencapai goal_state). Prose ini dilakukan oleh procedure

TimerTimer(Sender: TObject) yang disertai simulasi perpindahan nilai kapasitas air.

5. ANALISIS IMPLEMENTASI

No Kapasitas  Node di‐

expand Node 

diproses  Waktu  Hasil Jug A  Jug B  Jug Goal 1  12  12  12  11  3  0.003  Complete 2  1  1  1  11  3  0.005  Complete 3  4  3  1  18  7  0.005  Complete 4  22  25  3  18  7  0.005  Complete 5  45  30  15  20  8  0.005  Complete 6  5  3  2  18  7  0.005  Complete 7  40  25  15  28  11  0.005  Complete 8  16  4  8  32  10  0.005  Complete 9  6  2  4  35  11  0.005  Complete 10  36  20  16  28  11  0.006  Complete 11  3  7  2  106  45  0.007  Complete 12  14  6  4  113  48  0.007  Complete 13  4  1  3  176  56  0.008  Complete 14  35  5  15  166  53  0.008  Complete 15  10  1  3  166  53  0.008  Complete 16  7  2  6  199  64  0.009  Complete 17  10  3  2  272  117  0.012  Complete 18  10  3  4  504  177  0.025  Complete 19  14  1  4  939  301  0.096  Complete 20  14  1  4  939  301  0.096  Complete 

 

Table 2:Table percobaan terhadap 20 kasus water jug 

 

 

Grafik 1: Kebutuhan waktu solusi untuk kasus‐kasus di tabel sebelumnya 

Dapat dilihat bahwa pertumbuhan kebutuhan waktu dapat meningkat secara signifikan pada

kasus tertentu. Berdasarkan beberapa kali percobaan, dapat disimpulkan bahwa suatu kasus

dalam water jug akan membutuhkan solusi dan waktu yang lebih panjang jika terdapat

perbedaan yang besar antara jug goal dengan jug yang digunakan untuk mengisinya.

Percobaan diatas semuanya complete karena setiap masalah yang diajukan hanya yang

memiliki solusi. Seandai suatu kasus tidak memiliki solusi, maka program secara otomatis

akan memberi pemberitahuan. Menurut pengamatan pula, program akan selalu complete

dengan catatan node yang diperlukan tidak melebihi kapasitas buffer program.

0

0,02

0,04

0,06

0,08

0,1

0,12

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Grafik Perbandingan Suatu Problem Water Jug Terhadap Waktu

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

6. KESIMPULAN

- Algoritma A* merupakan perbaikan dari algoritma UCS dengan meminimalisasi jumlah

node yang diekspansi dalam tree-search, serta mampu memberikan solusi optimal

terhadap suatu masalah pencarian.

- A* adalah suatu teknik optimasi dari algoritma traversal graf. yang disebabkan oleh

penerapan heuristik pada saat pembangkitan pohon statusnya.

- Meskipun mampu memberikan solusi optimal serta algoritma yang sederhana, pada

kenyataannya algoritma A* juga memboroskan memori dalam segi pengurutan biaya-

biaya yang ada setiap kali ada biaya yang masuk.

7. Daftar Pustaka

[1] Suyanto. 2007. Artificial Intelegence. Bandung. Penerbit Informatika.

[2] Munir, Rinaldi. 2006. “Strategi Algoritmik”. Departemen Teknik Informatika, Institut

Teknologi Bandung

[3] Wikipedia Foundation, Inc. “A * Search Algorithm”.

http://en.wikipedia.org/wiki/A*_search_algorithm. Diakses tanggal 2 Maret 2008

pukul 21.00

[4] Jones, Justin Hayes. “A * Algorithm Tutorial”.

http://www.geocities.com/SiliconValley/Lakes/4929/astar.html. Diakses tanggal 2

Maret 2008 pukul 21.15

[5] Lester, Patrick. “A* Pathfinding for Beginners”.

http://www.gamedev.net/reference/articles/article2003.asp. Diakses tanggal 2 Maret

2008 pukul 21.20

[6] Rich, Mark. “Formalizing Search Spaces”.

http://pages.cs.wisc.edu/~richm/cs540/notes/search-un.html. Diakses tanggal 2 Maret

2008 pukul 21.30

Lampiran

Screen shot aplikasi: