Metode Pencarian Buta(Blind Search) & Heuristik

     1. Metode Pencarian Buta (Blind Search)
merupakan model pencarian buta atau pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Kalau ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Metode ini dibagi menjadi :

   a. Breadth First Search
- Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya.
- Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.
- Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi.

Contoh BFS :

Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan

- Initial State : Senen

- Goal State : Kp. Rambutan

Penjelasan :

1. Membangkitkan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen
   Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus         
   Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.          
   Terminal Pulo Gadung = Terminal bekasi          
   Terminal Manggarai = Terminal Cililitan, Terminal Harmoni
3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

   b. Depth First Search
- Depth-first Search sering disebut juga pencarian mendalam.
- Pencarian Depth – First Search dilakukan pada suatu simpul dalam setiap level dari yang paling kiri.
- Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori.
- Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
- Jika solusi  ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Contoh DFS :
Pada gambar terdapat Initial dan Goal State.

Penjelasan :

Metode ini akan memulai mencari simpul dari sebelah kiri dahulu, baru setelah itu ke kanan sampai semua simpul sudah mendapatkan goalnya. Disini dari simpul A kemudian ke simpul B,D,E,F,G karena sebelah kiri sudah habis, bisa dihapus atau pada gambar ditutup, maka rute dilanjutkan ke sebelah kanan tree yaitu mulai dari simpul C,H,I,J,K. Maka kita telah menemukan goal dari rute ini yakni simpul K.

   2. Metode Pencarian Heuristik
- merupakan sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengorbankan kelengkapan (complateness).
- Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Metode ini dibagi menjadi :

   a. Generate & Test
Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal.
Algoritma:
1.Bangkitkan suatu kemungkinan solusi(membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
2.Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
3.Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

Contoh Generate &Test :
 “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 dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Penjelasan :
dengan membangkitkan solusi-solusi yang mungkin dengan menyusun kota- kota dalam urutan abjad, yaitu :

• A-B-C-D
• A-B-D-C
• A-C-B-D
• dan seterusnya

 

Dari gambar diatas dapat di jelaskan sebagai berikut :

• Misalkan kita mulai dari node A. Kita pilih sebagai keadaan awal adalah lintasan ABCD dengan panjang lintasan - 19.
• Kemudian kita lakukan backtracking untuk mendapatkan lintasan ABDC dengan panjang lintasan -18.
• Lintasan ini kita bandingkan dengan lintasan ABCD. ternyata ABDC < ABCD, sehingga lintasan terpilih adalah ABDC.
• Kita lakukan lagi backtracking untuk mendapatkan lintasan ACBD (-12), ternyata ACBD < ABCD, maka lintasa terpilih sekarang adalah ACBD.
• Demikian seterusnya hingga di temukan solusi yang sebenarnya.
• Salah satu kelemahan dari metode ini adalah perlunya di bangkitkan semua kemungkinan solusi sehingga membutuhkan waktu yang cukup besar dalam pencariannya.

   b.  Hill Climbing
- Pada metode ini 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 lain yang mungkin.

Algoritma :
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) 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 ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru tersebut :
– Jika keadaan baru merupakan tujuan, keluar
– Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
– Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Hill Climbing dibagi menjadi :
1.     Teknik simple hill climbing
Algoritma akan berhenti kalau mencapai nilai optimum lokal. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. Tidak diijinkan untuk melihat satupun langkah selanjutnya.

2.     Teknik steepest – ascent hill climbing

Hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik.

Contoh Hill Climbing :
Diketahui keadaan awal dan tujuan dari suatu permainan kotak 8 puzzle, sebagai berikut :

Penjelasan :
Jadi kotak puzzle ini diselesaikan dengan cara pengurutan seperti hal nya mendaki, atau bisa disebut secara melingkar. Kotak pertama kita isi nilai yang paling kecil, kemudian sebelahnya mengurut sesuai urutan terkecil dan besar. Begitu seterusnya sampai tercapai goal dengan nilai yang terurut.

Sumber :

http://library.binus.ac.id/eColls/eThesisdoc/Bab2HTML/2007300192IFBab2/page10.html
http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html
https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html