HEURISTIC SEARCH
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.
–
Means-EndAnlysis, Constraint Satisfaction, dll.
PENDAKIAN BUKIT (Hill Climbing)
§
Metode ini hampir sama dengan metode pembangkitan dan
pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi
heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari
prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan
seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya
yang mungkin.
§
PENCARIAN TERBAIK PERTAMA (Best-First
Search)
§
Metode ini merupakan kombinasi dari metode depthfirst
search dan breadth-first search. Pada metode best-first search, pencarian
diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika
ternyata node pada level yang lebih tinggi ternyata memiliki nilai 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)
§
f’ = Fungsi evaluasi
§
g = cost dari initial state ke current state
§
h’ = prakiraan cost dari current state ke goal state
§
Constraint Satisfaction
§
Problem search standard :
– state adalah "black box“
– setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan
tes goal.
§
CSP:
– state didefinisikan sebagai variabel Xi dengan nilai
dari domain Di – Tes goal adalah sekumpulan constraint yang menspesifikasikan
kombinasi dari nilai subset variabel.
§
Contoh sederhana adalah bahasa representasi formal.
0 komentar:
Posting Komentar