并行搜索算法

搜索是计算机科学的基本操作之一。 它用于我们需要查找元素是否在给定列表中的所有应用程序。 在本章中，我们将讨论以下搜索算法 −

• 分而治之
• 深度优先搜索
• 广度优先搜索
• 最佳优先搜索

分而治之

在分而治之的方法中，问题被分为几个小子问题。 然后对子问题进行递归求解并合并得到原问题的解。

分而治之的方法在每个级别都涉及以下步骤 −

• 分解 − 原问题被分解为子问题。

• 求解 − 子问题递归求解。

• 合并 − 将子问题的解组合起来得到原问题的解。

二分查找是分而治之算法的一个例子。

伪代码

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)

深度优先搜索

深度优先搜索(或 DFS)是一种用于搜索树或无向图数据结构的算法。 这里的概念是从称为根的起始节点开始，并在同一分支中尽可能远地遍历。 如果我们得到一个没有后继节点的节点，我们返回并继续尚未访问的顶点。

深度优先搜索的步骤

• 考虑一个先前未访问过的节点(根)并将其标记为已访问。

• 访问第一个相邻的后继节点并将其标记为已访问。

• 如果所考虑的节点的所有后继节点都已被访问或者没有更多的后继节点，则返回其父节点。

伪代码

令v为图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()

广度优先搜索

广度优先搜索(或 BFS)是一种用于搜索树或无向图数据结构的算法。 这里，我们从一个节点开始，然后访问同一层中的所有相邻节点，然后移动到下一层中的相邻后继节点。 这也称为逐级搜索。

广度优先搜索的步骤

• 从根节点开始，将其标记为已访问。
• 由于根节点没有同级节点，因此进入下一级。
• 访问所有相邻节点并将其标记为已访问。
• 进入下一层并访问所有未访问过的相邻节点。
• 继续此过程，直到访问完所有节点。

伪代码

令v为图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()

最佳优先搜索

最佳优先搜索是一种遍历图以以最短可能路径到达目标的算法。 与 BFS 和 DFS 不同，最佳优先搜索遵循评估函数来确定接下来最适合遍历哪个节点。

最佳优先搜索的步骤

• 从根节点开始，将其标记为已访问。
• 找到下一个适当的节点并将其标记为已访问。
• 转到下一个级别并找到适当的节点并将其标记为已访问。
• 继续此过程，直至达到目标。

伪代码

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