Parallel Search Algorithm - Parallel Algorithm

How searching is done in parallel algorithm?

Searching is used in all the parallel algorithm applications. Some of the search algorithms explained in this chapter are as follows:

  • Divide and Conquer
  • Depth-First Search
  • Breadth-First Search
  • Best-First Search

Divide and Conquer

The problem is divided into small sub-problems. The sub-problems are solves recursively and the solution for the original problem is obtained by combining all the solutions.

At each level of algorithm, following steps are involved in divide and conquer approach -

  • Divide – The problem is divided into sub-problems.
  • Conquer − The sub-problems are solved recursively.
  • Combine – The solution of the original problem is obtained by combining the solutions of the sub-problems.

Example of divide and conquer algorithm is Binary Search.

Pseudocode

Depth-First Search

A tree or an undirected data structure graph is searched by Depth-First Search algorithm. It starts from the starting node called as Root and to the possible extent traverses in the same branch. If the node without the successor node is obtained, the search algorithm returns and continues with the vertex.

Steps of Depth-First Search

  • The node that is not visited previously is considered.
  • The first adjacent successor node is visited and is marked as visited.
  • If all the successors nodes of the considered node are visited already and do not have any more successor node, the search algorithm returns to the parent node.

Pseudocode

Let v be the vertex where the search starts in Graph G.

Breadth-First Search

A tree or an undirected graph algorithm is searched by this algorithm. Initially it starts with a node and all the adjacent nodes in the same level are visited and is then moved to the adjacent successor nodes in the next level. Hence it is also known as level-by-level search.

Steps of Breadth-First Search

  • The algorithm starts with a root node, which is marked as visited.
  • When there is no node in the same level as that of the root node, shift to next level.
  • All the adjacent nodes are visited and marked as visited.
  • In the next level, all the unvisited adjacent nodes are visited.
  • Till all the nodes are visited, the process is continued.

Pseudocode

Let v be the vertex where the search starts in Graph G.

Best-First Search

In order to reach the target in the shortest possible path, an algorithm traverses a graph. An evaluation function is followed for determining the appropriate node to traverse next.

Steps of Best-First Search

  • Start with the root node, mark it visited.
  • The next appropriate node is found and is marked as visited.
  • In the next level, find the appropriate node and mark it as visited.
  • Till the target is reached, the process is continued.

Pseudocode

Parallel Algorithm Related Tutorials

Parallel Algorithm Related Practice Tests


All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Parallel Algorithm Topics