Problema, Problema Space And Search

PROBLEMA, PROBLEMA SPACE AND SEARCH

Hafsah

1

Hal yang dibutuhkan dalam membangun sistem  Mendefinisikan

masalah yang tepat  Menganalisa masalah serta mencari teknik penyelesaian yang sesuai  Merepresentasikan pengetahuan  Memilih teknik penyelesaian yang terbaik

2

Pendefinisian masalah  Definisikan

suatu ruang keadaan  Tetapkan satu atau lebih keadaan awal  Tetapkan satu atau lebih tujuan  Tetapkan kumpulan aturan

3

Pendefinisian Masalah Sebagai Pencarian Ruang Keadaan  Contoh

: A Water Jug Problem

 Diberi

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

Sistem Produksi Terdiri dari:  Himpunan aturan, terdiri dari sisi kiri (pola) : menentukan kemampuan aplikasi  sisi kanan : menggambarkan operasi yang dilakukan jika dilaksanakan. 

 Pengetahuan

(basis data) : berisi informasi untuk tugas tertentu.  Strategi kontrol : menspesifikasikan urutan aturan akan dibandingkan dengan basis data  menspesifikasikan cara pemecahan masalah 

A

rule applier (pengaplikasi aturan).

5

Strategi Kontrol Syarat-syarat strategi kontrol:  cause

motion : Strategi kontrol yang tidak menyebabkan motion tidak akan pernah mencapai solusi.  Systematic : Beberapa strategi kontrol yang sistematik biasa disebut sebagai metoda-metoda dalam teknik searching.

6

Strategi Pencarian Kriteria dalam strategi pencarian:  Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?  Time complexity: Berapa lama waktu yang diperlukan?  Space complexity: Berapa banyak memori yang diperlukan?  Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?

7

METODE PENCARIAN BUTA  Algoritma

dasar strategi kontrol

 Breadth-First

Search  Depth-First Search  Algoritma

pendukung pencarian:

 Trial

and error searching  Tree search  Optimum searching  Best first searching 8

1. Breadth-First Search (BFS)  Pencarian

dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi. 9

S

A

C

B

D

E

H

Pohon Breadth First Search

F

G

10

Algoritma BFS: 1. 2. 3. 4. 5. 6.

7.

Letakkan simpul awal pada OPEN If OPEN= kosong THEN keluar n:= first (OPEN) If GOAL (n) THEN Keluar REMOVE (n, OPEN), ADD (n,CLOSED) Ekspansikan n untuk memunculkan semua simpul anak. Suatu simpul anak yang tidak termasuk pada OPEN atau CLOSED diletakkan pada ekor (TAIL) dari OPEN dan berikan pointer ke-n GOTO langkah 2. 11

 OPEN s  A,B  C,D,B  C,D,E,F  D,E,F

CLOSEd S S,A S,A,B S,A,B,C…..

12

 Keuntungan

BFS

 Tidak

akan menemui jalan buntu  Jika ada satu solusi, maka BFS akan menemukannya. Jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.  Kelemahan

BFS

 Memori

banyak (untuk menyimpan semua node dalam satu pohon)  Waktu lama (menguji n level untuk mendapatkan solusi pada level (n+1) 13

2. Depth-First Search (DFS)  Pencarian

dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Demikian seterusnya sampai ditemukan solusi atau jika menemui jalan buntu akan dilacak kebelakang (Backtracking) 14

S

A

C

B

D

E

H

Pohon Depth First Search

F

G

15

 State

awal (S)  State akhir (H)  BFS

: S-A-B-C-D-E-F-H  DFS :S-A-C-D-B-E-H

16

Algoritma DFS: 1. 2. 3. 4. 5. 6.

7.

Letakkan simpul awal pada OPEN If OPEN= kosong THEN keluar n:= first (OPEN) If GOAL (n) THEN Keluar REMOVE (n, OPEN), ADD (n,CLOSED) Ekspansikan n untuk memunculkan semua simpul anak. Suatu simpul anak yang tidak termasuk pada OPEN atau CLOSED diletakkan pada kepala (HEAD) dari OPEN dan berikan pointer ke-n GOTO langkah 2. 17

 Keuntungan

DFS

 Memory

relatif kecil (menyimpan node pada lintasan aktif)  Mungkin menemukan solusi tanpa harus menguji lebih banyak ruang keadaan  Kelemahan

DFS

 Memungkinkan

tidak ditemukan tujuan yang

diharapkan.  Hanya mendapatkan satu solusi pada setiap pencarian. 18