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.
5.1 Best First Search
Metode ini adalah
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)
dimana:
- f’ = Fungsi evaluasi
- g = cost dari initial state ke current state
- h’ = prakiraan cost dari current state ke goal state
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 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.
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:
Tidak ada komentar:
Posting Komentar