Pencarian Buta (Blind Search)

Nama : Erlin Novianty

Kelas : 3KA33

NPM : 1C114791

Tugas : Softskill Peng. Teknologi Sistem Cerdas

Dosen : Dewi Andriyani

Pencarian Buta (Blind Search)

Breadth First Search

Definisi 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 BFS :

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 :

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.

Keuntungan BFS :

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

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

Prosedur Breadth First Search merupakan pencarian yang dilakukan dengan mengunjungi tiap – tiap node secara sistematis pada setiap level hingga keadaan tujuan (goal state) ditemukan. Atau dengan kata lain, penelusuran yang dilakukan adalah dengan mengunjungi node – node pada level yang sama hingga ditemukan goal state nya.

Diagram pohon dari BFS

Keterangan :

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.

Contoh Breadth First Search

Diketahui sebuah peta perjalanan dimana ingin mencari rute perjalanan dari kota A ke kota B.

Penyelesaian :

Hasil pencarian menggunakan BFS mendapat solusi di level 3 dan level 4.

Depth First Search

Definisi Depth First Search

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

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

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

Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir n(dead end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi.

Diagram pohon dari DFS