4/7/2016
ِ ب ِْس ِم ه اّلل َّالر ْ َْح ِن َّالر ِح ْ ِي
fakultas ilmu komputer
program studi
informatika
السالم عليكم ورحمة هللا وبركاته
07/04/2016
07/04/2016
Ruang Masalah / Keadaan
Masalah, Ruang Keadaan dan Pencarian
07/04/2016
Suatu ruang yang berisi semua keadaan yang mungkin Contoh : Kita dapat memulai bermain catur dengan menempatkan diri pada keadaan awal, kemudian bergerak dari satu keadaan ke keadaan yang lain sesuai dengan aturan yang ada, dan mengakhiri permainan jika salah satu telah mencapai tujuan 07/04/2016
1
4/7/2016
Contoh 1 : Masalah Petani
Ruang Masalah / Ruang Keadaan
Mendefinisikan suatu ruang keadaan (state space) Menetapkan satu atau lebih keadaan awal (initial state) Menetapkan satu atau lebih tujuan (goal state) Menetapkan kumpulan aturan (rules group)
07/04/2016
07/04/2016
Seorang Petani akan menyeberangkan seekor Kambing, seekor Srigala, dan Sayuran dengan menggunakan perahu menyeberangi sungai. Perahu hanya bisa memuat Petani dan salah satu dari yang hendak diseberangkan : (Kambing /Srigala / Sayuran). Jika ditinggalkan oleh Petani, maka Sayuran akan dimakan oleh Kambing dan Kambing akan dimakan oleh Srigala. 07/04/2016
07/04/2016
2
4/7/2016
Masalah Petani Identifikasi Ruang Keadaan ›Permasalahan ini dapat dilambangkan dengan (kambing, serigala, sayuran, petani). ›Contoh : daerah asal (0,1,1,1) = daerah asal tidak ada kambing,ada serigala,ada sayuran,ada petani.
Keadaan Awal & Tujuan ›Keadaan awal, pada kedua daerah : daerah asal = (1,1,1,1) daerah seberang = (0,0,0,0)
›Keadaan tujuan, pada kedua daerah : daerah asal daerah seberang
= (0,0,0,0) = (1,1,1,1)
07/04/2016
Identifikasi Masalah Inisialisasi : Sisi1 – Sisi2 dan satu sisi terdiri maksimum 4 objek Ruang keadaan: 1. Kambing menyeberang 2. Sayuran menyeberang 3. Srigala menyeberang 4. Kambing kembali 5. Sayuran kembali 6. Srigala kembali 7. Petani kembali Keadaan awal : KSSP – {0,0,0,0} Tujuan / Goal : {1,1,1,1} - KSSP 07/04/2016
Solusi (kambing,serigala,sayuran,petani)
07/04/2016
Renungkan Gambar ini !
07/04/2016
3
4/7/2016
Contoh 2 : Masalah Ember Permasalahan ini dapat dilambangkan dengan (kambing, serigala, sayuran, petani). Ruang keadaan: 1. Kambing menyeberang 2. Sayuran menyeberang 3. Srigala menyeberang 4. Kambing kembali 5. Sayuran kembali 6. Srigala kembali 7. Petani kembali
Deskripsi Masalah Ada 2 ember masing-masing berkapasitas 4 galon (ember A) dan 3 galon (ember B). Ada pompa air yg akan digunakan untuk mengisi air pada ember tersebut. Bagaimana dapat mengisi tepat 2 galon air ke dalam ember berkapasitas 4 galon? Ember A Kapasitas : 4 galon
Ember B Kapasitas : 3 galon
Isi = 2 galon? 07/04/2016
07/04/2016 STIKOM Artha Buana
14
Deskripsi Masalah / Sistem 1) Identifikasi Ruang Keadaan
Permasalahan ini dapat digambarkan sebagai himpunan pasangan bilangan bulat : x = jumlah air yg diisikan ke ember 4 galon (ember A) y = jumlah air yg diisikan ke ember 3 galon (ember B) Ruang keadaan = (x,y) sedemikian hingga x є {0,1,2,3,4} dan y є {0,1,2,3} 2). Penentuan Keadaan Awal & Tujuan Keadaan awal : Kedua ember kosong = (0,0) Tujuan : Ember 4 galon berisi 2 galon air = (2,y) , y є {0,1,2,3} 3) Representasi Ruang Keadaan i. Matriks Ruang Keadaan ii. Graf Keadaan, Pohon Pelacakan & Pohon OR / AND
Aturan-aturan : Diasumsikan kita dapat mengisi ember air itu dari pompa air, membuang air dari ember ke luar, menuangkan air dari ember yang satu ke ember yang lain.
4) Penetapan Aturan–aturan ( rules) :
07/04/2016
07/04/2016
4
4/7/2016
Representasi Ruang Keadaan
Penetapan Aturan-Aturan Aturan ke-
Awal (0,0) (0,1)
Goal (1,0) (1,1)
(2,0) (2,1)
(3,0) (3,1)
(4,0) (4,1)
1
(x,y) x<4
(4,y)
Isi penuh Ember 4 liter
2
(x,y) y<3
(x,3)
Isi penuh Ember 3 liter
3
(x,y) x>0
(x-d,y)
Buang sebagian air dari Ember 4 liter
4
(x,y) y>0
(x,y-d)
Buang sebagian air dari Ember 3 liter
(1,2)
(2,2)
(3,2)
(4,2)
5
(x,y) x>0
(0,y)
Kosongkan Ember 4 liter
(0,3)
(1,3)
(2,3)
(3,3)
(4,3)
6
(x,y) y>0
(x,0)
Kosongkan Ember 3 liter
07/04/2016
(x,y) x+y 4 and y > 0
(4,y-(4-x))
7
Tuangkan air dari Ember 3 liter ke Ember 4 liter sampai penuh
(x,y) If x+y 3 and x > 0
(x-(3-y),3)
8
Tuangkan air dari Ember 4 liter ke Ember 3 liter sampai penuh
(x,y) x+y 4 and y > 0
(x+y,0)
9
Tuangkan seluruh air dari Ember 3 liter ke Ember 4 liter
(x,y) x+y 3 and x > 0
(0,x+y)
10
Tuangkan seluruh air dari Ember 4 liter ke Ember 3 liter
(0,2)
(2,0)
Tuangkan 2 liter air dari Ember 3 liter ke Ember 4 liter
(2,y)
(0,y)
Buang 2 liter air dalam Ember 4 liter sampai habis.
11
07/04/2016
Keterangan
(0,2)
07/04/2016
12
Jika Maka
Jumlah Air Ember 4 Liter
Jumlah Air Ember 3 Liter
Operator yang diaplikasikan
0
0
?
07/04/2016
5
4/7/2016
07/04/2016
Jumlah Air Ember 3 Liter
Operator yang diaplikasikan
0 0
0 3
2 9
3
0
2
3 4 0 2
3 2 2 0
7 5 9 Solusi
07/04/2016
Apakah dengan 1 Keadaan Awal (0,0), mempunyai 4 Solusi (Tujuan / Goal) ? Awal
07/04/2016
Jumlah Air Ember 4 Liter
Goal
(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)
Representasi Ruang Keadaan A. Graph Keadaan Node-node keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya. 07/04/2016
6
4/7/2016
B. Pohon Pelacakan
Graf Keadaan
M T
o Node M : awal, node T : tujuan. Ada 4 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
o Lintasan buntu atau lintasan yang tidak sampai ke tujuan : • • • • •
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
07/04/2016
o Menggambarkan keadaan secara hirarkis o Node pada level-0 disebut ’akar/root’ - menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut ’anak/child’ o Node yg tidak memiliki anak disebut ’daun/leaf’ menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end). 07/04/2016
Pohon Pelacakan C. Pohon OR / AND o Pohon OR Solusi masalah M 4 kemungkinan A or B or C or D o Pohon AND
Solusi masalah M A and B and C and D 07/04/2016
07/04/2016
7
4/7/2016
o Masalah sebelumnya jika diselesaikan dengan Pohon AND / OR :
07/04/2016
o Masalah sebelumnya jika diselesaikan dengan Pohon AND / OR :
07/04/2016
هللا خ ْ ًَْيا َك ِث ْ ًْيا َج َز ماُكم م السالم عليكم ورحمة هللا وبركاته
07/04/2016
8
