5.1 Best First Search
Best First Search (BFS)
merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari
pencarian Breadth First Search dan Depth First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node
dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang
kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan
penggantinya. Fungsi Heuristik yang digunakan merupakan prakiraan
(estimasi) cost dari initial state ke goal
state, yang dinyatakan dengan :
f’ = g + h’
Dimana
f’ = prakiraan cost dari initial ke goal
g = cost dari initial state ke current
state
h’ = prakiraan cost dari current state ke goal
state
Best first search (BFS) juga merupakan
sebuah metode yang membangkit kan simpul dari simpul sebelumnya. Best
first search memilih simpul baru yang memiliki biaya terkecil
diantara semua leaf nodes (simpul-simpul pada level
terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan
menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n). fungsi
evaluasi best-first search dapat berupa biaya perkiraan dari suatu simpul
menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan
tersebut.
Pada setiap langkah proses pencarian
terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang
memadai pada setiap node/simpul yang kita pilih dengan menggunakan
aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristic
merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu
problema secara selektif, yang memandu proses pencarian yang kita lakukan
sepanjang jalur yang memiliki kemungkinan sukses paling besar.
Ada beberapa istilah yang sering digunakan
pada metode best first search, yaitu :
1. Start node adalah sebuah terminology untuk posisi awal sebuah
pencarian
2. Curret node adalah simpul yang sedang dijalankan dalam algoritma
pencarian jalan terpendek
4. Simpul (node) merupakan representasi dari area pencarian
5. Open list adalah tempat menyimpan data simpul yang mungkin diakses
dari starting node maupun simpul yang sedang dijalankan
6. Closed list adalah tempat menyimpan data simpul yang juga merupakan
bagian dari jalur terpendek yang telah berhasil didapatkan
7. Goal node yaitu simpul tujuan
8. Parent adalah curret node dari suksesor.
5.2 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.
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.
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.
Pada dasarnya sama dengan algoritma Best
First Search, dengan mempertimbangkan adanya arc AND. Gambar berikut
menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu
mencuri atau membeli asal mempunyai uang.Untuk mendeskripsikan algoritma,
digunakan nilai F_UTILITY untuk biaya solusi.
Sebagai contoh, pada Gambar 2.34 Jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.
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
5.5 Means End Analysis ( MEA )
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.
Sumber Refrensi :
Tidak ada komentar:
Posting Komentar