Algoritma Pencarian Paralel

Pencarian adalah salah satu operasi fundamental dalam ilmu komputer. Ini digunakan di semua aplikasi di mana kita perlu menemukan apakah suatu elemen ada dalam daftar yang diberikan atau tidak. Pada bab ini, kita akan membahas algoritma pencarian berikut -

  • Memecah dan menaklukkan
  • Pencarian Kedalaman-Pertama
  • Pencarian Luas-Pertama
  • Pencarian Terbaik-Pertama

Memecah dan menaklukkan

Dalam pendekatan divide and conquer, masalah dibagi menjadi beberapa sub-masalah kecil. Kemudian sub-masalah diselesaikan secara rekursif dan digabungkan untuk mendapatkan solusi dari masalah aslinya.

Pendekatan divide and conquer melibatkan langkah-langkah berikut di setiap level -

  • Divide - Masalah asli dibagi menjadi sub-sub masalah.

  • Conquer - Sub-masalah diselesaikan secara rekursif.

  • Combine - Solusi dari sub masalah digabungkan untuk mendapatkan solusi dari masalah aslinya.

Pencarian biner adalah contoh algoritma divide and conquer.

Pseudocode

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

Pencarian Kedalaman-Pertama

Depth-First Search (atau DFS) adalah algoritma untuk mencari pohon atau struktur data grafik yang tidak diarahkan. Di sini, konsepnya dimulai dari simpul awal yang dikenal sebagairootdan melintasi sejauh mungkin di cabang yang sama. Jika kita mendapatkan simpul tanpa simpul penerus, kita kembali dan melanjutkan dengan simpul, yang belum dikunjungi.

Langkah-Langkah Penelusuran Mendalam-Pertama

  • Pertimbangkan node (root) yang tidak dikunjungi sebelumnya dan tandai sebagai dikunjungi.

  • Kunjungi node penerus pertama yang berdekatan dan tandai sebagai dikunjungi.

  • Jika semua node penerus dari node yang dipertimbangkan sudah dikunjungi atau tidak memiliki node penerus lagi, kembali ke node induknya.

Pseudocode

Membiarkan v menjadi puncak di mana pencarian dimulai pada Grafik G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

Pencarian Luas-Pertama

Breadth-First Search (atau BFS) adalah algoritma untuk mencari pohon atau struktur data grafik yang tidak diarahkan. Di sini, kita mulai dengan sebuah node dan kemudian mengunjungi semua node yang berdekatan di tingkat yang sama dan kemudian pindah ke node penerus yang berdekatan di tingkat berikutnya. Ini juga dikenal sebagailevel-by-level search.

Langkah-langkah Pencarian Luas-Pertama

  • Mulailah dengan simpul akar, tandai itu dikunjungi.
  • Karena node root tidak memiliki node di level yang sama, lanjutkan ke level berikutnya.
  • Kunjungi semua node yang berdekatan dan tandai sebagai dikunjungi.
  • Pergi ke tingkat berikutnya dan kunjungi semua node yang berdekatan yang belum dikunjungi.
  • Lanjutkan proses ini sampai semua node dikunjungi.

Pseudocode

Membiarkan v menjadi puncak di mana pencarian dimulai pada Grafik G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Pencarian Terbaik-Pertama

Best-First Search adalah algoritme yang melintasi grafik untuk mencapai target di jalur yang sesingkat mungkin. Tidak seperti BFS dan DFS, Best-First Search mengikuti fungsi evaluasi untuk menentukan node mana yang paling tepat untuk dilintasi berikutnya.

Langkah-Langkah Pencarian Terbaik-Pertama

  • Mulailah dengan simpul akar, tandai itu dikunjungi.
  • Temukan node yang sesuai berikutnya dan tandai sebagai dikunjungi.
  • Pergi ke tingkat berikutnya dan temukan node yang sesuai dan tandai sebagai dikunjungi.
  • Lanjutkan proses ini hingga target tercapai.

Pseudocode

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure