并行搜索算法

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

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

分治法

在分治法中，问题被分解成几个较小的子问题。然后递归地解决这些子问题，并将其组合起来以获得原始问题的解决方案。

分治法在每个级别涉及以下步骤：

• 分解 - 将原始问题分解成子问题。

• 解决 - 递归地解决子问题。

• 合并 - 将子问题的解决方案组合起来以获得原始问题的解决方案。

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

伪代码

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