Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching:
- Generate and Test
- Hill Climbing
- Best First Search
- Alpha Beta Prunning
- Means-End-Anlysis
- Constraint Satisfaction
- Simulated Annealing
- Problem Reduction
Disini saya akan membahas tentang 4 jenis heuristic, yaitu Best First search, Problem Reduction, Means-End-Ananysis, dan Constraint Satisfaction.
Best First Search (Pencarian terbaik pertama)
Metode ini merupakan metode pencarian yang diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata milik heuristic yang lebih buruk.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’(n) = g(n) + h’(n)
dimana
f’ = Fungsi evaluasi
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke goal state
f’ = Fungsi evaluasi
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke goal state
Problem Reduction
Merupakan metode yang kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita
akan dapat menemukan tujuan lebih cepat.
Means-End-Anlysis
Merupakan strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver). Proses pencarian pada metode ini berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward. Metode ini memiliki fungsi meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.
Constraint Satisfaction
Sumber
http://hendrik.staff.gunadarma.ac.id/Downloads/files/23065/teknik-pencarian-heuristik.pdf
akan dapat menemukan tujuan lebih cepat.
Means-End-Anlysis
Merupakan strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver). Proses pencarian pada metode ini berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward. Metode ini memiliki fungsi meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.
Constraint Satisfaction
Sumber
http://hendrik.staff.gunadarma.ac.id/Downloads/files/23065/teknik-pencarian-heuristik.pdf
Tidak ada komentar:
Posting Komentar