BLIND SEARCH & HEURISTIC SEARCH
1. BLIND SEARCH
Blind
Search 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.
- Pencarian Melebar Pertama (Breadth - Search First)
Merupakan algoritma
yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder
yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang
bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang
belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi,
demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi
persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan
teori graf.
Dalam algoritma BFS,
simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini
digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan
dikunjungi kemudian sesuai urutan pengantrian. Metode ini memiliki keuntungan
dan kekurangan, yaitu :
Keuntungan
- Tidak akan menemui jalan buntu
- Jika ada satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kekurangan
- Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
- Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).
Contoh Implementasi Breadth - First Search :
- Diketahui sebuah kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar kota dibentuk dengan sebuah graph terlihat dibawah:
- Sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal perjalanan adalah kota no. 1. Gunakan algoritma BFS!
Maka dengan menggunakan algoritma BFS, rute tercepat
yang didapat adalah sebagai berikut :
1
– 2 – 3 – 4 – 5 – 6 – 7 – 8
Rute tersebut didapat dari pencarian secara melebar.
Hal; tersebut dapat dijabarkan sebagai berikut :
- Pertama-tama, pointer menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2)
- Setelah itu, proses dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada tetangga terdekat, yakni no.4 (1-2-3-4)
- Pointer mencari teteangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan masuk ke daun berikutnya, yakni no.5.
- Proses diulang hingga pointer menunjuk angka 8.
- Pencarian Mendalam Pertama (Depth - Search First)
Pencarian dengan
metode Depth First Search (DFS) dilakukan dari node awal
secara mendalam hingga yang paling akhir (dead-end) atau sampai
ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu
dikunjungi. Sebagai ilustrasinya dapat dilihat pada gambar dibawah ini :
Berdasarkan gambar,
proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga
tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka
pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih
ada cabangnya. Begitu seterusnya hingga diperoleh tujuan (goal). Operasi
semacam ini dikenal dengan sebutanbacktracking. Metode ini memiliki keuntungan
dan kekurangan, yaitu :
Keuntungan :
- Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
- Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, sehingga tidak memboros waktu untuk melakukan sejumlah besar keadaan ‘dangkal’ dalam permasalahan graf/pohon.
Kelemahan :
- Memungkinkan tidak ditemukannya tujuan yang diharapkan.
- Hanya akan mendapatkan satu solusi pada setiap pencarian.
Contoh Depth - First Search :
- Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.
Permasalahannya :
- Di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.
Deskripsi :
- P = Petani
- Sy = Sayuran
- K = Kambing
- Sg = Serigala
Ruang Keadaan :
- Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)
Keadaan Awal :
- Daerah Asal = (P, Sy, K, Sg)
- Daerah seberang = (0, 0, 0, 0)
Tujuan :
- Daerah Asal = (0, 0, 0, 0)
- Daerah seberang = (P, Sy, K, Sg)
Metode Penyelesaian :
- Menggunakan algoritma DFS :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
- Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
2. HEURISTIC SEARCH
Heuristic Search adalah
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 & Test
Metode ini merupakan
penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu
bergerak kebelakang menuju pada suatu keadaan awal.
Prosedur :
- 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 : “Travelling Salesman Problem (TSP)”.
- 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 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini :
- Penyelesaian dengan metode Generate and Test
- Hill Climbing
Hill Climbing (mendaki
bukit) merupakan salah satu variasi metode buat dan uji (Generate and Test)
dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan
arah gerak dalam ruang pencarian (search).
Dalam prosedur buat dan
uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedur Hill
Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan
pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur :
- Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
- Evaluasi keadaan baru tersebut :
- Jika keadaan baru merupakan tujuan, keluar
- Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
- Dalam Hill Climbing, memiliki 3 masalah yang mungkin :
- Algoritma akan berhenti kalau mencapai nilai optimum local
- Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi
- Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh : “Travelling Salesman Problem (TSP)”.
- 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 l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak :
- atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi
Daftar Pustaka
