Rabu, 06 Desember 2017

Metode pencarian Buta (Blind Search) dan metode pencarian Heuristik.

Metode pencarian Buta (Blind Search) dan metode pencarian Heuristik.


1.Metode Pencarian Buta(Blind Search).  

merupakan pencarian asal. Jika solusi sudah ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi]. Blind search tidak mempunyai atribut atau informasi tambahan. Algoritma yang termasuk Blind search yaitu:

A.Pencarian Melebar Pertama (Breadth-First Search)

Pada metode pencarian ini, 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 ke level selanjutnya hingga solusi ditemukan
contoh:


 • Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama

B.Pencarian mendalam pertama (Depth-First Search)

 Proses pencarian dilakukan pada semua anaknya sebelum dilakukan           pencarian ke node-node yang selevel
 contoh:

• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak  lagi


2.metode pencarian Heuristik.

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:

A.PEMBANGKITAN dan PENGUJIAN (Generate and Test).

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang 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:

 “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



B.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:

Tidak ada komentar:

Posting Komentar