BLIND AND HEURISTIK SEARCH

Teknik Pencarian / Perancangan

Teknik Pencarian / Pelacakan

Teknik pencarian adalah suatu teknik atau cara yang dilakukan untuk mencari solusi dari suatu permasalahan dengan sekumpulan kemungkinan yang ada. Empat kriteria yang dapat  digunakan untuk mengukur perfomansi teknik pencarian :

1.    Completeness artinya apakah teknik yang digunakan akanmenjamin penemuan solusi jika solusinya memang ada

2.    Time complexity artinya berapa lama waktu yang diperlukan

3.    Space complexity artinya berapa banyak memori yang diperlukan

4.    Optimality artinya apakah teknik yang digunakan akan menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda

Teknik pencarian ada dua jenis, yaitu :

A.    Pencarian buta (blind search) yaitu tidak terdapatnya informasi awal yang digunakan dalam proses pencarian. Ada dua jenis pencarian buta (blind search) :

1.   Pencarian melebar pertama (Breadth – First Search)

Pada Breadth – First Search semua node pada level 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.

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

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

Pencarian terbimbing (heuristic search) 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) :

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

Kasus 4 puzzle (kotak permainan)

b. Kasus 8 puzzle (kotak permainan)

c. Kasus Travelling Salesman Problem (TSP)

2.   Pendakian Bukit (Hill Climbing)

Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsiheuristic. 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 nilaiheuristic terbaik.

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

1.  Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.

2.  Jika Q kosong, tidak ada solusi. Stop.

3.  Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2

4.  .Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.

• GAMBAR DFS :

sumber:

 http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html

http://hanz-kampus.blogspot.co.id/2010/02/heuristic-search-kecerdasan-buatan.html