1. Metode Pencarian buta ( Blind Search )
Breadth First Search (BFS)
Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).
Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada. Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).
Keuntungannya :
Kelemahannya :
Depth First Search (DFS)
Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
Keuntungannya :
Kelemahannya :
Contoh Penerapan BFS & DFS
Studi Kasus : 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 : adalah 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
Ruang Keadaan
Keadaan Awal
Tujuan
Metode Penyelesaian :
a. Berikut ini adalah algoritma BFS :
b. Menggunakan algoritma DFS :
Breadth First Search (BFS)
Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).
Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada. Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).
Keuntungannya :
- Tidak menemui jalan buntu.
- Jika ada suatu solusi, maka Breadth-first search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahannya :
- TABLE I. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.
- TABLE II. Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke-(n + 1).
Depth First Search (DFS)
Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
Keuntungannya :
- Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif yang di simpan.
- Secara kebetulan, metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
Kelemahannya :
- Memungkinkan tidak ditemukannya tujuan yang diharapkan.
- Hanya akan mendapatkan satu solusi pada setiap pencarian.
Contoh Penerapan BFS & DFS
Studi Kasus : 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 : adalah 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 :
a. Berikut ini adalah algoritma BFS :
- Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
- Jika Q kosong, tidak ada solusi. Stop.
- Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
- Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
b. 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. Metode Pencarian Heuristik
Generate and Test
Metode ini merupakan pemggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma;
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
- Uji untuk melihat apakah node tersebut benar-benar merupak solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diaharapkan
- 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 rute terpendek dimana setiap kota hanya boleh dikunjungin tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar dibawah ini:
Penyelesaian dengan metode Generate and Test
PENDAKIAN BUKIT (Hill Climbing)
Metode ini hampir sama dengan metode pembangkitan dan pengujian, 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 lainnya yang mungkin.
Algoritma Simple HillClimbing
Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
- 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.
Pada simple hill climbing, ada 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: 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 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
Sumber : https://amandainhere.blogspot.co.id/2016/11/contoh-pencarian-generate-and-test.html
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html
http://azizmusyaffaa.blogspot.co.id/2016/10/breadth-first-search-depth-first-search.html
