LiaoningNormalUniversity开放实验室项目研究论文题目：排列组合的并行实现学院：计算机与信息技术学院专业：计算机科学与技术班级序号：1班21号学号：学生姓名：指导教师：2011年12月第1页排列组合的并行实现学生：指导教师：郑晓薇张哲计算机与信息技术学院计算机科学与技术专业09级摘要：回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。排列组合是通过一定的约束条件，以及一定的规律来输出数字的几组排列。排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。关键词：回溯法，排列组合，约束条件Abstract：Backinthelawisatestthesolutionmethod:throughinductiveanalysisofproblem,findouttheproblemsolvingaclue,alongthecluesontest,testifsuccessful,namelygetsolution;Ifthetestfailure,hegraduallybacktowardstheback,changeotherroutesgoatest.Thepermutationandcombinationisthroughcertainconstraints,andcertainlawstooutputdigitalseveralgroupsofalignment.Thepermutationandcombinationisthecombinationofthemostbasiclearningconcept.Theso-calledarrangement,isreferstothenumberofelementsfromagivenouttheelementsofthedesignatednumberorder.Combinationmeansthatagivennumberofelementsfromthespecifiednumberofelementsoutonly,donotconsidersort.Toarrangeacombinationofcenterproblemsaregiventhearrangementandstudydemandcombinedthepossibilityoftotal.Keywords：backtrackingmethod;permutationandcombination;constraintcondition第2页前言许多问题的求解过程可以通过搜索问题的解空间来完成，而问题的解空间可用状态空间树来表示，树中的每一个节点对应问题求解的一个状态。对于一个状态S，如果由根到S的那条路径确定了这个解空间的一个元组，则称一个元组，则称S为一个解状态。如果树的搜索方法是深度优先的，就成为回溯法。排列组合的规律是多种多样的，此论文的排列组合是在设置其排列的最大数和排列的个数前提下，通过回溯法来完成其条件的约束，输出不同的排列，并实现并行。但是在回溯法的基础上并行经常会出现问题。所以要实现某些回溯法程序的并行，需要加在合适的位置上，这样才能有效的实现程序的并行化。第3页一、问题提出（一）背景分析许多要求寻找一组解满足某些约束条件的最优解的问题中，回溯法非常有用。但是随着问题复杂性的增加，串行回溯搜索往往非常费时，所以为了加快搜索速度，提高效率。实现回溯搜索的并行化就具有十分重要的意义。在某些排列组合中，用回溯法来进行数字序列的排列是非常稳定的，但是由于回溯法是通过不断返回根节点来寻找最优解非常耗时，所以在回溯的基础上实现并行化更是提高了排列的效率。（二）排列组合的具体约束条件如下排列：1213141521232425313234354142434551525354输出以上几组排列，通过设置m=2,n=5来约束排列中允许出现最大的数以及一组排列的个数，在每个排列中，不允许出现相同的数字，也不允许出现相同的排列。并统计其组成排列的个数。二、回溯法解决排列组合（一）串行算法设计应用回溯法产生排列A(n,m)，设置一维数组a，a(i)(i=1,2,...,m)在1～n中取值。首先从a(1)=1开始，逐步给a(i)(1≤i≤m)赋值，每一个a(i)赋值从1开始递增至n。定义变量g=1,当排列中有相同元素则g=0。若i=m与g=1?同时满足，则为一组解，用s统计解的个数后，格式打印输出这组解。由数字1～n组成的m位整数组，其约束条件是没有相同数字。（三）排列组合串行程序算设计其串行代码如下：#include"stdafx.h”#include第4页#include#defineN30voidmain(){doublebegin,end;begin=(double)clock();intn,m,a[N],i,j,g;longs=0;printf("inputn(n<10):");scanf("%d",&n);printf("inputm(1
