13 0 683 KB
BAB I PENDAHULUAN 1.1
Latar Belakang Permasalahan pencarian adalah merupakan yang sering dijumpai oleh peneliti di bidang Kecerdasan Buatan. Permasalahan ini merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan. Metode pencarian dibagi menjadi 3 bagian, dapat dilihat pada bagan dibawah ini :
Keterangan : 1. Metode Pencarian Buta, merupakan metode sederhana yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk pada bagian ini adalah Breadth First Search, Depth First Search, Hill climbing, Beam Fisrt, dan Best First Search. 2. Metode Penyelesaian Optimal, merupakan metode yang lebih kompleks yang akan mencari jarak terpendek. Metode yang termasuk pada bagian ini
1
adalah British Museum Procedure, Branch and Bound, Dynamic Programming dan A*. Metode-metode ini digunakan pada saat harga perjalanan untuk mencari kemungkinan menjadi perhitungan. 3. Metode Permainan, merupakan metode yang digunakan saat berhadapan dengan musuh. Prosedur ini adalah minimax search, alpha beta pruning. Metode ini banyak digunakan pada program-program permainan seperti catur,dsb. Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state (keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan. Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat. Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif. Secara umum, untuk mendeskripsikan suatu permasalahan dengan baik harus : a. Mendefinisikan suatu ruang keadaan. b. Menerapkan satu atau lebih keadaan awal. c. Menetapkan satu atau lebih tujuan. d. Menetapkan kumpulan aturan. 1.2
Rumusan Masalah Adapun rumusan masalah pada makalah ini, adalah: 1. Apa yang dimaksud dengan Best first search? 2. Apa yang dimaksud dengan Algoritma Best first search?
1.3
Batasan Masalah Adapun batasan masalah yang saya ambil, yaitu mengenai Algoritma Pencarian Best First search Best First Search.
1.4
Tujuan Adapun tujuan dari pembuatan Makalah ini, yaitu: 1. Dapat megetahui pengertian dari Best First Search 2. Dapat mengetahui Algoritma Best First Search
2
BAB II PEMBAHASAN 2.1
Pengertian 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)
3
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 nodenode 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.2
Algoritma Best First Search Merupakan
metode/teknik
search
yang
menggabungkan
kebaikan yang ada dari teknik Depth First Search dan Breadth First Search.
4
Tujuan menggabungkan dua tekhnik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan
memberikan
skala
prioritas
pada
setiap
state
saat
dihasilkan dengan fungsi heuristic. Pencarian diperkenankan mengunjungi node yang ada di level yg lebih rendah jika ternyata node pada level yg lebih tinggi ternyata memiliki nilai heuristik yg buruk. Contoh :
Untuk mengimplementasikan metode ini, dibutuhkan 2 antrian yang berisi node- node, yaitu : 1. OPEN
berisi
simpul-simpul
yang
masih
memiliki
peluang (peluangnya masih terbuka ) untuk terpilih sebagai simpul terbaik. 2. CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik ( peluang untuk terpilih sudah tertutup )
5
Best First Search akan membangkitkan node berikutnya dari semua node yg pernah dibangkitkan. Fungsi Heuristic : -
Suatu
fungsi
memberikan -
heuristic biaya
dikatakan
perkiraan
yang
baik
jika
mendekati
bisa biaya
sebenarnya. Semakin mendekati biaya sebenarnya, fungsi heuristic tersebut semakin baik.
Ada 2 jenis Pencarian Terbaik Pertama ( Best First Search), yaitu : 1. Greedy Best First Search 2. Algoritma A* 2.2.1
Greedy Best First Search Algoritma ini merupakan jenis algoritma Best First Search
yg
paling
sederhana.
Algoritma
ini
hanya
memperhitungkan biaya perkiraan saja, f(n) = h’(n) yang
Karena
hanya
belum
tentu
memperhitungkan kebenarannya,
biaya
maka
perkiraan
algoritma
ini
menjadi tidak optimal Contoh
6
Langkah 1 :
Langkah 2 :
Langkah 3 :
Solusi :
7
Kesimpulan : Dari contoh di atas, Greedy akan menemukan solusi S-BK-G dengan total jarak = 105. Padahal ada solusi lain yg lebih optimal, yakni
: S-A-B-F-K-G dengan total jarak
hanya 95 2.2.2
Algoritma A* Berbeda dg Greedy, algoritma ini akan menghitung fungsi
heuristic
dengan
cara
menambahkan
biaya
sebenarnya dengan biaya perkiraan. Sehingga didapatkan rumus :
g(n)
=
Biaya sebenarnya dari Node Awal ke Node n
h’(n) =
Biaya perkiraan dari Node n ke Node Tujuan
Contoh
8
Langkah 1 :
Langkah 2 :
9
Langkah 3 :
Langkah 4 :
Langkah 5 :
10
Langkah 6 :
Solusi :
BAB III 11
PENUTUP 3.1
Kesimpulan Adapun kesimpulan yang dapat diambil dari makalah ini, yaitu: 1. 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). 2. Algoritma Best-First Search Merupakan metode/teknik search yang menggabungkan kebaikan yang ada dari teknik Depth First Search dan Breadth First Search. 3. Ada 2 jenis Pencarian Terbaik Pertama ( Best First Search), yaitu : 1. Greedy Best First Search 2. Algoritma A*
DAFTAR PUSTAKA
12
Nenk
IecHa,
ARTIFICIAL
INTELLIGENCE
ALGORITMA
PENCARIAN (Searching Algorithm) Diperoleh 21 Oktober 2015 dari https://www.academia.edu/5024807/ARTIFICIAL_INTELLIGENC E_ALGORITMA_PENCARIAN_Searching_Algorithm_ Yusuf usup, Best-First Search Pengertian Best-first Search Best-First Search
Diperoleh
21
Oktober
2015
dari
https://www.academia.edu/4693101/BestFirst_Search_Pengertian_Best-first_Search_Best-First_Search
13