DEFINISI DAN CONTOH METODE PENCARIAN BUTA DAN HEURISTIK

1. Metode Pencarian Buta (Blind Search) 

Yaitu tidak terdapatnya informasi awal yang digunakan dalam proses pencarian.
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).

Ada dua jenis pencarian buta (blind search) :

a.   Pencarian melebar pertama (Breadth – First Search)

Pada 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 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. Keuntungannya :

• Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang   ada) dan solusi yang ditemukan pasti solusi yang paling baik.
• Jika ada 1 solusi, maka breadth – first search akan menemukannya.
• Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan

Kerugiannya :

• Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah.
• Membutuhkan waktu yang cukup lama

Kesimpulan :

Teknik pencarian Breadth – First Search  ini :

Completeness : Dimana teknik yang digunakan adanya solusi

Optimality : dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda Time complexity : waktu yang dibutuhkan cukup lama Space complexity : memori yang dibutuhkan juga banyak.

Contoh : 

Penjelasan Gambar :

   1. Membangkitakan 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.  Pencarian mendalam pertama (Depth – First Search)

Pada 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.

Keuntungannnya :

• Membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
• Dan secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat (waktunya cepat)

Kerugiannya :

•  Memungkinkan tidak ditemukannya atau tidak adanya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga) tidak complete karena tidak ada jaminan akan menemukan solusi
• Hanya mendapat 1 solusi pada setiap pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik tidak optimal.

    Contoh : 

     Pencarian dimulai dari simpul sebelah kiri yaitu ABD karena D tidak memiliki anak maka

     lanjut ke sebelah kanan yaitu E lalu FG. Anak-anak dari simpul B sudah habis maka lanjut ke simpul C dan di teruskan ke HIJK. K merupakan goal state dari pohon tersebut. Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).

   2. Metode Pencarian Heuristik

      Yaitu terdapatnya informasi awal yang digunakan dalam proses pencarian. Pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, disebabkan karena waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang besar, teknik pencarian buta (blind search) bukan teknik yang baik untuk digunakan karena keterbatasan kecepatan komputer dan memori.

     Dengan adanya teknik heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Fungsi dari teknik heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan. Contoh aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine. Ada empat jenis pencarian terbimbing (heuristic search) :

   a. Pembangkitan dan pengujian (Generate and Test)

     Teknik ini merupakan gabungan dari DFS dan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Dimana nilai pengujian berupa jawaban “ya” atau “tidak”. Algoritmanya :

• Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
• 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
• Jika solusi ditemukan, keluar dan jika tidak, ulangi lagi langkah pertama . Salah satu kelemahan teknik Generate and Test adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya.

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 Generate and Test

   b.  Pendakian Bukit (Hill Climbing)

    Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap kesalahan-kesalahan lainnya yang mungkin. Teknik-teknik pada Hill Climbing :

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.

Prosedur Hill Climbing :

   1. Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.

  2. Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

     3. Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :

    a. Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi,          berhentilah.

    b. Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.

   c. Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.

     d. Kembalilah ke langkah 2.

Masalah-masalah yang mungkin timbul pada prosedur Hill Climbing :

- Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.
- Daratan  (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.
- Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
-  Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.
- Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.

Contoh:

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 :  
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html
 http://choirulkahfi97.blogspot.co.id/2017/12/definsi-dan-contoh-metode-pencarian.html