Algorytm wyszukiwania równoległego

Wyszukiwanie jest jedną z podstawowych operacji w informatyce. Jest używany we wszystkich aplikacjach, w których musimy sprawdzić, czy element znajduje się na podanej liście, czy nie. W tym rozdziale omówimy następujące algorytmy wyszukiwania -

• Dziel i rządź
• Przeszukiwanie w głąb
• Przeszukiwanie wszerz
• Najlepsze pierwsze wyszukiwanie

Dziel i rządź

W podejściu dziel i rządź problem jest podzielony na kilka małych podproblemów. Następnie podproblemy są rozwiązywane rekurencyjnie i łączone w celu uzyskania rozwiązania pierwotnego problemu.

Podejście „dziel i rządź” obejmuje następujące kroki na każdym poziomie:

• Divide - Pierwotny problem jest podzielony na podproblemy.

• Conquer - Podproblemy są rozwiązywane rekurencyjnie.

• Combine - Rozwiązania podproblemów są łączone, aby uzyskać rozwiązanie pierwotnego problemu.

Wyszukiwanie binarne jest przykładem algorytmu dziel i zwyciężaj.

Pseudo kod

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)

Przeszukiwanie w głąb

Przeszukiwanie w głębi (lub DFS) to algorytm przeszukiwania struktury danych w drzewie lub nieukierunkowanym wykresie. Tutaj koncepcja polega na rozpoczęciu od węzła początkowego znanego jakorooti przejść tak daleko, jak to możliwe, w tej samej gałęzi. Jeśli otrzymamy węzeł bez kolejnego węzła, wrócimy i przejdziemy do wierzchołka, który jeszcze nie został odwiedzony.

Kroki wyszukiwania w głąb

• Rozważ węzeł (root), który nie był wcześniej odwiedzany i oznacz go jako odwiedzony.

• Odwiedź pierwszy sąsiedni węzeł i oznacz go jako odwiedzony.

• Jeśli wszystkie kolejne węzły rozważanego węzła są już odwiedzone lub nie ma on już kolejnego węzła, wróć do węzła nadrzędnego.

Pseudo kod

Pozwolić v być wierzchołkiem, w którym rozpoczyna się wyszukiwanie w Graph 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()

Przeszukiwanie wszerz

Breadth-First Search (lub BFS) to algorytm przeszukiwania struktury danych w drzewie lub nieukierunkowanym wykresie. Tutaj zaczynamy od węzła, a następnie odwiedzamy wszystkie sąsiednie węzły na tym samym poziomie, a następnie przechodzimy do sąsiedniego węzła następcy na następnym poziomie. Jest to również znane jakolevel-by-level search.

Kroki przeszukiwania wszerz

• Zacznij od węzła głównego, oznacz go jako odwiedzony.
• Ponieważ węzeł główny nie ma węzła na tym samym poziomie, przejdź do następnego poziomu.
• Odwiedź wszystkie sąsiednie węzły i oznacz je jako odwiedzone.
• Przejdź do następnego poziomu i odwiedź wszystkie nieodwiedzone sąsiednie węzły.
• Kontynuuj ten proces, aż zostaną odwiedzone wszystkie węzły.

Pseudo kod

Pozwolić v być wierzchołkiem, w którym rozpoczyna się wyszukiwanie w Graph 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()

Najlepsze pierwsze wyszukiwanie

Najlepsze pierwsze wyszukiwanie to algorytm, który przechodzi przez wykres, aby dotrzeć do celu na możliwie najkrótszej ścieżce. W przeciwieństwie do BFS i DFS, Best-First Search stosuje funkcję oceny w celu określenia, który węzeł jest najbardziej odpowiedni do przejścia dalej.

Kroki wyszukiwania w pierwszej kolejności

• Zacznij od węzła głównego, oznacz go jako odwiedzony.
• Znajdź następny odpowiedni węzeł i oznacz go jako odwiedzony.
• Przejdź do następnego poziomu i znajdź odpowiedni węzeł i oznacz go jako odwiedzony.
• Kontynuuj ten proces, aż cel zostanie osiągnięty.

Pseudo kod

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