Untuk membangun sistem yg mampu menyelesaikan masalah dengan AI : 1. Mendefinisikan masalah dengan tepat, mencakup,

spesifikasi yg tepat mengenai keadaan awal dan solusi yg diharapkan.

2. Menganalisis masalah tersebut dan mencari beberapa teknik penyelesaian masalah yg sesuai.

3. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut.

4. Memiliki teknik penyelesaian masalah yg terbaik.

Created A.Tohir from Dosen UIGM Mr.Zulkifli

◊ Definisikan / buat “State Space ” Ruang masalah◊ Tentukan Keadaan Awal State Space◊ Tentukan keadaan akhir/tujuan (Goal State)◊ Tentukan operatornya/ aturannya

Untuk Mendefinisikan suatu masalah :

Misalkan permasalahan yg dihadapi adalah “Permainan Catur”, maka harus Ditentukan :

1. Posisi Awal pd Papan Catur Posisi awal setiap permainan catur selalu sama, yaitu semua bidak diletakk-

an di atas papan catur dalam 2 sisi, yaitu kubu putih dan kubu hitam :

2. Aturan-aturan untuk melakukan gerakkan secara legal aturan-aturan ini sangat berguna untuk menentukan gerakan suatu bidak, yaitu melangkah dari satu keadaan ke keadaan lain. Misalkan untuk mempermudah menunjukkan posisi bidak, setiap kotak ditunjuk kan dalam huruf ( a, b, c, d, e. f. g. h) pada arah horizontal, dan angka (1, 2, 3, 4, 5, 6, 7, 8) pd arah vertikal. Suatu aturan untuk menggerak kan bidak dari posisi (e,2) ke (e,4), ditunjukkan pd aturan sbb :

If Bidak Putih pada kotak (e,2), And Kotak(e, 3) Kosong And Kotak (e,4) KosongThen Gerakkan Bidak dari (e,2) ke (e, 4)

Seperti terlihat pd gambar berikut :

3. Tujuan (Goal)Tujuan yg ingin dicapai adl. Posisi pd papan catur yg menunjukkan kemenangan seseorg. Thdp lawannya. Kemenangan ini ditandai dgn posisi raja yg sudah tidak dapat bergerak lagi.

Ruang keadaan (State Space) yaitu : suatu ruang yg berisi semua keadaan yg mungkin.

Created A.Tohir from Dosen UIGM Mr.Zulkifli

Graph Keadaan

Graph terdiri dari node-node yg menunjukkan keadaan yaitu :keadaan awal dan keadaan baru yg akan dicapai dgn menggunakan Operator. Node-node dalam graph saling dihubungkan dgn menggunakan busur yg diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya :

Beberapa cara merepresentasikan Ruang Masalah (Problem Space)

1. Graph Keadaan Contoh :

Created A.Tohir from Dosen UIGM Mr.Zulkifli

qerew

Struktur Pohon

Node AND/OR

Pada pohon AND/OR, Suatu masalah M yg hendak dicari solusinya dgn 3 kemungkinan yaitu A, B atau C. Artinya, masalah M bisa diselesaikan jika salah satu dari subgoal A,B atau C tidak terpecahkan.

M

A B C

M

CBA

fdsdsMasalah M hanya dpt diselesaikan dgn A and B

and C. Dgn kata lain, untuk memecahkan masalah M, maka hrs dipecahkan sub goal A,B dan C terlebih

dahulu.

Created A.Tohir from Dosen UIGM Mr.Zulkifli

Pohon AND/ORTujuan yg dicapai sampai dgn level 6 pd struktur pohon, Dengan menggunakan pohon AND/OR, maka bisa dipersingkat sampai level 2.

Contoh 1 :Ada 2 buah teko maasing-masing berkapasitas 4 galon (Teko A) dan3 galon (Teko B). Tidak ada tanda yg menunjukkan batas ukuran pd kedua Teko tsb. Ada sebuah pompa air yg akan digunakan untuk mengisikan air pd kedua teko tsb. Permasalhannya : Bagaimanakah kita dpt mengisikan tepat 2galon air ke dlmteko yg berkapasitas 4 galon

