Masalah Ruang Keadaan dan Pencarian (3)

Pencarian Heuristik

Ada 4 metode pencarian heuristic:

1. Pembangkit & Pengujian (Generate and Test)

2. Pendakian Bukit (Hill Climbing)

3. Pencarian Terbaik Pertama (Best First Search)

4. Simulated Annealing

Pencarian Terbaik Pertama (Best First Search)

• Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut.

• Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini.

• Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.

Penentuan node berikutnya adalah node yang terbaik yang pernah dibangkitkan

Masalah, Ruang Keadaan, dan Pencarian(2)

Metode Pelacakan dan Pencarian

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

1. Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
2. Time complexity : berapa lama waktu yang diperlukan?
3. Space complexity : berapa banyak memori yang diperlukan
4. Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

Dua teknik Pelacakan dan Pencarian

Dua teknik pencarian dan pelacakan

1. Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First Search)

• Pencarian mendalam pertama (Depth – First Search)

2. Pencarian terbimbing (heuristic search)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama (Breadth-first Search)

Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1. Mulai dari akar terus ke level 1 dari kiri ke kanan.Kemudian ke level selanjutnya hingga solusi ditemukan

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