- Parallel Algorithm Tutorial
- Parallel Algorithm Home
- Parallel Algorithm Introduction
- Parallel Algorithm Analysis
- Parallel Algorithm Models
- Parallel Random Access Machines
- Parallel Algorithm Structure
- Design Techniques
- Matrix Multiplication
- Parallel Algorithm - Sorting
- Parallel Search Algorithm
- Graph Algorithm
- Parallel Algorithm Useful Resources
- Parallel Algorithm - Quick Guide
- Parallel Algorithm - Useful Resources
- Parallel Algorithm - Discussion
并行搜索算法
搜索是计算机科学的基本操作之一。它用于我们需要查找元素是否在给定列表中的所有应用程序。在本章中,我们将讨论以下搜索算法 -
- 分而治之
- 深度优先搜索
- 广度优先搜索
- 最佳优先搜索
分而治之
在分而治之的方法中,问题被分为几个小子问题。然后对子问题进行递归求解并组合得到原问题的解。
分而治之的方法涉及每个级别的以下步骤 -
Divide - 将原始问题分为子问题。
征服- 子问题递归解决。
组合- 将子问题的解决方案组合起来以获得原始问题的解决方案。
二分查找是分而治之算法的一个例子。
伪代码
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