MASALAH, RUANG KEADAAN
Kecerdasan Buatan
Pokok Bahasan
Mendefinisikan Masalah dalam Ruang Keadaan Representasi Ruang Keadaan
Artificial Intelligence ARTIFICIAL INTELLIGENCE Output: SOLUSI
Input: MASALAH
Knowledge Base
Inference Engine
Permainan Catur
Keadaan awal :
Aturan-aturan untuk melakukan gerakan secara legal
IF
Then
Bidak putih pada Kotak(e,2), And Kotak(E,3) Kosong, And Kotak(E,4) Kosong Gerakkan bidak dari (E,2) ke (E,4)
Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya. Kemenangan ini ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi.
Ruang Keadaan
suatu ruang yang berisi semua keadaan yang mungkin
Penyelesaian masalah secara umum
Mendefinisikan suatu ruang keadaan; Menetapkan satu atau lebih keadaan awal; Menetapkan satu atau lebih tujuan; Menetapkan kumpulan aturan.
Representasi Ruang Keadaan
Graph Keadaan Pohon Pelacakan Pohon AND/OR Kasus …
Graph Keadaan A
3
4
B
E
6 C
M 5
2
8
H
3 I D
2
F
4
4
J
1
G
7
T 6
Lintasan dari M ke T: ◦ ◦ ◦ ◦
M-A-B-C-E-T M-A-B-C-E-H-T M-D-C-E-T M-D-C-E-H-T
◦ ◦ ◦ ◦ ◦
M-A-B-C-E-F-G M-A-B-C-E-I-J M-D-C-E-F-G M-D-C-E-I-J M-D-I-J
Lintasan yang menemui jalan buntu (tidak sampai ke T):
Pohon Pelacakan M
Level-0 Level-1
D
A B
I
C
Level-2
C
J
E
Level-3
Buntu
E
F
I
H
T
Level-4
Tujuan
F G
I J
Buntu Buntu
H
T Tujuan
T Tujuan
G
J
T
Buntu Buntu Tujuan
Level-5 Level-6
Pohon AND/OR M
A
B
(a)
M
C
A
arc yang terletak antara busur berarti AND
(b)
B
C
M A
B
H
D
E
C
T
Level-0
T
C
H
E
T
Level-1
T
Level-2
Contoh: Masalah Teko Air Ada 2 buah teko masing-masing berkapasitas 4 galon (teko A) dan 3 galon (teko B). Tidak ada tanda yang menunjukkan batas ukuran pada kedua teko tersebut. Ada sebuah pompa air yang akan digunakan untuk mengisikan air pada kedua teko tersebut. Permasalahannya: Bagaimanakah kita dapat mengisikan tepat 2 galon air ke dalam teko yang berkapasitas 4 galon?
Air tak terbatas 4 galon (teko A)
3 galon (teko B)
Penyelesaian …
Identifikasi ruang keadaan: ◦ Permasalahan ini dapat direpresentasikan dengan 2 bilangan integer, yaitu x dan y: x = air yang diisikan pada teko 4 galon (teko A); y = air yang diisikan pada teko 3 galon (teko B);
◦ Ruang keadaan: (x,y) sedemikian hingga x {0,1,2,3,4} dan y {0,1,2,3}.
Keadaan awal & tujuan: ◦ Keadaan awal, kedua teko dalam keadaan kosong: (0,0); ◦ Tujuan, keadaan dimana pada teko 4 galon berisi tepat 2 galon air: (2,n) untuk sembarang n.
Keadaan Awal
Tujuan
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(0,1)
(1,1)
(2,1)
(3,1)
(4,1)
(0,2)
(1,2)
(2,2)
(3,2)
(4,2)
(0,3)
(1,3)
(2,3)
(3,3)
(4,3)
Aturan-aturan
Atura n ke-
Jika
Maka
1.
(x,y) x<4
(4,y) Isi teko A.
2.
(x,y) y<3
(x,3) Isi teko B.
3.
(x,y) x>0
(x-d,y) Tuangkan sebagian air keluar dari teko A.
4.
(x,y) y>0
(x,y-d) Tuangkan sebagian air keluar dari teko B.
5.
(x,y) x>0
(0,y) Kosongkan teko A dengan membuang airnya ke tanah.
6.
(x,y) y>0
(x,0) Kosongkan teko B dengan membuang airnya ke tanah.
7.
(x,y) x+y 4 dan y > 0
(4,y-(4-x)) Tuangkan air dari teko B ke teko A sampai teko A penuh.
8.
(x,y) x+y 3 dan x > 0
(x-(3-y),3) Tuangkan air dari teko A ke teko B sampai teko B penuh.
9.
(x,y) x+y 4 dan y > 0
(x+y,0) Tuangkan seluruh air dari teko B ke teko A.
10.
(x,y) x+y 3 dan x > 0
(0,x+y) Tuangkan seluruh air dari teko A ke teko B.
11.
(0,2)
(2,0) Tuangkan 2 galon air dari teko B ke teko A.
12.
(2,y)
(0,y) Kosongkan 2 galon air di teko A dengan membuang airnya ke tanah.
Representasi ruang keadaan dengan pohon pelacakan. (0,0)
(4,0)
(4,3)
(0,0)
(0,3)
(1,3)
(4,3)
(0,0)
(3,0)
Salah satu solusi: Isi Teko A (gallon)
Isi Teko B (gallon)
Aturan yang dipakai
0
0
2
0
3
9
3
0
2
3
3
7
4
2
5
0
2
9
2
0
solusi
Contoh: Petani, Sayur, dan Kambing
Seorang petani akan menyeberangkan seekor kambing, seekor serigala, dan sayur-sayuran dengan sebuah boat yang melalui sungai. Boat hanya bisa memuat petani dan satu penumpang yang lain (kambing, serigala atau sayur-sayuran). Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh serigala.
Penyelesaian …
Identifikasi ruang keadaan
Keadaan Awal
Tujuan
◦ Permasalahan ini dapat dilambangkan dengan (JumlahKambing, JumlahSerigala, JumlahSayuran, JumlahBoat). ◦ Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah asal tidak ada kambing, ada serigala, ada sayuran, dan ada boat. ◦ Daerah asal: (1,1,1,1) ◦ Daerah seberang: (0,0,0,0)
◦ Daerah asal: (0,0,0,0) ◦ Daerah seberang: (1,1,1,1)
Aturan-aturan Aturan ke1. 2. 3. 4. 5. 6. 7.
Aturan Kambing menyeberang Sayuran menyeberang Serigala menyeberang Kambing kembali Sayuran kembali Serigala kembali Boat kembali
Salah satu solusi:
Daerah Asal
Daerah Seberang
Aturan yang dipakai
(1,1,1,1)
(0,0,0,0)
1
(0,1,1,0)
(1,0,0,1)
7
(0,1,1,1)
(1,0,0,0)
3
(0,0,1,0)
(1,1,0,1)
4
(1,0,1,1)
(0,1,0,0)
2
(1,0,0,0)
(0,1,1,1)
7
(1,0,0,1)
(0,1,1,0)
1
(0,0,0,0)
(1,1,1,1)
solusi
