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