Friday, November 4, 2016

METODE BLIND SEARCH

TEKNIK PENCARIAN/PENELUSURAN (SEARCHING)

   Pada umumnya manusia mempertimbangkan sejumlah alternatif strategi dalam menyelesaikan suatu problema. Dalam permainan catur misalnya, seorang pemain mempertimbangkan sejumlah kemungkinan tentang langkah-langkah berikutnya, memilih yang terbaik menurut kriteria tertentu seperti kemungkinan respon lawannya. Aspek tingkahlaku cerdas yang mendasari teknik penyelesaian problema seperti dalam permainan catur tersebut dinamakan proses pencarian ruang keadaan (space state search).

     Exhaustive search – adalah proses pencarian terhadap seluruh ruang keadaan serangakaian langkah yang paling dimungkinkan untuk menghasilkan kemenangan. Walaupun metode ini dapat diterapkan pada setiap ruang keadaan, namum ukuran ruang keadaan yang sangat besar membuat pendekatan ini secara praktis tidak dimungkinkan (dalam permainan catur terdapat 10120 keadaan). Bila kasus ini diimplementasikan ke dalam sisten komputer, maka akan membutuhkan memori yang sangat besar, dan waktu pencarian yang sangat lama. Dengan kata lain metode exhaustive search ini tidak efisien dan tidak efektif, sehingga tidak praktis untuk diimplementasikan. Untuk mengatasi kendala tersebut, ada beberapa cara yang dapat dilakukan, diantaranya :

pertama teknik pencarian parsial (Blind Search) dan yang kedua teknik pencarian heuristic (Heuristik Search).

PENCARIAN PARSIAL (BLIND SEARCH)

          1. PENCARIAN MELEBAR PERTAMA (BREADTH-FIRST SEARCH)

     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 (lihat gambar di bawah ini).
Keuntungan :
  1. Tidak akan menemui jalan buntu. 
  2. Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan. 
Kelemahan :
  1. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon. 
  2. Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1). 

          2. PENCARIAN KEDALAM PERTAMA (DEPTH-FIRST SEARCH)


     Pada Depth-First Search, proses pencarian akan dilakukanpada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi (lihat gambar di bawah).
Keuntungan :

  1. Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
  2. Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.


Kelemahan :

  1. Memungkinkan tidak ditemukannya tujuan yang diharapakan.
  2. Hanya akan menemukan 1 solusi pada setiap pencarian.



IMLEMENTASI BREADTH FIRST SEARCH PADA JAVA

      Untuk mengimplementasikan java pada BFS, saya menukil kodingannya Mark Watson dalam buku beliau Programming AI with Java. Beliau memberikan dua contoh penerapan BFS untuk pencarian jalur terpendek.

  1. Pencarian jalur terpendek pada game Maze
  2. Pencarian jalur terpendek pada simpul Graph

Pencarian Jalur terpendek pada game Maze :


        Game maze adalah game yang mengharuskan user untuk menemukan jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute hasil pencarian dituliskan dalam bentuk angka disetiap kotak.


Pencarian Jalur Terpendek pada Graph


     Titik awal adalah simpul 0 dan titik akhir adalah simpul 9, program secara otomatis akan mencari jalur terpendek dari simpul 0 menuju simpul 9 menggunakan metode BFS.


STUDI KASUS :
     Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan srigala.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 :

     Terdapat dua metode penyelesaian yang akan dibahas pada postingan kali ini. Metode pertama adalah metode breadth first search (BFS), dan metode kedua adalah metode Depth First Search (DFS). Berikut ini akan dijelaskan penyelesaian studi kasus diatas dengan kedua metode tersebut.


BFS (Breadth First Search)

  Adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada di dalam pohon. Berikut ini adalah algoritma BFS :

  1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
  2. Jika Q kosong, tidak ada solusi. Stop.
  3. 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.
  4. Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.



GAMBAR BFS :


DFS (Depth First Search)

     Adalah sebuah algoritma pencarian yang digambarkan dengan struktur pohon seperti pada BFS. Penyelesaiannya dilakukan dengan mendalam. Pencarian solusi dilakukan secara menurun sesuai urutan yang ditentukan.


GAMBAR DFS :



No comments:

Post a Comment