METODE PENCARIAN

Blind Search adalah pencarian solusi tanpa adanya informasi yang dapat mengarahkan pencarian untuk mencapai goal state dari current state (keadaan sekarang). Informasi yang ada hanyalah definisi goal state itu sendiri, sehingga algoritma dapat mengenali goal state bila menjumpainya. Dengan ketiadaan informasi, maka blind search dalam kerjanya memeriksa/mengembangkan node-node secara tidak terarah dan kurang efisien untuk kebanyakan kasus karena banyaknya node yang dikembangkan. Dikatakan “blind” atau “buta” karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Blind Search meliputi :

a. Breadth First Search (BFS)

Breadth First Search (BFS) merupakan metode pencarian yang bertujuan untuk memperluas dan memeriksa semua simpul pada graph atau urutan kombinasi dengan pencarian secara sistematis melalui setiap solusi. BFS melakukan pencarian secara mendalam pada keseluruhan graph atau urutan tanpa memperhatikan tujuan sehingga menemukan tujuan tersebut. BFS tidak menggunakan algoritma heuristik.

Karakteristik Breadth First Search :

1. Jika ada solusi, BFS akan menemukannya.

2. BFS akan menemukan solusi dengan jalur terpendek.

3. BFS tidak akan terjebak dalam “looping”.

4. BFS membutuhkan space untuk menyimpan node list antrian dan space yang dibutuhkan dan

mungkin space yang dibutuhkan itu cukup besar.

Asumsi :

1. Ada solusi dalam pohon

2. Pencarian tree adalah secara terurut.

BFS melakukan searching pada semua node yang berada pada level yang sama terlebih dahulu, sebelum melanjutkan proses searching pada node di level berikutnya.

Keterangan :

1. Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu

sebelum mengunjungi node-node pada level n+1.

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

Keuntungan Breadth First Search :

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 Breadth First Search :

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

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

BFS for Maze

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.

b. Depth First Search (DFS)

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi.

Kelebihan Depth-first search :

1. Pemakaian memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua

node yang pernah dibangkitkan.

2. Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan

menemukannya secara cepat.

Kelemahan Depth-first search :

1. Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada

jaminan untuk menemukan solusi (Tidak Complete).

2. Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda,

Contoh penerapan Depth-first search :

Studi Kasus : Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.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:

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.

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:

1. Generate and Test.

2. HillClimbing.

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

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan

tertentu dari keadaan awal).

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

3. 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 setiap kota hanya boleh dikunjungi tepat 1 kali. 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 Hill Climbing:

Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator

baru yang akan diaplikasikan pada keadaan sekarang:

1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan

keadaan yang baru.

2. Evaluasi keadaan baru tersebut :

3. Jika keadaan baru merupakan tujuan, keluar

4. Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan

keadaan baru tersebut menjadi keadaan sekarang.

5. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Pada simple hill climbing, ada 3 masalah yang mungkin:

a. Algoritma akan berhenti kalau mencapai nilai optimum local

b. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi

c. 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:
http://anasdharmawan.blogspot.co.id/2016/11/blind-search_3.html
http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html