排列组合并行算法的实现.doc

Liaoning Normal University开放实验室项目研究论文题 目： 排列组合的并行实现学 院： 计算机与信息技术学院专 业： 计算机科学与技术班级序号： 1班21号学 号： 学生姓名： 指导教师： 2011年12月排列组合的并行实现学生： 指导教师：郑晓薇 张哲计算机与信息技术学院 计算机科学与技术专业 09级摘要：回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。排列组合是通过一定的约束条件，以及一定的规律来输出数字的几组排列。排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。关键词：回溯法，排列组合，约束条件Abstract： Back in the law is a test the solution method: through inductive analysis of problem, find out the problem solving a clue, along the clues on test, test if successful, namely get solution; If the test failure, he gradually back towards the back, change other routes go a test. The permutation and combination is through certain constraints, and certain laws to output digital several groups of alignment. The permutation and combination is the combination of the most basic learning concept. The so-called arrangement, is refers to the number of elements from a given out the elements of the designated number order. Combination means that a given number of elements from the specified number of elements out only, do not consider sort. To arrange a combination of center problems are given the arrangement and study demand combined the possibility of total. Key words：backtracking method; permutation and combination; constraint condition前言许多问题的求解过程可以通过搜索问题的解空间来完成，而问题的解空间可用状态空间树来表示，树中的每一个节点对应问题求解的一个状态。对于一个状态S，如果由根到S的那条路径确定了这个解空间的一个元组，则称一个元组，则称S为一个解状态。如果树的搜索方法是深度优先的，就成为回溯法。排列组合的规律是多种多样的，此论文的排列组合是在设置其排列的最大数和排列的个数前提下，通过回溯法来完成其条件的约束，输出不同的排列，并实现并行。但是在回溯法的基础上并行经常会出现问题。所以要实现某些回溯法程序的并行，需要加在合适的位置上，这样才能有效的实现程序的并行化。一、 问题提出（一） 背景分析许多要求寻找一组解满足某些约束条件的最优解的问题中，回溯法非常有用。但是随着问题复杂性的增加，串行回溯搜索往往非常费时，所以为了加快搜索速度，提高效率。实现回溯搜索的并行化就具有十分重要的意义。在某些排列组合中，用回溯法来进行数字序列的排列是非常稳定的，但是由于回溯法是通过不断返回根节点来寻找最优解非常耗时，所以在回溯的基础上实现并行化更是提高了排列的效率。（二） 排列组合的具体约束条件 如下排列： 12 13 14 15 21 23 24 25 31 32 34 35 41 42 43 45 51 52 53 54 输出以上几组排列，通过设置m=2,n=5来约束排列中允许出现最大的数以及一组排列的个数，在每个排列中，不允许出现相同的数字，也不允许出现相同的排列。并统计其组成排列的个数。二、 回溯法解决排列组合（一）串行算法设计 应用回溯法产生排列A(n,m)，设置一维数组a，a(i)(i=1,2,.,m)在1n中取值。首先从a(1)=1开始，逐步给a(i)(1im)赋值，每一个a(i)赋值从1开始递增至n。定义变量g=1,当排列中有相同元素则g=0。若i=m与g=1同时满足，则为一组解，用s统计解的个数后，格式打印输出这组解。由数字1n组成的m位整数组，其约束条件是没有相同数字。（三） 排列组合串行程序算设计 其串行代码如下： #include "stdafx.h”#include<time.h> #include <stdio.h> #define N 30 void main() double begin,end; begin=(double)clock();int n,m,aN,i,j,g; long s=0; printf(" input n (n<10):"); scanf("%d",&n); printf(" input m(1<m<=n):"); scanf("%d",&m); i=1;ai=1; while(1) g=1; for(j=1;j<i;j+) if(aj=ai)g=0;break; /*出现相同元素时返回*/ if(g && i=m) s+; for(j=1;j<=m;j+) printf("%d",aj); /*输出一个排列*/ printf(" "); if(s%10=0) printf("n"); if(g && i<m) i+;ai=1;continue; while(ai=n) i-; /*回溯到前一个元素*/ if(i>0) ai+; else break; printf("n s=%ldn",s);end=(double)clock(); printf("串行查找的时间：%f秒n",(end-begin)/(double)CLOCKS_PER_SEC);（四） 排列组合串行程序运行结果 运行结果：(1) 当n=5,m=3 如图一 图一n=5,m=3串行运行结果（2）当n=6,m=4如图二 图二n=6,m=4串行运行结果三、 并行实现排列组合（一） 并行思想 通过并行语言OpenMP来实现程序的并行，并行是通过多核处理器对CPU进行有效的利用，把一个程序通过多线程处理的方式缩短时间，提高运行的效率。 OpenMP的编程模型以线程为基础，通过编译指导语句来显示地指导并行化，为编程人员提供了对并行化的完整的控制。它是一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言。具有良好的可移植性，支持多种编程语言，能够支持多种平台，包括大多数的类UNIX系统以及Windows NT系统（Windows 2000，Windows XP，Windows Vista等）。使用运行时函数库所包含的函数，必须在相应的源文件中包含OpenMP头文件，即#include “omp.h”四个最常用的OpenMP库函数：int omp_get_num_threads(void)返回当前使用的线程个数。int omp_set_num_threads(int NumThreads)在进入并行区域前，该函数设置将要使用的线程个数，它可以覆盖环境变量OMP_NUM_THREADS的值。int omp_get_thread_num(void)返回当前线程号，值在0(主线程)到线程总数减1之间。int omp_get_num_procs(void)返回可用的处理核(处理器)个数。支持超线程技术的处理核或处理器将被算作两个处理核(或两个处理器)。（二） 排列组合并行程序的实现在该排列组合中有两个循环可以套用变成并行循环，但其中一个中有break跳出无法执行并行，所以就用另一个循环来进行并行循环。其核心代码如下： s+;omp_set_num_threads(4) #pragma omp parallel for for(j=1;j<=m;j+) printf("%d",aj); /*输出一个排列*/ printf(" "); if(s%10=0) printf("n"); （三） 并行程序运行结果（1）当n=5,m=3 如图三图三n=5,m=3并行运行结果（2）当n=6,m=4如图四图四n=6,m=4并行运行结果四、并行运行结果与串行运行结果分析程序运行加速比：串行执行时间/并行执行时间m时间(s)时间(s)时间(s)平均时间加速比串行n=9 31.91.71.91.831.3343.4062.9843.3433.24458.2507.8128.4688.1751.36628.37530.84432.20330.4747105.875106.48499.093103.8171.24并行n=931.2031.5311.3751.36942.4532.1562.5002.3691.0656.5626.4846.6706.572628.02329.37528.62528.6742.06757.69842.07850.92150.232通过运行的数据的记录 排列组合通过并行其平均加速比为:1.41通过以上数据可以看出当n较大时，它加速比较明显提高，运行效率越高。在原来的初始并行设想中，是在程序刚开始访问根节点时并行，但是由于是回溯法，在判断排列是否相同时跳出了循环。由于其回溯法的数据相关性无法在那层循环中实现并行。如果可以在那层循环并行，其运行效率会更加有所提高。 while(1)g=1;omp_set_num_threads(4)/在for循环前加循环并行导语句#pragma omp parallel for for(j=1;j<i;j+)if(aj=ai)g=0;break;/跳出循环无法执行并行 五、 结束语 通过对排列组合程序并行算法的学习与编写，让我收获很多。首先，我的排列组合程序是一个通过回溯法来执行的程序。让我通过此程序理解回溯法的含义，更加熟练的运用回溯法来编写程序。再次让我通过此次编程接触了并行思想以及如何运用并行语言来实现程序的并行设计。同时也让我发现了回溯法在并行过程中的问题。以后也会沿着此方向来进行深入研究。完善程序的并行实现。参考文献： 1 陈国良 编著. 并行算法：排序和选择. 中国科大出版社，1990；台湾儒林图书公司 2 李晓梅，蒋增荣.并行算法M.湖南：湖南科学技术出版社，19923 李宝峰.多核程序设计技术M.北京:电子工业出版社，20074 陈国良 编著. 并行算法的设计与分析. 高等教育出版社（修订版），20025 沈志宇 等编著. 并行程序设计. 国防科大出版社，1997