Heuristik adalah
sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun
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.
A. Best
First Search
Metode
ini adalah 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 initial
state ke current state
·
h’ = prakiraan cost dari
current state ke goal state
Contoh: 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 merunut nilai untuk setiap node.
Terdapat dua jenis
algoritma Best First Search, yaitu:
·
Greddy Best yang hanya memperhitungkan biaya perkiraan saja.
Greedy Best First Search hanya memperhitungkan biaya perkiraan
(estimated cost) saja, yakni:
f(n) = h(n)
Dimana : h(n)= perkiraan biaya dari simpul n ke goal.
Biaya
yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya
memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma
ini menjadi tidak optimal.
Algoritma greddy best ini
membentuk solusi langkah per langkah (step by step). Pada setiap langkah,
terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah
harus dibuat keputusan yang terbaik dalam menentukan pilihan.
·
A* yang memperhitungkan
gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.
Algoritma ini merupakan
algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greddy
Best First Search. Algoritma ini memperhitungkan biaya dari biaya sebenarnya
ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan
sebagai:
f(n) =
g(n) + h(n)dimana : g(n) = biaya sebenarnya untuk mencapai simpul n,
h(n) =
perkiraan biaya dari simpul n ke goal,
f(n) =
perkiraan total biaya jalur yang melalui simpul n ke goal.
Dengan perhitungan biaya
seperti ini, algoritma A* adalah complete dan optimal.
B. 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 satisfaction problem 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. Nilai 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
satisfactionproblemdalam 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.
C. 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.
Ø 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 variabel
Graf Constraint :
node adalah variabel, arc adalah constraint
D. Means
End Analysis
MEA
adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS
(General Problem Solver). Proses pencariannya 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). Contoh OPERATOR first-order predicate calculus dan operator
tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang
menguranginya. MEA meningkatkan metode pencarian heuristik lain (di
rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata
antara current state dengan goal-nya.
REFERENSI:
Comments
Post a Comment