BLIND SEARCH

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)

b) Uniform Cost Search (UCS)

c) Depth First Search (DFS)

d) Depth Limited Search (DLS)

e) Iterative Deepening Search (IDS)

f) Bi-Directional Search (BDS)

Dari ke-enam macam pencarian buta di atas, yang sering dibahas adalah “Breadth First Search (BFS)” dan “Depth First Search (DFS)”.

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 :

· Jika ada solusi, BFS akan menemukannya.

· BFS akan menemukan solusi dengan jalur terpendek.

· BFS tidak akan terjebak dalam “looping”.

· 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 :

· Tidak akan menemui jalan buntu

· 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 :

· Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon

· 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 :

· Pemakaian memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.

· Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan Depth-first search :

· Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

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

maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

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 :

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

b. Menggunakan algoritma DFS :

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.