全排列递归算法的并行化

《全排列递归算法的并行化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第4期　　　　　　　　　　　　　　　宁夏大学学报(自然科学版)2007年12月 　Vol.28No.4　　　　　　　　JournalofNingxiaUniversity(NaturalScienceEdition)Dec.2007文章编号:025322328(2007)0420337203全排列递归算法的并行化1,2吴素萍(1.宁夏大学数学计算机学院,宁夏银川　750021;　2.中国科学院数学机械化重点实验室,北京　100080)摘　要:全排列问题的递归算法结构清晰,可读性强.为了提高排列的效率,给

2、出了全排列递归算法在MIMP2CREW模型和单指令多数据流的EREW模型上的并行化算法及实例分析.给出的算法成本是最低的.关键词:全排列;递归算法;并行算法分类号:(中图)TP311　　　文献标志码:A　　穷举组合目标在科学和工程技术中有着广泛的应中唯一的元素;当n>1时,Permutation(P)由(p1)Per2用,在计算机科学中占据着重要的地位,其中排列是一mutation(P1),(p2)Permutation(P2),⋯,(pn)Permuta2种最基本的组合运算形式.排列当然也是计算彩票中tion

3、(Pn)构成.根据上面的定义,可设计产生递归算法奖几率的基础,并且排列在实际问题中也有着广泛的Permutation(S,k,m)应用,相应地也有许多排列算法[1-2].在问题规模较大1.2　算法描述[4].及一些难解问题中,排列算法的效率就是一个重要的输入为元素集合S={1,2,⋯,n};输出为输出所有问题,因此,提高排列算法的效率就有很重要的实际意n!种全排列. 义.人们可以通过设计出高效的并行排列算法[3],来提Permutation(S,k,m){高排列的效率.全排列递归算法有着广泛和重要的应　if(k

4、=m)用.它除了可解决一般意义的全排列问题,在用回溯法　{解决的许多的NP难问题,比如,电路板排列问题等等　　for(i=0;i≤m;i++)的解决,都用到了全排列递归算法.全排列问题的递归　　　输出S[i];算法[4]虽然结构清晰,可读性强,但它的运行效率较　}　else低,耗费的计算时间和占用的存储空间较多.本文对全排列的递归算法进行了研究,为了提高排列的效率,在　　for(i=k;i≤m;i++)　{两个不同的并行模型上给出了该算法的并行化算法,　　　swap(S[k],S[i]);并对并行算法进行了分析

5、.　　　Permutation(S,k+1,m);1　串行算法　　　swap(S[k],S[i]);　}1.1　算法原理}设P={p1,p2,⋯,pn}是要进行排列的n个算法Permutation(S,k,m)递归地产生所有前缀A[0:k-1],且后缀是S[k:m]的全排列的所有排列,调 元素,全排列问题要求给出n个元素的全排列.引入记号Pi=P-{pi},集合X中元素的全排列记为Permuta2用算法Permutation(S,0,n-1)则产生S的全排列.tion(X).(pi)Permutation(X)

6、表示在全排列Permuta2　　针对上面的算法也可进行改进,通过n-1次递tion(X)的每一个排列前加上前缀pi得到的排列.P的归调用产生第一位置是1的全排列,其他排列通过交全排列可归纳定义如下:换前面产生的所有排列的第一个元素和其他元素得当n=1时,Permutation(P)=(p),其中p是集合到.使原递归算法的n次递归调用改为n-1次调用.收稿日期:2006211219基金项目:中国科学院数学机械化重点实验室开放课题资助项目(200504);宁夏大学科研基金资助项目(LG0505) 作者简介:吴素萍(

7、19652),女,副教授,主要从事并行计算及符号计算研究.©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net338宁夏大学学报(自然科学版)　　　　　　　　　　　　　第28卷　2　并行算法所有进程均等待开始;如果采用排队的调度策略,进程1和进程2分别由处理器P1和P2执行,它们同并行计算机体系结构是并行算法运行的物质基时产生前缀为1的所有排列和前缀为2的所有排础,但是并行算法的

8、设计与分析不能局限于某种具列;然后进程3由处理器P1和处理器P2中空闲的体结构的并行计算机.因此,必须对各种具体的并行处理器启动执行产生前缀为3的所有排列,进程4计算机抽象化,抽象出具有一般意义的并行计算模则可由另一处理器启动执行产生前缀为4的所有排型,然后在此模型上研究并行算法.2.1　MIMD2CREW模型上的全排列递归算法列;稍后,当进程3和进程4执行完毕后,处理器P1和P2因无