《ACM组合算法的选择与应用》由会员分享，可在线阅读，更多相关《ACM组合算法的选择与应用（57页珍藏版）》请在金锄头文库上搜索。
1、 孙 贺 论 文 集 第 1 页 共 57 页组合算法的选择与应用组合算法的选择与应用【关键字关键字】组合算法组合算法 评价依据评价依据 复杂性复杂性 选择选择 应用应用【摘要摘要】本文提出了在组合算法设计和组合算法选择方面所应当遵循的三个原则，即通用性、可计算性和较少的信息冗余量，并初步分析了它们之间的相互关系。这三个原则是整个组合算法设计的主导思想，也是数学建模和算法优化的方向。通过对三个问题的分析，提示了组合算法的设计方法，改进方向和优化技术，是对一系列组合数学原理的实际应用，也是对组合算法设计的初步研究。【Abstract】【Abstract】The disquisition brin
2、gs forward three principle in combination arithmetic designing and combination arithmetic choice. There is currency, countability and less information redundancy. And the disquisition analyses the relation of them. The three principle is the dominant ideology in combination arithmetic designing. Als
3、o it is the aspect of making mathematics modeling and optimizing arithmetic. Then the disquisition analyses three questions, prompts the devisals method, betterments way and the technique optimizing 孙 贺 论 文 集 第 2 页 共 57 页arithmetic. That is actual appliance to a catena of combination mathematics ele
4、ments and it is also initial research in combination arithmetic designing.【正文】一、引一、引 论论组合数学是一个古老的数学分支，也是当代数学中非常重要的数学分支。它发源于有趣的数学游戏，许多古典的组合数学问题，无论在理论数学或应用数学上都有很重要的研究价值。今天，一方面，极为成熟的组合计数理论为物理学、化学、生物学的发展奠定了坚实的基础，另一方面，由于计算机软硬件的限制，组合计数理论的计算机实践又必然涉及到基于多项式时间内的算法优化问题。本文正是基于以上情况，对一系列组合问题的算法设计做了一些初步探索。二、组合算法的评
5、价依据二、组合算法的评价依据任何事物都有好坏之分，算法也不例外。众所周知，时间复杂度与空间复杂度是算法评价的主要依据。那么，除了这两点外，组合算法的设计还应遵循怎样的原则呢？1通用性通用性即可移植性。一个算法，是只适合于一个特殊问题，还是可以适用于一类问题，这是组合算法评价的一个主要依据，有些组合数学问题，许多信息学竞赛或数学建模竞赛选手一看到题目后往往使用模拟法或构造产生式系统1，然后用深度优先搜索（DFS） ，或广度优先搜索（BFS）求孙 贺 论 文 集 第 3 页 共 57 页解，用这些方法设计的程序往往受到时间或空间的限制，而且由于在综合数据库中信息存储的数据结构不同，其算法实现时的规
6、模2也不同，这必然影响到算法的通用性问题。解决问题的办法是对原问题进行数学抽象，取其精华，去其糟粕。只有对原问题的数学模型仔细分析，抓住本质，才能建立高效的组合算法，只有这种经过数学抽象的算法，才能具有较好的通用性，能够应付较大的规模。另外，在大规模组合算法的设计过程中，强调通用性的好处是显而易见的，它便于算法的优化和升级。在实际应用中的某些条件改变时，可以重写较少的代码。从软件工程学的角度来说，通用性是必需的。2可计算性这里指的可计算性，是指能够在多项式时间内得出结果。一般来说，对于递归函数来说，由于计算机系统中的空间一定，因此对问题的规模有较严格的限制（例如在 Turbo Pascal 7
7、.0 系统中，栈的最大空间只有65520 字节）因此说，对于大多数的递归函数具有较差的可计算性。通过组合方法，求递归函数的非递归形式是解决这类问题有主要方法，但并不是所有的递归函数都可转化为非递归形式，双递归函数（如 Ackermann 函数3）便不能转化为非递归形式，这类函数具有较小的可计算性。当然，对于某些递归函数，通过寻找函数本身的组合意义进而将其转化为非递归函数也是一种方法。这种方法的应用读者将在后文中见到。3、信息冗余量1 见参考文献6第一章2 在本论文中，我们将规模定义为在一定时间内程序可以运行完毕的情况下输入数据的最大量。 3 Ackermann 函数可用递推关系如下定义A（m，
8、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 页 共 57 页在组合数学的建模过程中，大量的信息冗余是制约组合算法效率的一个重要因素，例如在递归程序运行的过程中，实际上产生了一棵解答树4，同一棵子树的结点间的信息不相互关联，这样便产生了大量的信息冗余，解决的方法之一便是引入记忆机制，将已得出的信息记录下来。这种机制实际上起到了剪枝的作用，但它严格受到空间的限制，实际上是时空矛盾在算法设计中的体现。这便是我们在组合算法设计中倡导函数非递归化的原因。它可以达到零
9、信息冗余。当然，组合算法的通用性、可计算性与信息冗余程度在一定程度上是对立的。例如双递归函数作为一种数学模型，能够反映一类问题，具有通用性，但却具有较差的可计算性和较大的信息冗余量，而有些问题虽具有较好的可计算性和较低的信息冗余量，却具有较差的通用性。总之，算法的时间复杂度，空间复杂度，通用性，可计算性和信息冗余量应是衡量组合算法的几个主要标准。三、组合算法的选择实例三、组合算法的选择实例组合算法的评价依据同时也是建立数学模型和优化算法的指导思想。那么应该如何设计高效，通用的组合算法呢？下面我们通过几个实际的组合问题来初步研究。例例 1 1核反应堆中有 和 两种粒子，每秒钟内一个 粒子可以反应
10、产生 3 个 粒子，而一个 粒子可以反应产生 1 个 粒子和 2 个 粒子。若在 t=0 时刻的反应堆中只有一个 粒子，求在 t 时刻的反应堆中 粒子和 粒子数。这是一个物理学中的简单问题。我们通过对两种算法的比较来说明组4 见参考文献6第二章（产生式系统的搜索策略）孙 贺 论 文 集 第 5 页 共 57 页合算法的通用性。模型 I：本题中共涉及两个变量，设在 i 时刻 粒子数为 ni， 粒子数为 mi，则有：n0=1,m0=0,ni=mi1，mi=3ni1+2mi1 本题便转化为求数列 N 和 M 的第 t 项，我们可用递推的方法求得 nt和 mt，此模型的空间需求较小，时间复杂度为 O（
11、n） ，但随着 n 的增大，所需时间越来越大，即：Tn此模型的算法如下：算法算法 1-11-1ProgProg Arithmtic1_1;BeginBeginReadRead(t);n0:=1; /初始化操作m0:=0;forfor i:=1 toto t dodo /进行 t 次递推beginbeginni:=mi-1;mi:=3*ni-1+2*mi-1;end;end;writewrite(nt); /输出结果孙 贺 论 文 集 第 6 页 共 57 页writewrite(mt);End.End. Arithmtic1_1模型 II：设在 t 时刻的 粒子数为f（t） ， 粒子数为 g(
12、t)，依题可知： g(t)=3f(t -1)+2g(t -1) （1）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) （t2） （4）g(0)=0,g(1)=3（4）式的特征根方程为：x22x3=0其特征根为 x1=3,x2= -1所以该式的递推关系的通解为g(t)=C13t+C2( -1)t代入初值 g(0)=0,g(1)=3 得C1+C2=03C1C2=3解此方程组得43,4321CC所以该递推关系的解为g(t)=tt) 1(433431
13、1) 1(43343) 1()(tttgtf即 tt tf) 1(43 43)(孙 贺 论 文 集 第 7 页 共 57 页算法算法 1 12 2ProgProg Arithmetic1_2;BeginBeginreadread(t);n:=trunc(exp(t*ln(3);m:=trunc(exp(t+1)*ln(3);ifif odd(t) thenthen beginbegin /判断( -1)tn:=n-3;m:=m+3;endendelseelse beginbeginn:=n+3;m:=m-3;endend;n:=trunc(n/4); / 4|n m:=trunc(m/4);
14、/ 4|mWriteWrite(n);WriteWrite(m);EndEnd. Arithmetic1_2在模型 II 中，我们运用组合数学的方法建立了递归函数并转化为非递归函数。它的优点是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。通过以上两个模型我们可以看出，模型 II 抓住了问题的本质，尤其成功地运用了组合数学中关于常系数线性齐次递推关系求解的有关知识，因而使算法本身既具有通用性和可计算性，同时达到了零信息冗余。孙 贺 论 文 集 第 8 页 共 57 页例例 2 2在平面直角坐标系中，有 n 个圆心坐标为整点的单位圆，求它们所覆盖区域的总面积。这是
15、一道计算几何学的问题，关于图形并的问题，较为常用的方法是离散化，但是如果借助于组合数学的有关理论，是否可以设计出更好的算法呢？我们先来看几个简单的例子。（1）两个圆的交（交集不为）设圆 i 的圆心坐标为（xi,yi） ，我们定义一个异型函数（dissmilaruty function）如下：|),(jijiyyxxji在讨论两个圆的交的问题时，设两圆为圆 1 与圆 2，它们的交有两种情况1)2 , 1 (设阴影部分面积为 S，则)321 21 31(22r=23 322r=23 322)2 , 1 (设阴影部分面积为 S，则S=孙 贺 论 文 集 第 9 页 共 57 页S=)21 41(222rr =22 2rr =12由于两个圆的非空交集问题是圆最简单的交问题。所以我们规定的交为 型交，的交为 型交，这个规定将
