Masalah, Ruang Keadaan, dan Pencarian(1)

Masalah

¨      Untuk membangun sistem yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal:

1. Mendefinisikan masalah dengan tepat

• Spesifikasi yang tepat mengenai keadaan awal

• Solusi yang diharapkan

1. Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai
2. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah
3. Memilih teknik penyelesaian masalah yang terbaik

Masalah Sebagai Ruang Keadaan

¨      Untuk menghadapi dan menyelesaikan suatu masalah, perlu ditentukannya :

1. Posisi awal dari suatu masalah
2. Aturan – aturan yang berlaku secara legal atau formal
3. Adanya tujuan yang akan diselesaikan dari suatu masalah itu

Ruang Keadaan ( State Space )

¨      Adalah suatu ruang yang berisi semua keadaan yang memungkin.

¨      Untuk mendeskripsikan masalah dengan baik, harus:

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

¨      Cara untuk mempresentasikan ruang keadaan :

1. Graph Keadaan:

Yaitu terdiri dari node – node yang saling berhubungan dengan anak panah sebagai arah dari keadaan awal ke keadaan yang baru.

¨      Contoh lintasan dari M ke T :

M-A-B-C-E-T, M-A-B-C-E-H-T, M-D-C-E-T, M-D-C-E-H-T

1. Pohon Pelacakan :

¨      Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis

¨      Terdiri dari beberapa node, level 0 disebut akar atau keadaan awal

¨      Node akar : menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut ’anak’ .

¨      Node-node yg tidak memiliki anak disebut ’daun’ menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

¨      Metode Pencarian dan Pelacakan

–         Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).

–         Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

1. Completeness               : menjamin ada tidaknya solusi dari masalah tersebut
2. Time complexity           : waktu yang diperlukan
3. Space complexity         : banyaknya memori yang diperlukan
4. Optimality                     : menjamin ada tidaknya solusi yang lain

–         Dua teknik pencarian dan pelacakan :

1. Pencarian buta (blind search)

• Kekurangan:

1. Memungkinkan tidak ditemukannya tujuan yang diinginkan.
2. Solusi hanya 1 yang didapatkan.

¨      Pencarian melebar pertama (Breadth – First Search) : mengunjungi dari akar dengan arah kiri ke kanan terus turun ke level – level berikutnya hingga ditemukan solusinya.

• Keuntungan :

1. Tidak akan menemui jalan buntu
2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik
3. Jika ada satu solusi maka bread-first search akan menemukannya

• Kelemahannya

1. Membutuhkan memori yang cukup banyak
2. Membutuhkan waktu yang cukup lama

¨      Pencarian mendalam pertama (Depth – First Search) :

• Keuntungan

1. Memakan memory yang relative kecil
2. Secara kebetulan akan menemukan solusi dengan cepat
3. Pencarian terbimbing (heuristic search)

¨      Pendakian Bukit (Hill Climbing)

¨      Pencarian Terbaik Pertama (Best First Search)

Bagi teman-teman yang ingin mendownload versi lengkapnya silakan klik di sini materi ini kami dapat dari pak yudi ^^