BAB III REPRESENTASI RUANG KEADAAN ( STATE SPACE)
A. Graph Keadaan Graph terdiri dari node-node yang menunjukkan keadaab yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node dalam graph keadaanya salig dihubungkan dengan menggunakan busur (arc) yang diberi panah untuk menunjukkan arah dari suatu keadaan ke adaan berikutnya. Dalam prakteknya sangatlah sulit untuk menggambarkan graph keadaan. Pada gambar 3.1 menunjukkan graph berarah dengan node M menunjukkan keadaan awal, dan node T adalah tujuan. Pada gambar tersebut kita dapat melihat ada 4 lintasan dari M ke T yaitu:
M–A–B–C–T
M–A–B–C–E–H–T
M–D–C–E–T
M–D–C–E–H–T
Kemudian ada juga lintasan yang tidak sampai ke tujuan/buntu yaitu:
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
Gambar Graph Keadaan :
11
A
F
B M
G
E T
C H D I
J
Gambar 3.1 Graph Keadaan Bentuk seperti ini biasanya cukup sulit untuk direpresentasikan dalam suatu software, karena
memungkinkan
adanya
silkus
dalam
graph
tersebut.
Misal
tanpa
mempertimbangkan arah akan didapat silkus :D-C-E-I-D. Node-node ini akan selalu berulang.
B.
Pohon Pelacakan Untuk menghindari kemungkinan adanya proses pelacakan node yang berulang
maka digunakan struktur pohon.
Sruktur pohon digunakan untuk menggambarkan
keadaan secara hirarkis. Pohon terdiri atas node-node. Node yang terletak pada level 0 disebut “akar”. Node akar menunjukkan keadaan awal yang biasanya merupakan topic atau objek. Node akar memiliki beberapa percabangan yang terdiri atas beberapa node successor yanga disebut “anak” . Namun jika dilakukan pencarian mundur, maka dapat dikatakan node tersebut memiliki predessor. Node yang tidak memilik anak disebut “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).
12
Gambar 3.2 menunjukkan graph dan terlihat tidak ada lagi siklus, karena setiap node tidak diperbolehkan memiliki cabang kembali ke node dengan level yang lebih rendah.
Level 0
M
A
Level 1
D
Level 2 B
I
C
Level 3
C
E
J
Level 4
E
F
I
H
T Tujuan
F
I
H
T
G
J
T
Level 5
Tujuan Buntu
G Buntu
J Buntu
Buntu
T
Tujuan
Level 6
Tujuan
Gambar 3.2 Struktur Pohon
C. Pohon AND/OR Pada ke dua cara yang telah disebutkan di atas, muncul masalah-masalah lain karean persoalan yang komplek sering tidak dapat diselesaikan secara langsung dalam ruang lingkup masalah. Persoalan tersebut bias diselesaikan dengan memecah menjadi
13
beberapa sub-sub yang sederhana. Strategi ini disebut Dekomposisi Dekomposisi ini digambarkan dengan grafik AND/OR Pada gambar 3.3a terlihat ada maslah M yang hendak dicari solusinya dengan 3 kemungkinan yaitu A, B, dan C. Artinya masalah M bias diselesaikan jika salah satu dari subgoal A,B,C tidak ter[ecahkan. Pada gambar 3.3b masalah M hanya bisa diselesaikna dengan A AND B AND C, jadi subgoal A, B dan C harus dipecahkan terlebih dulu
M
A
B
M
C
A
arc yang terletak antara busur B berarti AND
C
(b)
(a)
Gambar 3.3 Node AND/OR Untuk memecahkan persoalan yang berhubungan dengan simpul AND, seluruh anakkan simpul AND, seluruh anakan simpul AND tersebut harus dipecahkan. Jika menggunakan simpul OR maka pemecahan persoalan yang berhubungan dengan simpul induk dari simpul OR , maka salah satu anakan harus dapt dipecahkan. Pada gambar 3.4 memperlihatkan tujuan pada graph dari gambar 3.2. Dengan menggunakan pohon AND/OR, tujuan yang dicapai pada pohon sampai level 6 dapat dipersingkat hanya sampai pada level 2 saja.
14
M A
B
H
T
C
D
E
C
Level-0
T
H
E
T
Level-1
T
Level-2
Gambar 3.4 Pohon ANDOR
D. Kasus 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. Penyelesaian:
1. 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 akan diisikan pada teko 3 galon ( teko B)
Ruang keadaan: (x,y) sedemikian hinga x {0,1,2,3,4} dan y {0,1,2,3} 2. Keadaan awal dan 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
3. Keadaan teko air
15
Keadaan kedua teko dapat dilihat pada gambar 3.5
Keadaan awal
Tujuan
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(0,1)
(1,1)
(2,0)
(3,1)
(4,1)
(0,2)
(1,2)
(2,0)
(3,2)
(4,2)
(0,3)
(1,3)
(2,0)
(3,3)
(4,3)
Gambar 3.5 Keadaan teko air 4. Aturan-aturan Produksi Setelah merepresentasika keadaan awal dan tujuan yang ingin dicapai, maka dilanjutkan dengan membuat aturan-aturan produksi (production rule) yang berisi semua kemungkinan penyeleaian masalah yang mungkin.
16
Aturan-aturan untuk masalah teko air dapat digambarkan seperti pada tabel 3.1 Aturan
JIka
Maka
Keterangan
Ke 1
(X,Y | X < 4)
(4,Y)
Isi galon 4lt dengan air
2.
(X,Y| Y < 3)
(X,3)
Isi galon 3 lt dengan air
3.
(X,Y | X > 0)
(X-D, Y)
Keluarkan sebagian air dari 4 lt galon
4.
(X,Y| Y> 0)
(X,Y-D)
Keluarkan sebagian air dari 3 lt galon
5.
(X,Y | X >0)
(0,Y)
Kosongkan galon 4lt.
6
(X,Y| Y >0)
(X,0)
Kosongkan galon 3 lt
7.
(X,Y | X +Y>=4
(4,Y-(4-X))
Tuangkan air dari galon 3lt ke galon 4lt sampai
and Y>0) 8.
galon 4lt penuh
(X,Y | X +Y>=3
(X-(3-Y),3)
and X>0) 9.
Tuangkan air dari galon 4lt ke galon 3lt sampai galon 3lt penuh
(X,Y | X +Y<=4
(X+Y,0)
Tuangkan semua air dari gaon 3 lt ke galon 4 lt
(0,X+Y)
Tuangkan semua air dari galon 4 lt ke galon 3
and Y>0) 10.
(X,Y|X+Y <= 3, and X>0)
lt
Production rules dari Water Jug Problem Jumlah air di dalam galon Jumlah air di dalam galon Rule yang terpakai 4lt
3lt 0
0
2
0
3
9
3
0
2
3
3
7
4
2
5
0
2
9
2
0
Solusi
17
E. Kasus Petani, Kambing, Srigala dan Sayuran
Seorang petani akan menyeberangkan seekor kambing, seekor srigala, dan sayursayuran dengan sebuah boat yang melalui sungai. Boat hanya bias memuat petani dan satu penumpang yang lain ( kambing, srigala, atau sayur-sayuran). Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh srigala.
Penyelesaian: 1. Identifikasi ruang keadaan. Permasalaahn ini dapat dilambangkan dengan (Jumlahkambing, JumlahSrigala, JumlahSayuran, JumlahBoat). Sebagai contoh Daerah asal (0,1,1,1) berarti daerah asal tidak ada kambing, ada srigala, ada sayuran, dan ada boat. 2. Keadaan awal dan tujuan
Keadaan awal, pada kedua daerah: Daerah asal : (1,1,1,1) Daerah seberang: (0,0,0,0)
Tujuan, pada kedua daerah: Daerah asal: (0,0,0,0) Daerah seberang: (1,1,1,1)
3. Aturan-aturan Aturan dapat digambarkan pada table 3.2:
18
Tabel 3.2 aturan masalah petani ATURAN KE ATURAN 1.
Kambing menyeberang
2.
Sayuran menyeberang
3.
Srigala menyeberang
4.
Kambing kembali
5.
Sayuran kembali
6
Srigala kembali
7
Boat kembali
Salah satu solusi yang bias ditemukan dapat dilihat pada table 3.3 Tabel 3.3 Contoh solusi masalah DAERAH ASAL (1,1,1,1)
DAERAH SEBERANG (0,0,0,0)
ATURAN YANG DIPAKAI 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
19
20
