Parallel-algorithm-parallel-search-algorithm

並列検索アルゴリズム

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

• 分割統治
• 深さ優先検索
• 幅優先検索
• ベストファースト検索

分割統治

分割統治アプローチでは、問題はいくつかの小さなサブ問題に分割されます。 次に、副問題が再帰的に解決され、元の問題の解決策を得るために結合されます。

分割統治アプローチには、各レベルで次の手順が含まれます-

• 分割-元の問題はサブ問題に分割されます。
• 征服-副問題は再帰的に解決されます。
• 結合-サブ問題の解決策を組み合わせて、元の問題の解決策を取得します。

バイナリ検索は、分割統治アルゴリズムの例です。

疑似コード

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 と呼ばれる開始ノードから開始し、同じブランチ内で可能な限りトラバースすることです。 後続ノードのないノードを取得した場合、まだアクセスされていない頂点に戻って続行します。

深さ優先検索の手順

• 以前にアクセスされていないノード（ルート）を検討し、アクセス済みとしてマークします。
• 最初の隣接する後続ノードにアクセスし、訪問済みとしてマークします。
• 考慮されたノードのすべての後続ノードが既にアクセスされているか、後続ノードがこれ以上ない場合は、その親ノードに戻ります。

疑似コード

グラフ G で検索を開始する頂点を v とします。

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）は、ツリーまたは無向グラフデータ構造を検索するためのアルゴリズムです。 ここでは、ノードから開始して、同じレベルのすべての隣接ノードを訪問し、次のレベルの隣接する後続ノードに移動します。 これは、*レベルごとの検索*とも呼ばれます。

幅優先検索の手順

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

疑似コード

グラフ G で検索を開始する頂点を v とします。

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()

ベストファースト検索

Best-First Searchは、グラフを横断して最短距離でターゲットに到達するアルゴリズムです。 BFSやDFSとは異なり、Best-First Searchは評価関数に従って、次に通過するのに最も適切なノードを決定します。

ベストファースト検索の手順

• ルートノードから開始し、訪問済みとしてマークします。
• 次の適切なノードを見つけて、訪問済みとしてマークします。
• 次のレベルに進み、適切なノードを見つけて、訪問済みとしてマークします。
• 目標に達するまでこのプロセスを続けます。

疑似コード

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