Heuristikadalahsebuahteknikyang
mengembangkanefisiensidalamprosespencarian, namumdengankemungkinanmengorbankankelengkapan(completeness).Fungsiheuristikdigunakanuntukmengevaluasikeadaan-keadaanproblemaindividual
danmenentukanseberapajauhhaltersebutdapatdigunakanuntukmendapatkansolusiyang
diinginkan.
5.1 Best First Search
Metodeinimerupakankombinasidarimetodedepth-first
searchdanbreadth-first search. Padametodebest-first search,
pencariandiperbolehkanmengunjunginode yang adadilevel yang lebihrendah,
jikaternyatanode padalevel yang lebihtinggiternyata memilikinilaiheuristic yang
lebihburuk.
FungsiHeuristikyang
digunakanmerupakanprakiraan(estimasi) cost dariinitial statekegoal state, yang
dinyatakandengan:
f’(n) = g(n) + h’(n)
dimanaf’= Fungsievaluasi
g = cost dariinitial statekecurrent state
h’= prakiraancost daricurrent stateke goal state
Contoh: Node
M merupakan keadaan awal dan noda 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.
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.
5.2 Problem
Reduction
Dalam teori komputabilitas dan teori kompleksitas komputasi , pengurangan adalah
transformasi dari satu masalah ke
masalah lain. Tergantung pada transformasi yang digunakan ini dapat digunakan
untuk mendefinisikan kelas kompleksitas pada
serangkaian masalah.
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 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.
5.3
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
variabel
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). 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 :
·
lutfiatulm.blogspot.com/2013/03/representasi-pengetahuan.html
Tidak ada komentar:
Posting Komentar