teknik pencarian (searching)

24
TEKNIK PENCARIAN (SEARCHING) KECERDASAN BUATAN

Upload: izzy

Post on 16-Feb-2016

190 views

Category:

Documents


1 download

DESCRIPTION

TEKNIK PENCARIAN (SEARCHING). KECERDASAN BUATAN. Masalah , Ruang Keadaan dan Pencarian. Untuk membangun sebuah sistem yang digunakan untuk menyelesaikan suatu problem, dibutuhkan 3 hal sbb : - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: TEKNIK PENCARIAN (SEARCHING)

TEKNIK PENCARIAN (SEARCHING)

KECERDASAN BUATAN

Page 2: TEKNIK PENCARIAN (SEARCHING)

Masalah, Ruang Keadaan dan PencarianUntuk membangun sebuah sistem yang digunakan untuk menyelesaikan suatu problem, dibutuhkan 3 hal sbb :1. Mendefinisikan ruang masalah untuk masalah

yang dihadapi : spesifikasi kondisi awal dan solusi yang diharapkan.

2. Mendefinisikan aturan produksi yang digunakan untuk mengubah state ke state lainnya

3. Memilih metode pencarian yang tepat sehingga menemukan solusi terbaik dengan usaha yang minimal

Page 3: TEKNIK PENCARIAN (SEARCHING)

Metode PencarianPencarian buta atau tidak berbekal informasi

(blind or un-informed search)Pencarian dengan panduan ( heuristic or

informed search)

Page 4: TEKNIK PENCARIAN (SEARCHING)

Ruang MasalahMasalah utama dalam membangun sistem

berbasis AI adalah bagaimana mengkonversikan situasi yang diberikan kedalam situasi lain yang diinginkan menggunakan sekumpulan informasi tertentu.

Page 5: TEKNIK PENCARIAN (SEARCHING)

Contoh PermasalahanDiberikan 2 ember air yang berkapasitas 8 liter dan 6 liter. Kita dapat mengisi satu ember dari ember lainnya dan proses penakaran hanya dengan memakai 2 ember tersebut. Bagaimana kita bisa mengisikan tepat 4 liter dalam ember 8 liter? Asumsikan tidak boleh ada air yang hilang dalam proses penakaran".

Page 6: TEKNIK PENCARIAN (SEARCHING)

Langkah Penyelesaian Masalah Menentukan aksi-aksi (problem space) yang

bisa mengubah kondisi pada kedua ember dalam bentuk rule atau tree-diagram seperti dalam Gambar 1.1 Contoh kemungkinan aksi-aksi:a) Isi ember 8 literb) Isi ember 6 literc) Kosongkan ember 8 literd) Kosongkan ember 6 liter

Page 7: TEKNIK PENCARIAN (SEARCHING)

Langkah Penyelesaian Masalah (2)e) Isikan seluruh air dalam ember 8 liter ke 6 liter.f) Isikan seluruh air dalam ember 6 liter ke 8 liter.g) Penuhi ember 8 liter dari 6 liter.h) Penuhi ember 6 liter dari 8 liter.

Page 8: TEKNIK PENCARIAN (SEARCHING)

Langkah Penyelesaian Masalah (3)Menentukan urutan aksi untuk menghasilkan solusi, seperti:

Page 9: TEKNIK PENCARIAN (SEARCHING)

Permasalahan Jirigen AirAnda diberikan dua buah jirigen air tanpa skala ukuran, yang satu berkapasitas maksimum 4 galon dan yang lain berkapasitas maksimum 3 galon. Terdapat sebuah kran yang dapat mengalirkan air dengan jumlah tidak terbatas yang dapat digunakan untuk mengisi jirigen tersebut. Bagaimana langkah anda untuk mendapatkan tepat 2 galon air didalam jirigen berkapasitas 3 galon?

Page 10: TEKNIK PENCARIAN (SEARCHING)

Solusi Definisikan ruang masalah, initial state, goal

statex : jumlah air dalam jirigen 4 galony : jumlah air dalam jirigen 3 galoninitial state : (0,0)goal state : (n, 2)

Page 11: TEKNIK PENCARIAN (SEARCHING)

Solusi (2)Definisikan aturan produksi

Aturan produksi adalah : operasi yang mengubah suatu state ke state lainnya.

Contoh aturan produksi untuk permasalahan diatas

Page 12: TEKNIK PENCARIAN (SEARCHING)

