Kamis, 03 November 2016

Metode pencarian

Pengertian Breadth-First Search

Algoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras ddikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerlukan sebuah antrian 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 telah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. Urutan proses searching BFS ditunjukkan dalam Gambar 1.1 adalah: A,B,C,D,E,F, ...

Gambar 1.1 : Diagram pohon dari BFS.

Cara Kerja Algoritma BFS

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

1.   Masukkan simpul ujung (akar) ke dalam antrian.
2.   Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.
3.   Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4.   Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
5.   Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.
6.   Ulangi pencarian dari langkah kedua.
Contohnya terlihat dibawah ini:



Maka penyelesaiannya adalah:Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9
Penerapan BFS dalam Algoritma

Adapun penerapan BFS pada algoritma adalah sebagai berikut:








Keuntungan dan Kelemahan BFS

Keuntungan dari BFS adalah :

*        Tidak akan menemukan jalan buntu.

*        Tidak ada satu solusi, maka BFS search akan menemuknnya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan dari BFS adalah :

*        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 kasus BFS
Berikut adalah contoh kasus dengan menggunakan metode BFS. Kita akan mencari jalur tujuan dengan menggunakan angkutan umum.Contoh :
Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan
*        Initial State : Senen

*        Goal State : Kp. Rambutan

RUTE PERJALANAN





Gambar 1.2 : Rute perjalanan

Penjelasan Gambar :
1.      Membangkitakan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2.      Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen
Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus            
Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.            
Terminal Pulo Gadung = Terminal bekasi            
Terminal Manggarai = Terminal Cililitan, Terminal Harmoni
3.      Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

Kesimpulan
Dari pembahasan diatas dapat ditarik kesimpulan yaitu :

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki tetangga yang terdekat terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.

 Metode BFS membutuhkan memori yang cukup banyak namun dengan menggunakan metode ini solusinya tidak akan menemukan jalan buntu.

Pengertian Depth-First Search
Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya.
Berikut gambar yang mengiilustrasikan urutan simpul yang dikunjungi pada algoritma DFS:


Gambar Ilustrasi urutan kunjungan simpul pada algoritma DFS

Dari gambar, dapat dilihat bahwa dengan algoritma DFS, setiap anak simpul pertama yang bertetangga dengan simpul akar dikunjungi sampai tingkat terdalamnya lebih dahulu, lalu seluruh simpul pada subpohon tersebut, sebelum simpul lain yang juga bertetangga dengan simpul akar.

2.Algoritma DFS
Berikut ini adalah algoritma Depth-First Search :

procedure DFS(input v:integer)
Mengunjungi seluruh simpul graf dengan algoritma pencarian DFS
Masukan: v adalah simpul awal kunjungan
Keluaran: semua simpulyang dikunjungi ditulis ke layar

Deklarasi
   w : integer
Algoritma:
   write(v)
   dikunjungi[v]¬true
   for tiap simpul w yang bertetangga dengan simpul v do
      if not dikunjungi[w] then
          DFS(w)
      endif
   endfor


3.SKENARIO UJI COBA

Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.
Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).
Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma DFS:
1. Masukkan simpul ujung (akar) ke dalam tumpukan
2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan
5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
6. Ulangi pencarian dari langkah kedua

4. HASIL UJI COBA

Keuntungan Dari Algoritma Depth-First Search
  • Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja.
  • Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan Dari Algoritma Depth-First Search
  • Memungkinkan tidak ditemukannya tujuan yang diharapkan.
  • Hanya akan menemukan satu solusi pada setiap pencarian.


5. KESIMPULAN

Algoritma Depth-First Search bisa digunakan untuk melakukan pencarian rute terpendek. Dengan memperhatikan keuntungan dan kelemahan dari algoritma tersebut, bisa diambil kesimpulan bahwa algoritma ini bisa membantu pencarian rute terpendek, sehingga bisa mendapatkan penyelesaian yang efektif.
Algoritma Depth-First Search akan berhenti melakukan pencarian jika sudah ditemukan tujuan akhir.
SUMBER :


Tidak ada komentar:

Posting Komentar