Langsung ke konten utama

Metode Pencarian Buta dan Heuristik

Pencarian Buta

Merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya.

Algoritma Breadth-First Search

  • Traversal akan dilakukan dalan suatu graf, misalnya dimulai dari simpul v. 
  • Kunjungi simpul v, bila simpul yang dicari ditemukan, maka pencarian selesai dan kembalikan hasil.
  • Bila tidak ditemukan, kunjungi semua simpul yang bertetangga dengan v, bila tidak ditemukan, cari lagi di simpul yang belum dikunjungi yang bertetangga dari simpul yang dikunjungi tadi. Begitu seterusnya sampai pencarian selesai (pencarian berhasil atau tidak ditemukan).

Contoh Penerapan BFS

  • Pencarian Jalur Terpendek dalam Permainan Maze
 
Game maze adalah game yang mengharuskan user untuk menemukan jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute hasil pencarian dituliskan dalam bentuk angka disetiap kotak

Algoritma Depth-First Search

  • Masukkan simpul ujung (akar) ke dalam tumpukan
  • Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
  • Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
  • Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan
  • Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
  • Ulangi pencarian dari langkah kedua

Contoh Penerapan DFS

  • Permainan Pairs
Algoritma DFS dapat digunakan untuk mencari solusi pada permainan Pairs. Penggunaan algoritma ini terlihat pada pencarian pasangan dari kartu sampai seluruh kartu telah diperiksa kesamaannya, kemudian baru dilanjutkan dengan kartu berikutnya.


Pencarian Heuristik

Merupakan pencarian bersyarat (terbimbing). Artinya, solusi yang diperoleh adalah solusi yang terbaik, bukan solusi sekali ketemu. Bagian-bagiannya adalah [masalah]-[pencarian]-[syarat]-[solusi]. Misal contoh masalah pada kasus di atas, Ambillah kelereng merah yang tidak pecah dan tidak lonjong. Sehingga ketika ketemu kelereng merah dan ada pecahnya, itu masih bukan solusi karena tidak sesuai dengan syarat (tidak pecah dan tidak lonjong).

Generate and Test

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (Backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma :
  • Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
  • Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
  • Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
Contoh
  • Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini 
Penyelesaian dengan Metode Generate and Test





 

 

Hill Climbing

Metode ini hampir sama dengan metode generate and test, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.

Algoritma
  • Cari operator yang belum pernah digunakan, gunakan operator tersebut untuk mendapatkan keadaan yang baru.
  • Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang :
  • Cari operator yang belum digunakan, gunakan operator tersebut untuk mendapatkan keadaan yang baru.
  • Evaluasi keadaan baru tersebut :
  1. Jika keadaan baru merupakan tujuan, keluar.
  2. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
  3. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
  • Pada simple hill climbing, ada 3 masalah yang mungkin :
  1. Algoritma akan berhenti kalau mencapai nilai optimum local.
  2. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi.
  3. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh "TSP dengan Simple Hill Climbing"
  • Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak (n! / 2! (n-2)!) atau sebanyak 6 kombinasi.
  • Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.

Sumber

  • http://www.metode-algoritma.com/2016/01/breadth-first-search-bfs-swift-java.html
  • http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
  • Madanella, E.D.M., “Analisis Penggunaan Algoritma Pencarian Melebar (BFS) dan Algoritma Pencarian Mendalam (DFS) dalam Teori Graf”.
  • http://hendrik.staff.gunadarma.ac.id/Downloads/files/23065/teknik-pencarian-heuristik.pdf
  • http://www.charisfauzan.net/2015/01/pencarian-buta-teori-dan-implementasi.html 
  • informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006.../MakalahSTMIK2007-115.pdf

Komentar

Postingan populer dari blog ini

Data Science vs Big Data vs Data Analytics

Data Science Tahun 2012 yang lalu, Harvard Business Review menyebut profesi data scientist sebagai profesi terseksi abad 21. Bagaimana tidak? Seorang data scientist memiliki kemampuan mengolah data dengan volume yang sangat besar dalam sehari. Ia juga dituntut untuk mempunyai tingkat kreativitas yang tinggi untuk mengomunikasikan hasil olahan data. Kemampuan ini sangatlah jarang ditemukan. Inilah yang membuat profesi ini terlihat keren, dan konon memberi pundi-pundi penghasilan yang tidak sedikit. Seorang data scientist dituntut untuk menguasai sejumlah disiplin ilmu: ilmu statistik untuk mengolah data, pemrograman sebagai pendukung pengolahan data dalam jumlah besar, ekonomi (atau bidang ilmu lain tergantung pada bidang perusahaan atau organisasi) dalam menganalisis dan mendapatkan insight dari hasil olahan data, serta kemampuan untuk menceritakan (story telling) data yang telah dianalisis. Big Data Big Data adalah istilah yang menggambarkan volume data yang besar, baik d

Perbandingan Framework COBIT, ITIL, dan Six Sigma

ITSM ITSM (Information Technology Service Management, Manajemen Layanan Teknologi Informasi) adalah suatu metode pengelolaan sistem teknologi informasi (TI) yang secara filosofis terpusat pada perspektif konsumen layanan TI terhadap bisnis perusahaan. Beberapa contoh kerangka kerja yang menerapkan ITSM adalah COBIT, ITIL, dan Six Sigma. Framework COBIT (Control Objectives for Information and Related Technology) Konsep kerangka kerja COBIT dapat dilihat dari tiga sudut pandang, meliputi : Information Criteria, IT Resources, IT Processes, seperti terlihat pada gambar dibawah ini : Model proses COBIT terdapat empat domain yang didalamnya terdapat 34  proses dalam memberikan informasi kepada dunia usaha sesuai dengan bisnis dan kebutuhan tata kelola teknologi informasi. Sehingga domain tersebut dapat diidentifikasikan yang terdiri dari 34 proses, yaitu (ITGI, 2007) : Domain Plain and Organize (PO) Yaitu mencakup masalah mengidentifikasikan cara terbaik TI untuk membe