DAFTAR ISI
HALAMAN
JUDUL………………………………………………………….. i
KATA
PENGANTAR…………………………………………………………
ii
DAFTAR
ISI……………………………………………………...................... iii
BAB I
PENDAHULUAN
1.1 Latar
Belakang……………………………………….....................
1
1.2 Rumusan
Masalah………………………………………………… 2
1.3
Tujuan…………………………………………………………….. 2
BAB
II PEMBAHASAN
2.1
Metode Pencarian Best First
Search (BFS)…………....................
3
2.2
Algoritma Best First Search (BFS)………………….................... 4
BAB II I PENUTUP
3.1 Kesimpulan…………………………………………………….... 8
3.2
Saran………………………………………………….................. 8
DAFTAR PUSTAKA
iii
Kata Pengantar
Puji syukur penulis ucapkan kepada
Allah Swt, yang telah memberikan rahmat dan hidayah-Nya.Sehingga bisa
menyelesaikan tugas makalah metode pencarian best first search ini dengan baik
untuk memenuhi tugas kecerdasan buatan.
Akhir kata penulis ucapkan
terimakasih kepada pembaca dan menyadari masih banyak kekurangan dalam makalah
yang singkat dan sederhana ini. Sehingga sangat di butuhkan kritik dan saran
yang mebangun agar dalam penulisan makalah berikutnya dapat lebih baik lagi dan
lebih bermanfaat bagi pembacanya.
penulis
ii
BAB I
PENDAHULUAN
1.1 Latar Belakang
Kemajuan
teknologi tidak hanya menuntut kecepatan penyebaran informasi tetapi juga dalam
bidang ilmu Artificial Intelligence
untuk melakukan
metode pencarian
dan pelacakan yang merupakan suatu hal penting dalam suatu sistem. Karena
pencarian dan pelacakan ini adalah hal yang menentukan keberhasilan sistem
tersebut. sebuah algoritma
pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan
berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut,
yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar
algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Pada
dasarnya, metode pencarian dan pelacakan dibagi dua, yaitu pencarian buta (blind
search) dan pencarian tersusun (heuristic search).
Blind Searchg adalah model pencarian buta atau pencarian yang tidak memiliki informasi awal Blind Searching sendiri dibagi menjadi
tiga macam yaitu : Breadth First
Search, Depth first Search, Uniform
Cost Search.
Heuristic Search merupakan metode pencarian yang memperhatikan nilai
heuristik (nilai perkiraan).
Teknik pencarian heuristik (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 dari Heuristic Searching : Generate
and Test, Hill Climbing, Best First Search, Alpha Beta Prunning, Means-End-Anlysis, Constraint
Satisfaction.
1.2 Perumusan Masalah
Berdasarkan latar belakang diatas, maka ada
beberapa masalah yang akan di bahas dalam makalah ini, yaitu :
1.
Metode pencarian Heuristic
2.
Metode pencarian Best First Search
3.
Algoritma Best First Search
1.3 Tujuan
Adapun tujuan dari penulisan makalah ini, yaitu:
4.
Memahami pengertian Metode pencarian Heuristic
1.
Memahami metode pencarian Best First Search
2.
Memahami
Algoritma Best First Search
BAB II
PEMBAHASAN
2.1 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.
2.2 Metode Pencarian Best First Search
|
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
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
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.
2.3 Algoritma Best
First Search
Algoritma best first search ini merupakan kombinasi dari algoritma depth
first search dengan algoritma breadth first search dengan mengambil
kelebihan dari kedua algoritma tersebut. Apabila pada pencarian dengan
algoritma hill climbing tidak diperbolehkan untuk kembali ke node
pada level yang lebih rendah meskipun node di level yang lebih rendah
tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma
best first search, pencarian diperbolehkan mengunjungi node yang ada di level
yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai
heuristik yang lebih buruk.
Algoritma best first search merupakan
salah satu bagian dari tipe informed search. Algoritma ini menggunakan
nilai-nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai heuristik
terbaik akan dibuka lebih dahulu. Bila goal state belum ditemukan, akan dilakukan
pemeriksaan pada simpul berikutnya dengan nilai heuristik terbaik pada
kedalaman yang sama. Simpul tersebut kemudian dibuka dan diperiksa apakah
terdapat goal state pada cabang-cabangnya. Bila goal state belum
ditemukan, akan dilakukan proses yang sama pada simpul berikutnya.
Merupakan metode yang membangkitkan suksesor
dengan mempertim- bangkan harga (didapat dari fungsi heuristik tertentu) dari
setiap node, bukan dari aturan baku seperti DFS maupun BFS. Gambar 3.4
mengilustrasikan langkah-langkah yang dilakukan oleh algoritma Best First Search. Pertama kali,
dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga
paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah,
yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan
dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil
dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan
dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node
Tujuan.
Gambar 2.1 Langkah-langkah yang dilakukan
oleh 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.
1. OPEN berisi
initial state dan CLOSED masih kosong.
2. 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.
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.
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*
Algoritma A* merupakan algoritma
best first search dengan modifikasian fungsi heuristik, yang akan meminimumkan
total biaya lintasan, dan pada kondisi yang tepat akan memberikan solusi
yang terbaik dalam waktu yang optimal.
Algoritma A juga membutuhkan dua antrian,
yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang memprediksi
keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma untuk
melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini di
sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi
yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih baik jika
fungsi di definisikan sebagai kombinasi atau jumlah dua komponen yaitu g(n) dan
h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari keadaan awal
sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya penerapan
setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju suatu simpul
dan bukan merupakan hasil estimasi.
Fungsi h(n) merupakan pengukur biaya
tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu
diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang
membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya
lintasan.
Secara
matematis,fungsi F sebagai estimasi fungsi evaluasi terhadap node ndapat di tuliskan :
f’(n) = g(n) + h’(n)
Dengan f’(n) = fungsi evaluasi
g(n) = biaya yang
sudah di keluarkan dari keadaan awal sampai
keadaan n
h’(n) = estimasi biaya untuk
sampai pada suatu tujuan mulai dari n
dari fungsi di atas maka ada
beberapa kondisi yang perlu diperhatikan, yaitu:
Jika h = h’, berarti proses
pencarian telah sampai ke tujuan ( goal ).
Jika g = h’ = 0 maka f’ random, artinya system tidak dapat
di kendalikan.
Jika g = k, k adalah konstanta dan
biasanya bernilai 1, h’ = 0, artinya system
menggunakan breadth first
search.
BAB III
PENUTUP
3.1 Kesimpulan
Berdasarlan uraian pembahasan pada
bab sebelumnya dapat ditarik kesimulan
Sebagai
berikut :
1. Metode pencarian heuristik (heuristic searching)
merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state
space) suatu problema secara selektif.
2. 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.
3. Algoritma
best first search ini merupakan
kombinasi dari algoritma depth first
search dengan algoritma breadth
first search dengan mengambil kelebihan dari kedua algoritma
tersebut.
3.2 Saran
dalam bidang Artificial Intelligence dikenal metode pencarian
dan pelacakan. dan yang dibahas dalam makalah ini yaitu metode pencarian best
first search yang merupakan bagian dari pencarian heuristic
DAFTAR
PUSTAKA
diakses 3 Oktober 2015 pukul 12.23
diakses 1 Oktober 2015 pukul 01.14
http://najibzot.blogspot.com/p/teknik-searching-kecerdasan-buatan-di.html
diakses 8 Oktober 2015 pukul 11.31