MASALAH, RUANG KEADAAN dan PENCARIAN (kecerdasan buatan)

Inference Engine

Secara umum, untuk mendeskripsikan masalah dengan baik, hendaknya:

1. Mendefenisikan suatu ruang keadaan
2. Menetapkan satu atau lebih keadaan awal
3. Menetapkan satu atau lebih tujuan
4. Menetapkan kumpulan aturan

Beberapa cara untuk merepresentasikan ruang keadaan, yakni:

1. Graf Keadaan
2. Pohon Pelacakan
3. Pohon AND/OR

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

1. Graf Keadaan

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

1. Graf Keadaan

Pada graf keadaan dengan arah di atas:

>> Ada 4 lintasan yang mencapai tujuan, yakni :

1. M-A-B-C-E-T

2. M-A-B-C-E-H-T

3. M-D-C-E-T

4. M-D-C-E-H-T

>> Ada 5 lintasan yang tidak mencapai tujuan yakni :

1. M-A-B-C-E-F-G

2. M-A-B-C-E-I-J

3. M-D-C-E-F-G

4. M-D-C-E-I-J

5. M-D-I-J

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

1. Graf Keadaan

Kelemahan graf berarah:

>> Memungkinkan terjadi siklus (perulangan) seandainya graf tidak memiliki arah.

>> Sulit mencapai tujuan

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

b. Pohon Pelacakan

Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

b. Pohon Pelacakan

à Keuntungan pohon pelacakan:

>> Tujuan tercapai

>> Tidak terjadi siklus

à Kelemahan pohon pelacakan:

>> Proses pelacakan agak lama (perlu waktu

lama)

• 2. MASALAH, RUANG KEADAAN dan PENCARIAN

c. Pohon AND/OR

Kelemahan pada teknik pohon pelacakan dapat diselesaikan dengan teknik pelacakan menggunakan pohon AND/OR.

Metode Pencarian dan Pelacakan

Ada 2 teknik pencarian dan pelacakan, yakni:

1. Pencarian Buta (Blind Search)

a. Pencarian Melebar Pertama (Breadth-First Search)

b. Pencarian Mendalam Pertama (Depth-First Search)

2. Pencarian terbimbing (heuristic search)

a. Pembangkit & Pengujian (generate and test)

b. Pendakian Bukit (Hill climbing)

b.1 Simple Hill Climbing

b.2 Steepest-Ascent Hill Climbing

c. Pencarian Terbaik Pertama (Best First Search)

c.1 OR Graph

c.2 Algoritma A*

d. Simulated Annealing