Materi2 problem solving

State Space dan Problem Solving

Problem Solving

1. Definisikan masalah dengan tepat

2. Analisa masalahnya (buat ruang masalahnya)

3. Representasikan ‘task knowledge’

4. Pilih dan gunakan teknik pemecahan masalah terbaik

Pendefinisian Masalah Sebagai Pencarian Ruang

Keadaan

Aspek lain dari masalah

• keadaan awal (initial state)• keadaan akhir/tujuan (goal

state)• operatornya/aturannya

Contoh pada Catur

• Menspesifikasikan posisi awal dari papan catur

• Peraturan (rules) yang mendefinisikan langkah-langkah yang legal

• Tujuan (Goal) dari permainan adalah : memenangkan permainan.

Produksi Rule

• Sekumpulan Aturan (a set of rules)

• Knowledge Base /Data Base• Sebuah strategi pengontrol

(Control Strategy)• Aturan yang dipakai (a rule

applier)

Water Jug Problem

• Anda diberi dua buah gelas, yang satu ukuran 4 liter dan yang lain 3 liter. Kedua gelas tidak memiliki skala ukuran. Terdapat pompa yang dapat digunakan untuk mengisi gelas dengan air. Bagaimana anda mendapatkan tepat 2 liter air di dalam gelas ukuran 4 liter?

Analisa

• Masalah : A water jug problem

• Initial state:Diketahui dua buah gelas masing-masing berkapasitas 4 liter (A) dan 3 liter (B), dan sebuah pompa.

• Goal state:Isi gelas A (yang berkapasitas 4 liter) dengan 2 liter air!

State Space Problem

• Ruang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0, 1, 2, 3, atau 4 dan y = 0, 1, 2,atau 3; x menyatakan jumlah air dalam gelas ukuran 4 liter, dan y menyatakan jumlah air dalam gelas ukuran 3 liter. Keadaan mula-mula adalah (0,0). State tujuan adalah (2,n) untuk setiap nilai n.

Produksi Rule

Rule no Rules State Action

1. (x,y)

If x < 4

→ (4,y) Isi penuh gelas 4 liter

2. (x,y)

If y < 3

→ (x,3) Isi penuh gelas 3 liter

3. (x,y)

If x > 0

→ (x-d,y) Buang sebagian air dari gelas 4 liter

4. (x,y)

If y > 0

→ (x,y-d) Buang sebagian air dari gelas ukuran 3 liter

5. (x,y)

If x > 0

→ (0,y) Kosongkan gelas 4 liter

6. (x,y)

If y > 0

→ (x,0) Kosongkan gelas 3 liter

Rule

No.

Rules State Action

7. (x,y)

If x+y ≥4 and y > 0

→ (4,y-(4-x)) Tuangkan air dari gelas 3 liter ke gelas 4 liter sampai

gelas 4 liter penuh

8. (x,y)

If x+y ≥3 and x > 0

→ (x-(3-y),3) Tuangkan air dari gelas 4 liter ke gelas 3 liter sampai

gelas 3 liter penuh

9. (x,y)

If x+y ≤4 and y > 0

→ (x+y,0) Tuangkan seluruh air dari gelas 3 liter ke gelas 4 liter

10. (x,y)

If x+y ≤3 and x > 0

→ (0,x+y) Tuangkan seluruh air dari gelas 4 liter ke gelas 3 liter

11. (0,2) → (2,0) Tuangkan 2 liter air dari gelas 3 liter ke gelas 4 liter

12. (2,y) → (0,y) Buang 2 liter dalam gelas 4 liter sampai habis.

Solusi WJ

Jumlah galon

dalam gelas 4

galon

Jumlah galon

dalam gelas

3 galon

Aturan yang dilakukan

0 0 -

0 3 2

3 0 9

3 3 2

4 2 7

0 2 5 atau 12

2 0 9 atau 11

Apa ini?

Ruang Masalah

Dalam menganalisa suatu masalah kita perlu mengetahui beberapa karakteristik masalah, diantaranya adalah:

1. Apakah masalah dapat dipilah-pilah (decomposeable) menjadi sejumlah sub-masalah independent yang lebih kecil atau lebih mudah ?

 2. Dapatkah langkah-langkah penyelesaian yang terbukti tidak tepat diabaikan ?

3. Apakah ruang lingkup atau semesta pembicaraan

masalah dapat diprakirakan ? 4. Apakah solusi masalah yang baik telah

dibanding- kan dengan semua solusi yang dimungkinkan ?5. Apakah basis pengetahuan yang digunakan

untuk memecahkan masalah bersifat konsisten ? 6. Apakah benar-benar dibutuhkan sejumlah

besar informasi untuk memecahkan masalah

yang sedang dihadapi, atau pengetahuan hanya

penting untuk membatasi proses pencarian (searching) ? 

7. Apakah sebuah komputer sendirian dapat diberi

masalah dan kemudian menyajikan solusi secara sederhana, atau akankah solusi dari suatu masalah membutuhkan interaksi antara komputer dan manusia ?