Blind Search : DFS dan BFS

Blind Search merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah.

Depth First Search (DFS) Algoritma DFS pertama kali diperkenalkan oleh Tarjan dan Hopcroft 20 tahun lalu. Mereka menunjukkan bagaimana Depth First Search (DFS) merupakan metode pencarian secara mendalam dan bagian dari blind search atau pencarian buta. Pencarian dimulai dari level paling pertama, kemudian dilanjutkan ke anak paling kiri pada level berikutnya. Demikian seterusnya sampai tidak terdapat anak lagi atau level yang paling dalam. Jika pencarian belum menemukan solusi, maka dilakukan penelusuran kembali ke node sebelumnya dan dilanjutkan ke node tetangga. Proses ini diulangi terus hingga menemukan solusi (Kusumadewi, 2003).
Keuntungan Depth First Search

1. Membutuhkan memori yang relatif kecil, karena hanya node – node pada lintasan yang aktif saja yang disimpan.
2. Secara kebetulan metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan Depth First Search

1. Memungkinkan tidak ditemukannya tujuan yang diharapkan.
2. Hanya akan mendapatkan satu solusi pada setiap pencarian.

Sistem yang dibangun untuk menyelesaikan masalah, menggunakan metode pencarian Depth First Search (DFS). DFS akan mencari keseluruhan kemungkinan rute yang dapat terjadi dari data yang tersedia kemudian hasil dari seluruh pencarian akan dibandingkan untuk mendapatkan hasil yang tercepat atau termurah tergantung kondisi yang diinginkan. Pencarian solusi DFS dicirikan dengan simpul-simpul terdalam terlebih dahulu. Pertama simpul awal dibangkitkan, kemudian simpul pada arah kedua, pada simpul arah ketiga dan seterusnya. Jadi pencarian mengikuti sebuah lintasan tunggal mulai dari simpul awal terus menurun kebawah ke simpul-simpul arah bawahnya. Jika pencarian mencapai level terdalam, maka pencarian dilakukan level sebelumnya.
Berikut adalah cara kerja algoritma DFS pada aplikasi pencarian rute bus kota. Contoh kasus yang dijelaskan dimisalkan yaitu rute bus dari palur ke klewer berdasarkan database.
Pengecekan rute ke klewer , dimulai dari titik awal Palur menuju ke titik selanjutnya yaitu
Panggung, pengguna dapat menggunakan bus Atmo dan Damri dan selanjutnya pada titik
Panggung terdapat 2 cabang titik yaitu St.Balapan dan Ps.Gede, maka pengecekan
dilakukan pada node paling kiri dulu, dikarenakan pada titik St. Balapan tidak
ditemukan data Klewer maka kemudian pengecekan rute dilanjutkan pada node
selanjutnya dan jika ditemukan data lokasi sama dengan data lokasi tujuan maka
pencarian dihentikan.

========================================================================

METODE Algoritma Breadth First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah sebuah teknik umum yang digunakan untuk melakukan traversal pada graf.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungi masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

Berdasarkan penelitian yang dilakukan oleh Kerstin Klockner, Nadine Wirshum, Anthony Jameson pada makalahnya yang berjudul “Depth- and Breadth-First Processing of Search Result” kita dapat menyimpulkan bahwa pengguna cenderung melakukan pencarian secara strictly depth-first strategy. Yaitu melihat suatu link yang paling atas dari hasil pencarian kemudian mengaksesnya dan terus menelusuri link yang terdapat pada document tersebut yang berkaitan dengan kata kunci yang dicari. Sehingga agar pencarian oleh FTP search lebih efektif perlu ada penyesuaian dengan algoritma mesin pencari. Algoritma yang menurut kami paling sesuai adalah algoritma BFS pada mesin pencari yang akan menampilkan daftar file yang paling dekat relefansinya dengan kata kunci.

Metode FTP search melakukan hal yang sama dengan WebCrawler yaitu mengunjungi setiap server, mencatat link file dan memasukkannya ke dalam basis data. Sehingga file yang paling relevan ditempatkan di bagian paling atas daftar hasil pencarian. Perbedaan dengan web crawler ftp search akan mengelompokkan file-file tersebut berdasarkan server.

Kelebihan metode baru ini bagi pengguna FTP search adalah pengguna akan dapat langsung melihat file yang paling relevan pada bagian atas daftar hasil pencarian dan meminimalisasi pengaksesan lintas server.

sumber

https://www.scribd.com/doc/55693337/Artificial-Neural-Network