1.
Best
First Search
Best-First Search merupakan
sebuah metode yang membangkitkan 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
3.
Suksesor adalah simpul-simpul
yang yang akan diperiksa setelah current node
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.
Algoritma best-first search
Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah
senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi
belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan
dan sudah dievaluasi. Algoritma selengkapnya adalah sebagai berikut.
·
OPEN berisi initial state dan
CLOSED masih kosong.
·
Ulangi sampai goal ditemukan atau
sampai tidak ada di dalam OPEN
a.
Ambil simpul terbaik yang ada di
OPEN
b.
Jika simpul tersebut sama dengan
goal, maka sukses
c.
Jika tidak, masukkan simpul
tersebut ke dalam CLOSED
d.
Bangkitkan semua aksesor dari
simpul tersebut
e.
Untuk setiap suksesor kerjakan:
·
Jika suksesor tersebut belum
pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat
parent.
·
Jika suksesor tersebut sudah
pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik
daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk
suksesor tersebut dn nodes lain yang berada di level bawahnya.
Algoritma yang
menggunakan metode best-first search, yaitu:
a.
Greedy Best-First
Greedy Best-First adalah algoritma best-first
yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated
cost) saja, yakni f(n) = h(n). Biaya yang sebenarnya
(actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya
perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak
optimal.
b.
A*
A* adalah algoritma best-first search yang
menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan
didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi
matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan
perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.
2.
Problem
Reduction
Problem reduction adalah dasar teknik
pemecahan masalah AI dimana dilakukan dengan cara mengurangi masalah dalam satu
set sub masalah yang lebih mudah pemecahannya. Intinya adalah berusaha
mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah
diselesaikan. Ide utama teknik problem reduction adalah mendekomposisi masalah
ke dalam skala yang lebih kecil.
Problem Reduction dibagi dalam dua metode yaitu :
a)
Graf AND OR Graf AND OR atau tree
merupakan graf yang digunakan untuk memperlihatkan solusi dari permasalahan
yang dapat diselesaikan dengan cara mendekomposisikan masalah tersebut menjadi
sekumpulan masalah yang lebih kecil, dimana semuanya harus dapat diselesaikan.
Pereduksian ini membangkitkan arc(busur) AND. Satu busur AND akan menghasilkan
beberapa nomor dari simpul setelahnya dimana semua simpul harus diselesaikan
supaya pancaran menghasilkan solusi. Hanya saja pada graf OR banyak pancaran
akan muncul dari beberapa node, mengindikasikan beberapa jalan yang dapat
menyelesaikan masalah. Untuk menemukan
solusi dari sebuah graf AND OR kita memerlukan sebuah algoritma yang serupa
dengan algoritma BFS(Best First Search) tetapi dengan kemampuan untuk menangani
pancaran AND dengan tepat. Algoritma ini harus menemukan bagian dari simpul
awal dari graf untuk menghimpun simpul-simpul yang menggambarkan state solusi.
Perlu diketahui bahwa hal ini mungkin
diperlukan untuk mendapatkan lebih dari solusi dalam setiap pancaran AND. Untuk mendeskripsikan algoritma Graph AND-OR
kita menggunakan nilai F_UTILITY, yaitu biaya solusi. Algoritma :
·
Inisialisasi graph ke node awal.
·
Kerjakan langkah-langkah di bawah ini
hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY
Pada
Gambar di atas, 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.
b)
Graf AO*(Algorithm Optimized) Algoritma
AO* menggunakan struktur Graph dimana tiap-tiap node pada graph tersebut akan
memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri
sampai suatu solusi. Algoritma
§ Diketahui
GRAPH yang hanya berisi node awal (sebut
saja node INIT). Hitung h’(INIT).
§ Kerjakan
langkah-langkah di bawah ini hingga INI bertanda SOLVED atau samoai nilai
h’(INIT) menjadi lebih besar daripada F_UTILITY:
o
Ekspand INIT dan ambil salah satu node
yang belum pernah diekspand (sebut NODE).
o
Bangkitkan successor-successor NODE. Jika
tida memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada
successor, maka untuk setiap successor (sebut sebagai SUCC) yang bukan
merupakan ancestor dari NODE
o
Kirimkan informasi baru tersebut ke graph,
dengan cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang
nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya.
Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong.
§ Jika
mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH
yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut:
CURRENT) dan hapus dari S.
§ Hitung
biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama
dengan jumlah h’ untuk tiaptiap node pada akhir arc ditambah dengan biaya arc
itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari
stiap arc yang muncul tadi.
§ Tandai
jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya
minimum.
§ Tandai
CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc
yang baru saja ditandai tadi telah ditandai dengan SOLVED.
§ Jika
CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah,
maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua
ancestor dari CURRENT ke S.
Sebagai contoh, pada Gambar di atas, 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.
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.
·
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
4. 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 :
0 komentar:
Posting Komentar