Metode Pencarian Buta (Blind Search) dan Pencarian Heuristik

1. Metode Pencarian Buta (Blind Search)

  • Breadth First Search

       Merupakan pencarian yang dilakukan dengan mengunjungi tiap tiap node secara sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan tujuan (goal state) nya.
          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.
          Pengimplementasian Breath First Search dapat ditelusuri dengan menggunakan daftar list open dan closed, untuk menelusuri gerakan pencarian di dalam ruang keadaan. Pada 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.
          Algoritma Pencarian Melebar (BFS) :
  1. Kunjungi simpul V.
  2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu.
  3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.
  4. Jika graf berbentuk pohor berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum mengunjungi simpul-simpul pada aras d + 1.
Contoh :
         Misalkan traversal dimulai dari simpul 1.

         Gambar (a) BFS(1) : 1, 2, 3, 4, 5, 6, 7, 8
         Gambar (b) BFS(1) : 1, 2, 3, 4, 5, 6, 7, 8
         Gambar (c) BFS(1) : 1, 2, 3, 4, 5, 6, 7, 8, 9

  • Depth First Search

         Pada Depth First Search, proses pencarian akan di laksanakan pada semua anaknya sebelum di lakukan pencarian ke node-node yag selevel. pencarian di mulai dari node akar ke level yang lebih tinggi. Proses ini di ulangi terus hingga di temukannya solusi.
         Algoritma Depth First Search yaitu sebagai berikut :
  1. Kunjungi simpul v.
  2. Kunjungi simpul w yang bertetangga dengan simpul v.
  3. Ulangi DFS mulai dari simpul w.
  4. Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.
  5. Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi.
Contoh : 
Misalkan traversal di mulai dari simpul 1.
         Gambar (a) DFS(1) : 1, 2, 4, 8, 5, 6, 3, 7
         Gambar (b) DFS(1) : 1, 2, 3, 6, 8, 4, 5, 7
         Gambar (c) DFS(1) : 1, 2, 5, 8, 9, 6, 3, 7, 4

2. Metode Pencarian Heuristik

  • Generated & Test

         Algoritma Generate and Test merupakan algoritma paling sederhana dalam Teknik pencarian heuristik. Dalam Generate and Test, terdapat dua prosedur penting yaitu generate (membangkitkan) yaitu membangkitkan semua solusi yang mungkin dan test (pengetesan) yaitu menguji solusi yang dibangkitkan tersebut. Algoritma Generate and Test menggabungkan algoritma DFS dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju state awal.
         Algoritma Generate and Test adalah sebagai berikut :
  1. Bangkitkan sebuah solusi yang mungkin
  2. Menguji tiap-tiap node yang merupakan solusi dengan cara membandingkan node tersebut dengan node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
  3. Jika solusi telah ditemukan, maka keluar dari sistem. Jika belum menemukan solusi, maka kembali ke langkah 1.
Contoh : 

         Seorang salesman ingin mengunjungi sejumlah kota. Akan dicari rute terpendek di mana setiap kota hanya boleh dikunjungi tepat & kali. Jarak antara tiap-tiap kota sudah diketahui. misalkan ada kota dengan jarak antara tiap-tiap kota seperti terlihat pada gambar berikut :

Penyelesaian :
         Penyelesaian dengan menggunakan Generate abd Test 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.

  • Hill Climbing

         Metode ini hampir sama dengan metode Generate and Test, 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.

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


 Referensi : 
LINK REFERENSI 1
LINK REFERENSI 2
LINK REFERENSI 3 (DOWNLOAD PDF)
LINK REFERENSI 4

Komentar

Posting Komentar