並行搜尋演算法

搜尋是計算機科學中的基本操作之一。它用於所有需要查詢元素是否在給定列表中的應用程式。在本章中，我們將討論以下搜尋演算法：

• 分治法
• 深度優先搜尋
• 廣度優先搜尋
• 最佳優先搜尋

分治法

在分治法中，問題被分解成幾個較小的子問題。然後遞迴地解決這些子問題，並將其組合起來以獲得原始問題的解決方案。

分治法在每個級別涉及以下步驟：

• 分解 - 將原始問題分解成子問題。

• 解決 - 遞迴地解決子問題。

• 合併 - 將子問題的解決方案組合起來以獲得原始問題的解決方案。

二分查詢是分治演算法的一個例子。

虛擬碼

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