Pencarian

Bab III

Pencarian

Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik

• Waktu aksesnya yang cukup lama

• Besarnya memori yang diperlukan

• 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

Pencarian Heuristik

• Operator

• Ubin kosong geser ke kanan

• Ubin kosong geser ke kiri

• Ubin kosong geser ke atas

• Ubin kosong geser ke bawah

Langkah Awal hanya 3 operator yang bisa digunakan

• Ubin kosong digeser ke kiri, ke kanan dan ke atas.

• Jika menggunakan pencarian buta, tidak perlu

mengetahui operasi apa yang akan dikerjakan

(sembarang)

• Pada pencarian heuristik perlu diberikan informasi

khusus dalam domain tersebut

Informasi yang bisa diberikan

Untuk jumlah ubin yang menempati posisi yang benar jumlah yang

lebih tinggi adalah yang lebih diharapkan (lebih baik)

Untuk jumlah ubin yang menempati posisi yang salah jumlah yang

lebih kecil adalah yang diharapkan (lebih baik).

Menghitung total gerakan yang diperlukan untuk mencapai tujuan

jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Ada 4 metode pencarian heuristik

• Pembangkit & Pengujian (Generate and Test)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search)

• Simulated Annealing

-Pembangkit & Pengujian (Generate and Test)

Pada prinsipnya metode ini merupakan penggabungan antara depthfirst search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma:

• Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik

tertentu atau lintasan tertentu dari keadaan awal).

• Uji untuk melihat apakah node tersebut benar-benar merupakan

solusinya dengan cara membandingkan node tersebut atau node

akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan

yang diharapkan.

• Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah

yang pertama.

Kelemahan

• Perlu membangkitkan semua kemungkinan sebelum

dilakukan pengujian

• Membutuhkan waktu yang cukup lama dalam

pencariannya

-Pendakian Bukit (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik, Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.

-Simple Hill Climbing

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada

operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan

keadaan yang baru.

• Evaluasi keadaan baru tersebut.

• Jika keadaan baru merupakan tujuan, keluar.

• Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan

keadaan baru tersebut menjadi keadaan sekarang.

• Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

-Steepest Ascent Hill Climbing

Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya

saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

Algoritma

Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan

sekarang.

• 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.

• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai

heuristiknya dengan SUCC. Jika 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.