BLIND SEARCH

 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.

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