Suatu hari ada tugas dari Dosen
Artificial Intelligence untuk mencari suatu permasalahan dan penyelesaiannya.
Dan alhasil inilah yang saya kerjakan. Entah bagaimana saya pun terpilih untuk
presentasi di depan, walau di bombardir dengan berbagai macam pertanyaan.
Permasalahan yang saya ambil disini mengikuti contoh dari sebuah buku. Ya
semoga artikel ini bisa membantu kalian-kalian yang mendapatkan tugas yang
sama. Semoga beruntung.
Permasalahan : takaran minyak tanah hanya untuk 5 liter dan
7 liter. Definisikan masalah dan selesaikan untuk mendapatkan minyak tanah
sebanyak 3 liter di dalam takaran minyak tanah 7 liter.
Mendefinisikan masalah sebagai suatu ruang keadaan (state
space search)
- Identifikasi ruang keadaan
Permasalahan ini dapat
direpresentasikan dengan 2 bilangan integer, yaitu x dan y.
-
X = minyak tanah yang diisikan pada takaran 5
liter
-
Y = minyak tanah yang diisikan pada takaran 7
liter
Ruang keadaan : (x,y) sedemikian
sehingga x € {0,1,2,3,4,5} dan y € {0,1,2,3,4,5,6,7}
- Keadaan awal dan tujuan
-
Kedua takaran dalam keadaan kosong (0,0)
-
Tujuan, keadaan di galam takaran 7 liter berisi
tepat 3 liter minyak tanah : (n,3) untuk sembarang n
- Keadaan takaran minyak tanah (ruang keadaan)
|
|
(0,0)
Keadaan awal
|
(1,0)
|
(2,0)
|
(3,0)
|
(4,0)
|
(5,0)
|
|
|
(0,1)
|
(1,1)
|
(2,1)
|
(3,1)
|
(4,1)
|
(5,1)
|
|
|
(0,2)
|
(1,2)
|
(2,2)
|
(3,2)
|
(4,2)
|
(5,2)
|
|
tujuan
|
(0,3)
|
(1,3)
|
(2,3)
|
(3,3)
|
(4,3)
|
(5,3)
|
|
|
(0,4)
|
(1,4)
|
(2,4)
|
(3,4)
|
(4,4)
|
(5,4)
|
|
|
(0,5)
|
(1,5)
|
(2,5)
|
(3,5)
|
(4,5)
|
(5,5)
|
|
|
(0,6)
|
(1,6)
|
(2,6)
|
(3,6)
|
(4,6)
|
(5,6)
|
|
|
(0,7)
|
(1,7)
|
(2,7)
|
(3,7)
|
(4,7)
|
(5,7)
|
- Aturan-aturan
|
Aturan ke -
|
jika
|
Maka
|
|
1
|
(x,y)
X<5
|
(5,y)
Isi penuh takaran 5 liter
|
|
2
|
(x,y)
Y<7
|
(x,7)
Isi penuh takaran 7 liter
|
|
3
|
(x,y)
x>0
|
(x-d,y)
Tuangkan sebagian minyak tanah keluar dari takaran 5 liter
|
|
4
|
(x,y)
y>0
|
(x,y-d)
Tuangkan sebagian minyak tanah keluar dari takaran 7 liter
|
|
5
|
(x,y)
x>0
|
(0,y)
Kosongkan takaran 5 liter
|
|
6
|
(x,y)
y>0
|
(x,0)
Kosongkan takaran 7 liter
|
|
7
|
(x,y)
x+y≥5 dan y>0
|
(5,y-(5-x))
Tuangkan minyak tanah dari takaran 7 liter ke takaran 5 liter sampai
penuh
|
|
8
|
(x,y)
x+y≥7 dan x>0
|
(x-(3-y),y)
Tuangkan minyak tanah dari takaran 5 liter ke takaran 7 liter sampai
penuh
|
|
9
|
(x,y)
x+y≤5 dan y>0
|
(x+y,0)
Tuangkan minyak tanah dari takaran 5 liter ke takaran 7 liter
|
|
10
|
(x,y)
x+y≤7 dan x>0
|
(0,x+y)
Tuangkan minyak tanah dari takaran 7 liter ke takaran 5 liter
|
|
11
|
(2,0)
|
(0,2)
Tuangkan 3 liter minyak tanah dari takaran 5 liter ke takaran 7 liter
|
|
12
|
(x,2)
|
(x,0)
Kosongkan 3 liter minyak tanah di takaran 7 liter
|
Representasi ruang keadaan
- Solusi
|
Takaran 5 liter
|
Takaran 7 liter
|
Aturan yang dipakai
|
|
0
|
0
|
-
|
|
5
|
0
|
1
|
|
0
|
5
|
9
|
|
5
|
5
|
1
|
|
3
|
7
|
8
|
|
3
|
0
|
6
|
|
0
|
3
|
9 atau 11
|
- Menyelesaikan dengan metode Breadth-First Search (BFS)
Pencarian
dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke
kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan
pada level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan
strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling
baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah
dibangkitkan. Hal ini harus dilakukan untuk penelusuran balik jika solusi sudah
ditemukan.
Pohon Breadth First Search untuk permasalahan
diatas
No comments:
Post a Comment