Metode Pencarian (Blind Searching)

Blind Searching

Merupakan pencarian buta, pencarian ini tidak memiliki informasi awal.

Ciri - ciri Blind Search

• Membangkitkan simpul berdasarkan urutan
• Kalau ada solusi, solusi akan ditemukan
• Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui

Blid search di bagi menjadi 2 yaitu :

Pencarian Melebar Pertama (Breadth-First Search)

• Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke kanan
• Kemudian ke level selanjutnya hingga solusi ditemukan

Keuntungan BFS :

• Tidak akan menemui jalan buntu
• Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
• yang paling baik
• Jika ada satu solusi maka bread-first search akan menemukannya

Kelemahannya BFS :

• Membutuhkan memori yang cukup banyak
• Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama (Depth-First Search)

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam. Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.

Kelebihan DFS adalah:

• Pemakain 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 adalah:

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

Sumber :

http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html

https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/