並列検索アルゴリズム

検索は、コンピュータサイエンスの基本的な操作の1つです。これは、要素が指定されたリストにあるかどうかを確認する必要があるすべてのアプリケーションで使用されます。この章では、次の検索アルゴリズムについて説明します。

• 分割統治
• 深さ優先探索
• 幅優先探索
• 最良優先探索

分割統治

分割統治法では、問題はいくつかの小さなサブ問題に分割されます。次に、サブ問題が再帰的に解決され、組み合わされて、元の問題の解決策が得られます。

分割統治法には、各レベルで次の手順が含まれます。

• Divide −元の問題はサブ問題に分けられます。

• Conquer −サブ問題は再帰的に解決されます。

• Combine −サブ問題の解決策を組み合わせて、元の問題の解決策を取得します。

二分探索は分割統治アルゴリズムの一例です。

擬似コード

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）は、ツリーまたは無向グラフデータ構造を検索するためのアルゴリズムです。ここでの概念は、と呼ばれる開始ノードから開始することです。root同じブランチで可能な限りトラバースします。後続ノードのないノードを取得した場合は、まだアクセスされていない頂点に戻って続行します。

深さ優先探索のステップ

• 以前にアクセスされていないノード（ルート）を検討し、アクセス済みとしてマークします。

• 最初に隣接する後続ノードにアクセスし、アクセス済みとしてマークします。

• 検討対象のノードのすべての後続ノードがすでにアクセスされている場合、または後続ノードがもうない場合は、その親ノードに戻ります。

擬似コード

しましょう 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）は、ツリーまたは無向グラフデータ構造を検索するためのアルゴリズムです。ここでは、ノードから始めて、同じレベルの隣接するすべてのノードにアクセスし、次のレベルの隣接する後続ノードに移動します。これは、level-by-level search。

幅優先探索のステップ

• ルートノードから開始し、アクセス済みとしてマークします。
• ルートノードには同じレベルのノードがないため、次のレベルに進みます。
• 隣接するすべてのノードにアクセスし、アクセス済みとしてマークします。
• 次のレベルに移動し、未訪問の隣接ノードすべてにアクセスします。
• すべてのノードにアクセスするまで、このプロセスを続けます。

擬似コード

しましょう 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