使用OpenMP并行化常见算法_openmp算法

OpenMP并行化常见算法

openmp是强大的并行编译库，可以动态地设置多线程，使用方便。
这里我将以搜索算法为例，介绍如何用OpenMP把常见算法并行化。

旅行商问题

旅行商问题已经老生常谈了。指在有向带权图内，寻找一条最短回路(指经过每个顶点仅一次，且权值总和最小)。事实上该问题是一个NPhard问题，想解决它只能花费指数级的时间复杂度。
我们尝试使用BFS和DFS去求解它。因为题目要求经过每个顶点仅一次，则不会出现环，即只要约定我们的搜索不走已经经过的顶点，搜索的状态就永远不会出现交叉，即我们是要在一个解空间树里求解。
先定义用于表示一个搜索状态的结构体，以及一个用于求下一状态的算法。

/*
记录搜索状态的状态结点
用经典数组保存路径，其中order[i]表示i顶点被造访的
时间顺序，起点的order[i]为0，后续每下溯一层则加1
front表示最新造访的顶点，以它为起点下溯一层。
order[i]==-1表示从未造访过，也是我们可以扩展的顶点。
*/
struct Node
{
   
	int order[N];
	int front = -1;
	int cost = 0;
	Node() {
    fill(order, order + N, -1); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

successors算法很简单，我们在结构体里已经定义了分辨顶点是否被遍历过的方法order[i]==-1，只需要遍历所有顶点，并把未遍历过的顶点作为后继顶点生成新的解状态结点即可。
考虑DFS算法，如果用非递归的形式，也就是用栈和循环模拟递归，自然可以实现循环形式的DFS算法。既然搜索的是解空间树，循环的各部分没有相关性，我们就能用parallel for语句直接把DFS并行化，这是相当简单的。
解空间树的分支因子在最上层为n-1，每向下一层，如果要简单地划分for循环来实现并行，则在最上层划分是最优解。
当n远大于线程数时自然可行，但是本问题是NPhard问题，n很大时是不可能求解的，一般n都在几十左右，而我们的线程数却有可能很多，这样就造成了极大的负载不均衡，会失去我们原有的并行优越性。
为此可能需要并行化的BFS，BFS借助队列进行。每次从队首取出结点，然后求successors，把新的结点放入队尾。很容易看出，每个successors操作之间是可以并行的，而一次successors操作只需要线性时间复杂度，这就把原有的大规模问题变得颗粒化。只要我们的多线程每次都从队列中请求元素，然后并行地执行successors，再把新结点入队，就实现了很好的负载均衡的并行搜索算法。
要注意的一点是，队列不允许并行的pop和push，因此操作队列的代码应该被设置线程锁；此外，修改全局变量，最优解solution时，也要设计线程锁。
另一个问题，单线程中，我们直接认为队列为空的时候就是搜索完毕的时候。但多线程中，即使搜索未进行完，仍然有可能让队列为空，这时某个线程去队列内请求元素就会造成报错。因此对搜索进行完毕就需要其他的逻辑，当所有的叶结点，也就是goalstate都被搜索完的时候，搜索就真正结束了。在此之前，某些线程即使无法从队列中得到元素，也不能退出循环，而需要一直等待。
bfs的cpp代码如下

#include <iostream>
#include <algorithm>
#include <omp.h>
#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;

#define N 4

/*
问题：
开发能并行线程解决旅行商问题的程序。
旅行商问题是在一张n个顶点的全连通带权图中，寻找一条经过
每个顶点仅一次，并且能回到出发城市的“回路”，并让
这个回路的cost最小。我们能够证明的是，没有多项式
级别的算法能求解本问题，我们至少要花费指数级的时间
去计算。

分析：解决旅行商问题的基本算法就是朴素的搜索，一般使用
空间占用较小的DFS搜索。首先分析问题&#x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22