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.
Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
5.1 Best First Search
Metode
ini merupakan kombinasi dari metode depth-first 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)
dimana f’ = Fungsi evaluasi
g = cost dari
ini tial state ke current state
h’ = prakiraan
cost dari current state ke goal state
Contoh :
Misalkan
kita memiliki ruang pencarian seperti pada gambar dibawah. Node M merupakan
keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node
M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke
kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di
node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A
untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan
antara node n dengan node tujuan (jalan buntu). Kita bisa mengurut nilai untuk
setiap node.
5.2 Problem Reduction
Problem
reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi
masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah
diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat
penting dalam penyelesaian constraint satisfactionproblem yang sangat
berat sehingga semua aplikasi komersial penyelesaian constraint
satisfactionproblem menggunakan teknik konsistensi ini sebagai langkah
dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan
efisiensi program pengenalan gambar oleh peneliti di intelejensi semu.
Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar
dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang
memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten
pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai
yang konsisten.Untuk
mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint
satisfaction problem yang sangat sederhana.
Anggap
A < B adalah constraint antara variabel A dengan domainDA
= { 3..7} dan variabel B dengan domain DB = { 1..5}.
dengan jelas tampak bahwa bahwa untuk sebagian nilai pada DA
tidak ada nilai yang konsisten di DB yang memenuhi constraint
A < B dan sebaliknya. Niai yang demikian dapat dibuang dari domain
yang berkaitan tanpa kehilangan solusi apapun. Reduksi itu aman. Didapatkan domain
yang tereduksi DA = {3,4} dan DB = {4,5}.
Perhatikan
bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai
contoh kumpulan label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari
domain, tetapi untuk setiap nilai A dari DA
adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya.
Walaupun
teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi,
teknik konsistensi ini membantu menyelesaikan constraint satisfactionproblem
dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian
maupun pada saat pencarian.
Constraint
sering direpresentasikan dengan gambar graf (gambar 1) di mana setiap verteks
mewakili variabel dan busur antar verteks mewakili constraint binari
yang mengikat variabel-variabel yan dihubungkan dengan busur tersebut. Constraint
unari diwakilkan dengan busur melingkar.
Kebanyakan solusi menggunakan pohonOR,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.
5.3 Constraint Satisfaction
Problem search standard :
– state adalah "black box“
– setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.
– 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.
– 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)}
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
Graf Constraint : node adalah variabel, arc adalah constraint
5.4 Means End 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 :
0 komentar:
Posting Komentar