《组合算法的选择与应用》由会员分享，可在线阅读，更多相关《组合算法的选择与应用（23页珍藏版）》请在金锄头文库上搜索。
1、组合算法的选择与应用【关键字】组合算法评价依据复杂性选择应用【摘要】本文提出了在组合算法设计和组合算法选择方面所应当遵循的三个原那么，即通用性、可计算性和较少的信息冗余量，并初步分析了它们之间的相互关系。这 三个原那么是整个组合算法设计的主导思想， 也是数学建模和算法优化的方向。 通 过对三个问题的分析，提示了组合算法的设计方法，改良方向和优化技术，是对 一系列组合数学原理的实际应用，也是对组合算法设计的初步研究。【正文】一、引论组合数学是一个古老的数学分支，也是当代数学中非常重要的数学分支。 它发源丁有趣的 数学游戏，许多古典的组合数学问题，无论在理论数学或应用数学上都有很重要的研究价值。今
2、天，一方面，极为成熟的组合计数理论为物理学、化学、生物学的开展奠定了坚实的基 础，另一方面，由丁计算机软硬件的限制，组合计数理论的计算机实践乂必然涉及到基丁多项 式时间内的算法优化问题。本文正是基丁以上情况，对一系列组合问题的算法设计做了一些初 步探索。二、组合算法的评价依据任何事物都有好坏之分，算法也不例外。众所周知，时间复杂度与空间复杂度是算法评价 的主要依据。那么，除了这两点外，组合算法的设计还应遵循怎样的原那么呢？1. 通用性通用性即可移植性。一个算法，是只适合丁一个特殊问题，还是可以适用丁一类问题，这 是组合算法评价的一个主要依据,有些组合数学问题,许多信息学竞赛或数学建模竞赛选手一
3、 看到题目后往往使用模拟法或构造产生式系统1,然后用深度优先搜索DFS,或广度优先搜 索BFS求解，用这些方法设计的程序往往受到时间或空间的限制，而且由丁在综合数据库 中信息存储的数据结构不同，其算法实现时的规模见参考文献6第一章在本论文中，我们将规模定义为在一定时间内程序可以运行完毕的情况下输入数据的最大量。也不同，这必然影响到算法的通用性问题。 解决问题的方法是对原问题进行数学抽象， 取其精华，去其糟粕。只有对原问题的数学模型仔 细分析，抓住本质，才能建立高效的组合算法，只有这种经过数学抽象的算法，才能具有较好 的通用性，能够应付较大的规模。另外，在大规模组合算法的设计过程中，强调通用性的
4、好处是显而易见的，它便丁算法的 优化和升级。在实际应用中的某些条件改变时，可以重写较少的代码。从软件工程学的角度来 说，通用性是必需的。2. 可计算性这里指的可计算性，是指能够在多项式时间内得出结果。一般来说，对丁递归函数来说，由丁计算机系统中的空间一定，因此对问题的规模有较严格的限制例如在Turbo Pascal 7.0系统中，栈的最大空间只有65520字节因此说，对丁大多数的递归函数具有较差的可计算性。通过组合方法，求递归函数的非递归形式是解决这类问题有主要方法， 但并不是所有的递归函 数都可转化为非递归形式，双递归函数如 Ackermann函数 Ackermann函数可用递推关系如下定义
5、A (m, 0) =A (m-1 , 0)m=1, 2,A (m, n) =A (m-1 , A (m, n-1 )m=1 , 2, ,n=1 , 2,初始条件为A (0, n) =n+1 , n=0, 1,4见参考文献6第二章(产生式系统的搜索策略)便不能转化为非递归形式，这 类函数具有较小的可计算性。当然，对丁某些递归函数，通过寻找函数本身的组合意义进而将其转化为非递归函数也是 一种方法。这种方法的应用读者将在后文中见到。3、信息冗余量在组合数学的建模过程中,大量的信息冗余是制约组合算法效率的一个重要因素，例如在递归程序运行的过程中，实际上产生了一棵解答树4,同一棵子树的结点间的信息不相互
6、关联， 这样便产生了大量的信息冗余，解决的方法之一便是引入记忆机制，将已得出的信息记录下来。 这种机制实际上起到了剪枝的作用，但它严格受到空间的限制，实际上是时空矛盾在算法设计 中的表达。这便是我们在组合算法设计中倡导函数非递归化的原因。它可以到达零信息冗余。当然，组合算法的通用性、可计算性与信息冗余程度在一定程度上是对立的。例如双递归 函数作为一种数学模型，能够反映一类问题，具有通用性，但却具有较差的可计算性和较大的 信息冗余量，而有些问题虽具有较好的可计算性和较低的信息冗余量，却具有较差的通用性。 总之，算法的时间复杂度，空间复杂度，通用性，可计算性和信息冗余量应是衡量组合算法的 几个主要
7、标准。三、组合算法的选择实例组合算法的评价依据同时也是建立数学模型和优化算法的指导思想。那么应该如何设计高效，通用的组合算法呢？下面我们通过几个实际的组合问题来初步研究。例1 .核反响堆中有a和6两种粒子，每秒钟内一个a粒子可以反响产生3个6粒子，而 一个6粒子可以反响产生1个a粒子和2个6粒子。假设在t=0时刻的反响堆中只有一个a粒子, 求在t时刻的反响堆中a粒子和6粒子数。这是一个物理学中的简单问题。我们通过对两种算法的比拟来说明组合算法的通用性。模型I：此题中共涉及两个变量，设在 i时刻a粒子数为ni, 6粒子数为 mi,那么有： n0=1,m0=0,ni=mi i, mi=3ni i+
8、2mi 1此题便转化为求数列N和M的第t项，我们可用递推的方法求得nt和mt,此模型的空间 需求较小，时间复杂度为O (n)，但随着n的增大，所需时间越来越大，即：Tn此模型的算法如下：算法1-1Prog Arithmtic1_1;BeginRead(t);n0:=1;初始化操作m0:=0;for i:=1 to t do/进行t次递推beginni:=mi-1;mi:=3*ni-1+2*mi-1;end;write (nt);输出结果write (mt);End. Arithmtic1_1模型II：设在t时刻的a粒子数为f (t ), 6粒子数为g(t),依题可知:厂 g(t)=3f(t-1
9、)+2g(t-1)(1)J f(t)=g(t -1)(2)g(0)=0,f(0)=1下面求解这个递归函数的非递归形式由(2)得 f(t -1)=g(t-2)(3)将(3)代入(1)得g(t)=3g(t -2)+2g(t-1)(t 2)(4)g(0)=0,g(1)=3(4) 式的特征根方程为：2x 2x3=0其特征根为X1=3,X2= -1所以该式的递推关系的通解为g(t)=C1 - 3t+C2 - ( -1)t 代入初值g(0)=0,g(1)=3得 C1+C2=03C1C2=3解此方程组得C1 =,C2 = 44所以该递推关系的解为g(t)= 4 3t -j (-1). f(t) =g(t -
10、1) =3 3t4 - (-1广t c 44即 f (t) = 一 3 ( -1)t44算法1 2Prog Arithmetic1_2;Beginread (t);n:=trunc(exp(t*ln(3);m:=trunc(exp(t+1)*ln(3);if odd(t) then begin / 判断(-1)tn:=n-3;m:=m+3;endelse beginn:=n+3;m:=m-3;end ;n:=trunc(n/4); / 4|nm:=trunc(m/4); / 4|mWrite (n);Write (m);End. Arithmetic1_2在模型II中，我们运用组合数学的方法建
11、立了递归函数并转化为非递归函数。它的优点 是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。通过以上两个模型我们可以看出，模型II抓住了问题的本质，尤其成功地运用了组合数学 中关丁常系数线性齐次递推关系求解的有关知识，因而使算法本身既具有通用性和可计算性， 同时到达了零信息冗余。例2.在平面直角坐标系中，有n个圆心坐标为整点的单位圆，求它们所覆盖区域的总面 积。这是一道计算几何学的问题，关丁图形并的问题，较为常用的方法是离散化，但是如果借 助丁组合数学的有关理论，是否可以设计出更好的算法呢？我们先来看几个简单的例子。(1) 两个圆的交(交集不为巾)设圆i的圆心坐
12、标为(xi,yi)，我们定义一个异型函数(dissmilaruty function)如下：(i, j) =|为Xj | | yi - yj |(1,2) =1在讨论两个圆的交的问题时，设两圆为圆 1与圆2,它们的交有两种情况设阴影局部面积为S,那么(1,2) =2设阴影局部面积为S,那么S=2 ( 二r2 _ 1 r2)42二 22=r - r2ji=-12由丁两个圆的非空交集问题是圆最简单的交问题。所以我们规定中i, j =1的交为a型交,平i,j= 2的交为6型交，这个规定将在下文的讨论中用到。2、三个圆的交交集不为巾：经过分析易证，假设三个圆的交集不为空，那么三个圆中任意两圆的交集一定
13、不为空，反之亦成立。且在任意两圆相交所组成的三个交中，一定有2个a型交，1个6型交。如下图，阴影局部面积为S,那么有：S=2 (1 二623 2、 二 2r -r ) r412二.3二5.3+=兀3212 1223、四个圆的交交集不为巾经分析可证，假设四个圆的交集不为 巾。贝U四个圆的圆心一定围成一个边长为 1的正方形, 这四个圆心按照顺时针或逆时针方向一定形成4个a型交，四个圆的交集如图中阴影局部 所示，设其阴影局部面积为S,贝U:S=(2r sin15 )2 二r2 -2rsin15 - cos1512222 21心=4r sin 15r sin30 r12221= 4sin 1512 4
14、可以证明5个或5个以上互不重合的单位圆的交集必为 4 。分析至此，我们可以知道，任意多个单位圆的交集都可以通过2、3、4个圆的交而获得,那么任意多个单位圆的并集呢？由交集到并集，这使我们想起了容斥原理，丁是得出:nnJ nn _2 n J n| A, 一 A2An|= Ai M M | A - Aj | 二-| A A人 |i 4i j 4 1旧 j A，J .1n _3 n _2 n J n| A - Aj - Ak - Am |i 4 j k d 1 m 1模型有了，但是平面上的位置关系如何来表示呢？我们用带权有向图来有表示单位圆问的 关系，边上的权函数定义如下：=0 Ai n Aj= 4C (i,j) =J 1 Ai 与 Aj 为 a 型交2Ai与Aj的6型交丁是所有单位圆之间的信息便可由一个三角矩阵表示出来。两个圆、三个圆、四个圆相交 的情况可由以下图表示：(2)(3)(4)(1)图表示两圆为a型交的圆；(2)图表示两圆为6型为圆；(3)图表示3个圆相交的图，在 3边中有边权为2, 其余两边权为1; (4)图为四个圆相交时的图。题目标分析至此，我们便可轻松地设计出算法。算