1. (x,y) (4,y)if x < 4

Isi penuh jurigen 4 galon

2. (x,y) (x,3)if y < 3

Isi penuh jurigen 3 galon

3. (x,y) (x-d,y)if x > 0

Buang sebagian air dari jurigen 4 galon

4. (x,y) (x,y-d)if y > 0

Buang sebagian air dari jurigen 3 galon

5. (x,y) (0,y)if x > 0

Kosongkan jurigen 4 galon

6. (x,y) (x,0)if y > 0

Kosongkan jurigen 3 galon

7. (x,y) (4,y-(4-x))if x+y ≥ 4 and y > 0

Tuangkan air dari jurigen 3 galon ke 4 galon sampai jurigen 4 galon penuh

8. (x,y) (x-(3-y),3)if x+y ≥ 3 and x > 0

Tuangkan air dari jurigen 4 galon ke 3 galon sampai jurigen 3 galon penuh

9. (x,y) (x+y,0)if x+y ≤ 4 and y > 0

Tuangkan seluruh air dari jurigen 3 galon ke jurigen 4 galon

10. (x,y) (0,x+y)if x+y ≤ 3 and x > 0

Tuangkan seluruh air dari jurigen 4 galon ke jurigen 3 galon

11. (0,2) (2,0) Tuangkan 2 galon air dari jurigen 3 galon ke jurigen 4 galon

12. (2,y) (0,y) Buang 2 galon air dalam jurigen 4 galon sampai habis

Page 13: TEKNIK PENCARIAN (SEARCHING)

SolusiPilih metode pencarian yang tepatSalah satu solusi untuk masalah diatas

Jumlah Air dalam Jurigen 4 galon

Jumlah Air dalam Jurigen 3 galon

Aturan Produksi yang di aplikasikan

0 0 -

0 3 2

3 0 9

3 3 2

4 2 7

Page 14: TEKNIK PENCARIAN (SEARCHING)

Metode PencarianUntuk mengukur performasi metode

pencarian, terdapat empat kriteria yang dapat digunakan :CompletenessTime complexitySpace complexityOptimality

Page 15: TEKNIK PENCARIAN (SEARCHING)

Blind/Un-informed SearchBreadth First SearchUniform Cost SearchDepth First SearchDepth Limited SearchIterative-Deeping SearchBi-directional Search

Page 16: TEKNIK PENCARIAN (SEARCHING)

Breadth-First SearchBreadth-first search (BFS) melakukan proses

searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.

Urutan proses searching BFS ditunjukkan dalam Gambar berikut adalah: A,B,C,D,E,F,

Page 17: TEKNIK PENCARIAN (SEARCHING)
Page 18: TEKNIK PENCARIAN (SEARCHING)

Algoritma BFS1. Create a variable called NODE-LIST (queue) and

set it to the initial state.2. Until a goal state is found or NODE-LIST is empty

do: Remove the first element from NODE-LIST and call it E.

If NODE-LIST was empty, quit. For each way that each rule can match the state

described in E do: Apply the rule to generate a new state. If the new state is a gold state, quit and return

this state. Otherwise, add the new state to the end of

NODE-LIST.

Page 19: TEKNIK PENCARIAN (SEARCHING)

Karakteristik BFSJika ada solusi, maka BFS pasti akan

menemukannyaBFS akan menemukan solusi dengan panjang

jalur yang minimal (terpendek)No cycleMemori yang besar

Page 20: TEKNIK PENCARIAN (SEARCHING)

Depth-First SearchPencarian dilakukan pada suatu simpul dalam

setiap level. Jika pada level yang terdalam solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapar dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi

Page 21: TEKNIK PENCARIAN (SEARCHING)
Page 22: TEKNIK PENCARIAN (SEARCHING)

Algoritma DFS1. If the initial state is a goal state, quit and

return success.2. Otherwise, do the following until success or

failure is signaled: Generate a successor, E, of the initial state. If there

are no more successors, signal failure. Call Depth-First Search with E as the initial state. If success is returned, signal success. Otherwise

continue in this loop.

Page 23: TEKNIK PENCARIAN (SEARCHING)

Keuntungan DFSPemakain memori hanya sedikit, berbeda

jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.

Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Page 24: TEKNIK PENCARIAN (SEARCHING)

Kelemahan DFSJika pohon yang dibangkitkan mempunyai

level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).