Penyelesaian :

A. Identifikasii ruang keadaan Permasalahan ini dpt direpresentasikan dgn 2 bilangan

integer, yaitu, X dan Y :• X = air yg diisikan pd teko 4 galon (teko A)• Y = air yg diisikan pd teko 3 galon (teko B)Ruang keadaan : (X,Y) sedemikian sehingga X € (0, 1,2,3,4) dan Y € (0,1,2,3)

B. Keadaan Awal dan Tujuan• Keadaan awal, kedua teko dlm keadaan kosong : (0,0)• Tujuan, keadaan dimana pd teko 4 galon berisi tepat 2

galon air(2,n) untuk sembarang n.C. Keadaan Teko Air Keadaan kedua teko dapat dilihat pd gambar berikut :

4 Galo

n

3 Galo

n

Teko “A” Teko “B”

Air tak terbatas

(0, 0)

(0, 1)

(0, 2)

(0, 3)

(1, 0)

(1, 1)

(1, 2)

(1, 3)

(2, 2)

(2, 1)

(2, 0)

(2, 3) (3, 3)

(3, 2)

(3, 1)

(3, 0)

(4, 4)

(4, 3)

(4, 1)

(4, 0

Keadaan Awal

Tujuan

Created A.Tohir from Dosen UIGM Mr.Zulkifli

     

Aturan Ke Jika Maka

1 (x,y) (4,y)

  X< 4 Isi Teko A

2 (x,y) (x,3)

  y< 3 Isi Teko B

3 (x, y) (x-d, y)

  X > 0 Tuangkan sebagian air keluar dari teko A

4 (x, y) (x,y-d)

  y > 0 Tuangkan seabagian air keluar dari teko B

5 (x, y) (0, y)

  X > 0 Kosongkan Teko A dgn membuang airnya ke tanah

6 (x,y) (x, 0)

  y > 0 Kosongkan teko B dgn membuang airnya ke tanah

7 (x, y) (4, y-(4-x)

  x + y ≥ 4 dan y > 0 Tuangkan air dari teko B ke teko A sampai teko A penuh

8 (x, y) (x-(3 - y) , y

  x + y ≥ 3 dan y > 0 Tuangkan air dari teko A ke teko B sampai teko B penuh

9 (x, y) (x + y, 0)

  x + y ≤ 4 dan y > 0 Tuangkan seluruh air dari teko B ke teko A

10 ( x, y ) (0, x+y)

  x + y ≤ 3 dan x > 0 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 dgn membuang airnya ke tanah.

D. Aturan-Aturan

E. Representasi ruang keadaan dgn pohon pelacakan

Tiap pohon menunjukkan suatu keadaan. Jalur dari Parent ke Child men- unjukkan suatu operasi. Tiap-tiap node pd pohon pelacakan ini memiliki node-node child yg menunjukkan keadaan yg dicapai parent.

(0, 0)

(4, 0 (0, 3)

(4, 3) (0, 0) (1, 3) (4, 3) (0, 0) (3, 0)

Contoh: 2

Masalah “ Petani, Kambing, serigala dan sayuran “

dfdsf

Penyelesaian 1. Identifikasi Ruang Keadaan Permasalahan ini dpt dilambangkan dgn (jumlahKambing, JumlahSerigala, JumlahSayuran, JumlahBoat). Sbg contoh daerah asal (0,1,1,1) berarti pd daerah asal tdk ada kambing, ada serigala, 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)

Created A.Tohir from Dosen UIGM Mr.Zulkifli

   

Aturan Ke Aturan 1 Kambing menyeberang

2 Sayuran menyeberang

3 Serigala menyeberang

4 Kambing kembali

5 Sayuran kembali

6 Serigala kembali

7 Boat kembali

     

Daerah Asal Daerah Seberang Aturan Yg. 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

Salah satu Solusi Yg. Dpt Ditemuakan adalah sbb :

NEXT TIMElanjut ke BAG 4

Created A.Tohir from Dosen UIGM Mr.Zulkifli