Materi 3

METODE PENCARIAN dan PELACAKAN

Dalam metode ini, diperlukan kesuksesan dalam pencarian. Sebelum kita mendalami tentang metode ini, kita harus mengetahui dulu, apa itu kesuksesan dalam pencarian.

Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Dari suatu pencarian kita dapat menyimpulkannya pada kalimat Ruang Keadaan. Dimana Ruang Keadaan ini merupakan suatu ruang berisi semua keadaan yang mungkin.

Dalam Metode Pencarian dan Pelacakan, terdapat 4 kriteria yang digunakan untuk mengukur performansi metode pencarian yaitu :
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?

Dalam metode ini terdapat dua teknik Pencarian dan Pelacakan yaitu :
1. Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First Search)
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)
Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel

Keuntungan :
1. Memori yang relatif kecil.
2. Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi.

2. Pencarian terbimbing (heuristic search)
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)

Dari metode ini, kita akan membahas salah satu dari teknik metode Pencarian dan Pelacakan ini. Teknik yang akan kita bahas adalah Pecarian terbimbing atau pencarian Heuristic. Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic
Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine

A. Hill Climbing
Metode Pencarian Bukit (Hill Climbing) ini dibagi menjadi dua macam metode, yaitu :

• Simple Hill Climbing, algoritmanya sebagai berikut :
- Pertama kita mulai dengan pengujian, jika yang diuji merupakan tujuan, maka pengujian berhenti dan jika tidak, lakukan pengujian kembali dengan keadaan sekarang sebagai keadaan awal.
- Kerjakan langkah selanjutnya sampai solusinya ditemukan, atau sampai tidak ada operator baru. Kemudian cari operator yang belum pernah digunakan, setelah itu gunakan operator ini untuk mendapatkan keadaan yang baru. Periksa keadaan baru tersebut.
- Jika keadaan baru merupakan tujuan, maka pengujian selesai dan keluar. Jika bukan tujuan, kembali seperti tadi yaitu jadikan keadaan baru tersebut menjadi keadaan sekarang. Jika keadaan baru tetap bukan tujuan, gunakan iterasi.

• Steepest Ascent Hill Climbing
- Pertama kita mulai dengan pengujian, jika yang diuji merupakan tujuan, maka pengujian berhenti dan jika tidak, lakukan pengujian kembali dengan keadaan sekarang sebagai keadaan awal. Kerjakan hingga tujuan tercapai.
- Tentukan SUCC sebagai nilai heuristic terbaik dari successor-successor. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang. Gunakan operator tersebut dan bentuk keadaan baru.
- Periksa keadaan baru tersebut. Jika keadaan baru merupakan tujuan, maka pengujian selesai dan keluar. Jika bukan tujuan, bandingkan nilai heuristiknya dengan SUCC. Jika hasilnya lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.
- Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.