Best First Search Makalah [PDF]

Citation preview

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