Algoritmo di ricerca parallela

La ricerca è una delle operazioni fondamentali nell'informatica. Viene utilizzato in tutte le applicazioni in cui è necessario verificare se un elemento è nell'elenco fornito o meno. In questo capitolo, discuteremo i seguenti algoritmi di ricerca:

  • Dividere e conquistare
  • Ricerca in profondità
  • Ricerca in ampiezza
  • Migliore prima ricerca

Dividere e conquistare

Nell'approccio divide et impera, il problema è suddiviso in diversi piccoli problemi secondari. Quindi i sottoproblemi vengono risolti ricorsivamente e combinati per ottenere la soluzione del problema originale.

L'approccio divide et impera prevede i seguenti passaggi ad ogni livello:

  • Divide - Il problema originale è suddiviso in sottoproblemi.

  • Conquer - I problemi secondari vengono risolti in modo ricorsivo.

  • Combine - Le soluzioni dei sottoproblemi vengono combinate per ottenere la soluzione del problema originale.

La ricerca binaria è un esempio di algoritmo divide et impera.

Pseudocodice

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)

Ricerca in profondità

Depth-First Search (o DFS) è un algoritmo per la ricerca in un albero o in una struttura di dati del grafico non orientata. In questo caso, il concetto è di iniziare dal nodo di partenza noto comeroote traversa il più possibile nello stesso ramo. Se otteniamo un nodo senza nodo successore, torniamo e continuiamo con il vertice, che deve ancora essere visitato.

Fasi della ricerca in profondità

  • Considera un nodo (root) che non è stato visitato in precedenza e contrassegnalo come visitato.

  • Visita il primo nodo successore adiacente e contrassegnalo come visitato.

  • Se tutti i nodi successori del nodo considerato sono già visitati o non ha più nodi successori, torna al suo nodo padre.

Pseudocodice

Permettere v essere il vertice in cui inizia la ricerca in 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()

Ricerca in ampiezza

Breadth-First Search (o BFS) è un algoritmo per la ricerca in un albero o in una struttura di dati del grafico non orientata. Qui, iniziamo con un nodo e quindi visitiamo tutti i nodi adiacenti nello stesso livello e poi ci spostiamo al nodo successore adiacente nel livello successivo. Questo è anche noto comelevel-by-level search.

Passi della ricerca in larghezza

  • Inizia con il nodo radice, contrassegnalo come visitato.
  • Poiché il nodo radice non ha alcun nodo allo stesso livello, passare al livello successivo.
  • Visita tutti i nodi adiacenti e contrassegnali come visitati.
  • Vai al livello successivo e visita tutti i nodi adiacenti non visitati.
  • Continua questo processo fino a quando tutti i nodi non sono stati visitati.

Pseudocodice

Permettere v essere il vertice in cui inizia la ricerca in 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()

Migliore prima ricerca

Best-First Search è un algoritmo che attraversa un grafico per raggiungere un obiettivo nel percorso più breve possibile. A differenza di BFS e DFS, Best-First Search segue una funzione di valutazione per determinare quale nodo è il più appropriato da attraversare successivamente.

Passaggi della ricerca Best-First

  • Inizia con il nodo radice, contrassegnalo come visitato.
  • Trova il successivo nodo appropriato e contrassegnalo come visitato.
  • Vai al livello successivo e trova il nodo appropriato e contrassegnalo come visitato.
  • Continua questo processo fino a raggiungere l'obiettivo.

Pseudocodice

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