Metode Pencarian dan Pelacakan 2 (Heuristik)
NAMA : Dewi Laras Wijayanti
NPM : 12114876
KELAS : 3KA10
MATA KULIAH : Peng.Teknologi Sistem Cerdas
Metode Pencarian Heuristic
Heuristic
Search merupakan metode pencarian yang
memperhatikan nilai heuristic (nilai perkiraan). Teknik pencarian heuristic (heuristic
searching) merupakan suatu strategi untuk melakukan proses pencarian ruang
keadaan (state space) suatu problema secara selektif, yang memandu
proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan
sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses
pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness)
Heuristic
Search memperkirakan jarak menuju Goal (yang
disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching:
– Generate and Test.
– Hill Climbing.
– Best First Search.
– Means-EndAnlysis, Constraint Satisfaction, dll.
Dan disini saya akan membahas Metode
Pencarian dan Pelacakan (Heuristik) antara lain :
5.1 Best First Search
Metode ini
adalah kombinasi dari metode depth-search first dan metode breadth-search first
dengan mengambil kelebihan keduanya. Ketika pada hill climbing tidak
diperkenankan untuk kembali ke node sebelumnya, pada metode ini diijinkan jika
ternyata node yang lebih tinggi memiliki nilai heuristik 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
Contoh: Misalkan kita memiliki ruang
pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T
merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode 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.
5.2 Problem Reduction Dalam Teknik
Pencarian Heuristik
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.
Secara intuitif,
masalah A ke B direduksi masalah jika solusi ke B ada dan memberikan solusi ke
A setiap kali A memiliki solusi. Jadi, pemecahan A tidak bisa lebih sulit
daripada memecahkan B. Kita menulis A ≤ m B, biasanya dengan subskrip
pada ≤ untuk menunjukkan jenis pengurangan yang digunakan (m: pengurangan
pemetaan, p: reduksi polinomial).
5.3 Constranint 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
- Binary
CSP biner : setiap constraint merelasikan dua variabel
- Graf Constraint : node adalah variabel, arc adalah constraint
5.4 Means End Analysis
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.
DAFTAR PUSTAKA
Komentar
Posting Komentar