Metode Pencarian dan Pelacakan 2 (Heuristik)

PENCARIAN TERBAIK PERTAMA (Best-First Search)

Metode ini merupakan 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)

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.

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

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.

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 DAadalah 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.

 Untuk mendeskripsikan algoritma Graph AND-OR kita menggunakan nilai F_UTILITY, yaitu biaya solusi.

Algoritma:

1.    Inisialisasi graph ke node awal.

2.    Kerjakan langkah-langkah di bawah ini hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY:

(a.)      Telusuri graph, mualai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tersebut dan belum pernah diekspansi atau diberi label SOLVED.

(b.)      Ambil satu node dan ekspansi node tersebut. Jika tidak ada successor, maka set F_UTILITY sebagai nilai dari node tersebut. Bila tidak demikian, tambahkan successor-successor dari node tersebut ke graph dan hitung nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’ = 0, tandai node tersebut dengan SOLVED.

(c.)      Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward sepanjang graph. Jika node berisi suatu arc suatu successor yang semua descendant-nya berlabel SOLVED maka tandai node itu dengan SOLVED.

Pada Gambar 2.33, pada langkah-1 semula hanya ada satu node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D.  Node D memiliki biaya yang lebih rendah (6) jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih untuk diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga kita harus memperbaiki nilai f’ dari D menjadi 10. Kembali ke level sebelumnya, node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D. Demikian seterusnya.

Daftar Pustaka : 

http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html

http://ichaajja212.blogspot.co.id/2012/10/heuristic-search-techniques-problem.html