MENDAPATKAN AIR 2 LITER DARI 2 BUAH EMBER YANG BERKAPASITAS 4 LITER DAN 3 LITER

 

Deskripsi

Ada dua buah ember air masing-masing berkapasistas 4 liter dan 3 liter. Semula isi keduanya kosong. Pada kedua ember tersebut tidak terdapat tanda ukuran batas volume. Ada sebuah keran air yang digunakan untuk mengisi air pada kedua ember tersebut. Bagaimana kita dapat mengisi tepat 2 liter air dengan ember berkapasistas 4 liter dan 3 liter pada ember berkapasitas 3 liter.

Misalkan := x =volume dari ember 4 liter, dan y = volume dari ember 3 liter.

 

Ruang Keadaan

Untuk masalah ini dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sehingga x=0,1,2,3,4 dan y=0,1,2,3

x|y	0	1	2	3
0	(0,0)	(0,1)	(0,2)	(0,3)
1	(1,0)	(1,1)	(1,2)	(1,3)
2	(2,0)	(2,1)	(2,2)	(2,3)
3	(3,0)	(3,1)	(3,2)	(3,3)
4	(4,0)	(4,1)	(4,2)	(4,3)

 

x : jumlah air dalam ember 4 liter

y : jumlah air dalam ember 3 liter

initial state : (0,0)

goal state  : (n, 2)

 

Rule	Keadaan Sekarang	Keadaan berikutnya
Isi penuh ember 4 liter	(x,y) if (x<4)	(4,y)
Tuangkan air dari ember 4 liter ke ember 3 liter hingga ember 3 liter penuh	(X,Y) IF X+Y=4, Y>0	1,Y+(4-Y)
Kosongkan embe r 4 liter	(X,Y) If y>0	(1,0)
Tuangkan selueuh air dari ember 4 liter ke ember 3 liter	(X,Y) If X+y=1, x=1	(0,y+x)
Isi penuh ember 4 liter	(X,Y) If (X<4)	(4,1)
Tuangkan isi ember 4 liter ke 3 liter hingga ember 3 liter penuh	(X,Y) If X+y=3,y>0	x-y, y+(y-x)
Kosongkan ember 3 liter	(X,Y) Y>0	(2,0)
Tuangkan seluruh air dari ember 4 liter ke ember 3 liter	(X,Y) If X+y=2, x=2	(0,2)