Algorithme de recherche parallèle

La recherche est l'une des opérations fondamentales de l'informatique. Il est utilisé dans toutes les applications où nous avons besoin de trouver si un élément est dans la liste donnée ou non. Dans ce chapitre, nous aborderons les algorithmes de recherche suivants -

  • Diviser et conquérir
  • Recherche en profondeur d'abord
  • Recherche en largeur d'abord
  • Meilleure première recherche

Diviser et conquérir

Dans l'approche diviser pour conquérir, le problème est divisé en plusieurs petits sous-problèmes. Ensuite, les sous-problèmes sont résolus de manière récursive et combinés pour obtenir la solution du problème d'origine.

L'approche diviser pour conquérir implique les étapes suivantes à chaque niveau -

  • Divide - Le problème d'origine est divisé en sous-problèmes.

  • Conquer - Les sous-problèmes sont résolus de manière récursive.

  • Combine - Les solutions des sous-problèmes sont combinées pour obtenir la solution du problème d'origine.

La recherche binaire est un exemple d'algorithme de division et de conquête.

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)

Recherche en profondeur d'abord

La recherche en profondeur d'abord (ou DFS) est un algorithme de recherche dans un arbre ou une structure de données de graphe non dirigée. Ici, le concept est de partir du nœud de départ connu sous le nom derootet traverser autant que possible dans la même branche. Si nous obtenons un nœud sans nœud successeur, nous retournons et continuons avec le sommet, qui n'a pas encore été visité.

Étapes de la recherche en profondeur d'abord

  • Considérez un nœud (racine) qui n'a pas été visité auparavant et marquez-le comme visité.

  • Visitez le premier nœud successeur adjacent et marquez-le comme visité.

  • Si tous les nœuds successeurs du nœud considéré sont déjà visités ou s'il n'a plus de nœud successeur, retournez à son nœud parent.

Pseudocode

Laisser v être le sommet où la recherche commence dans 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()

Recherche en largeur d'abord

La recherche en largeur d'abord (ou BFS) est un algorithme de recherche dans un arbre ou une structure de données de graphe non orienté. Ici, nous commençons avec un nœud, puis visitons tous les nœuds adjacents du même niveau, puis passons au nœud successeur adjacent au niveau suivant. Ceci est également connu commelevel-by-level search.

Étapes de la recherche en largeur d'abord

  • Commencez par le nœud racine, marquez-le comme visité.
  • Comme le nœud racine n'a pas de nœud au même niveau, passez au niveau suivant.
  • Visitez tous les nœuds adjacents et marquez-les comme visités.
  • Passez au niveau suivant et visitez tous les nœuds adjacents non visités.
  • Continuez ce processus jusqu'à ce que tous les nœuds soient visités.

Pseudocode

Laisser v être le sommet où la recherche commence dans 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()

Meilleure première recherche

Best-First Search est un algorithme qui parcourt un graphique pour atteindre une cible dans le chemin le plus court possible. Contrairement à BFS et DFS, Best-First Search suit une fonction d'évaluation pour déterminer quel nœud est le plus approprié pour traverser ensuite.

Étapes de la meilleure première recherche

  • Commencez par le nœud racine, marquez-le comme visité.
  • Trouvez le prochain nœud approprié et marquez-le comme visité.
  • Passez au niveau suivant et trouvez le nœud approprié et marquez-le comme visité.
  • Continuez ce processus jusqu'à ce que la cible soit atteinte.

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