Metode Pencarian dan Pelacaan 2 (Heuristik)

Metode Pencarian dan Pelacaan 2 (Heuristik)

  19.36    unknown

---

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness). Heuristic berfungsi untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic

Ada 4 metode pencarian heuristic

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

Pengurangan Masalah (Problem Reduction)

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.

Menggunakan Graf AND-OR yang pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND.

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.

CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.

Contoh : Pewarnaan Peta 

 

Variabel WA, NT, Q, NSW, V, SA, T

Domain Di = {red,green,blue}
Constraints : daerah yang bertetangga dekat harus memiliki warna yang berbeda.
Contoh WA ≠ NT, atau (WA,NT) {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}

Solusi lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green

Constraint Graf

Binary CSP biner : setiap constraint merelasikan dua variable
Graf Constraint : node adalah variabel, arc adalah constraint

 

MEA (Means-Ends Analysis)

MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963]. Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward. Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu. Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika tindakan operator dapat dipenetrasi. 

Contoh OPERATOR first-order predicate calculus dan operator2 tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang menguranginya. Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA di atas strategi pencarian Brute-Force. Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

Sumber :
https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/
https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/
https://www.academia.edu/4865567/Teknik_Pencarian_Heuristik_1_25_Pengantar_Kecerdasan_Buatan_AK045218_Generate_and_Test_Hill_Climbing_Best_First_Search_Problem_Reduction_Constraint_Satisfaction_Means_End_Analysis?auto=download
http://rahmaanisa96.blogspot.co.id/2016/11/5-metode-pencarian-dan-pelacakan-2.html