|
组合算法的评价依据同时也是建立数学模型和优化算法的指导思想。那么应该如何设计高效，通用的组合算法呢？下面我们通过几个实际的组合问题来初步研究。
例1．核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以反应产生3个β粒子，而一个β粒子可以反应产生1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t时刻的反应堆中α粒子和β粒子数。
这是一个物理学中的简单问题。我们通过对两种算法的比较来说明组合算法的通用性。
模型I：本题中共涉及两个变量，设在i时刻α粒子数为ni，β粒子数为mi，则有：n0=1,m0=0,ni=mi—1，mi=3ni—1+2mi—1
本题便转化为求数列N和M的第t项，我们可用递推的方法求得nt和mt，此模型的空间需求较小，时间复杂度为O（n），但随着n的增大，所需时间越来越大，即：
T
n
此模型的算法如下：
算法1-1
Prog Arithmtic1_1;
Begin
Read(t);
n[0]:=1; //初始化操作
m[0]:=0;
for i:=1 to t do //进行t次递推
begin
n[i]:=m[i-1];
m[i]:=3*n[i-1]+2*m[i-1];
end;
write(n[t]); //输出结果
write(m[t]);
End. Arithmtic1_1
模型II：设在t时刻的α粒子数为f（t），β粒子数为g(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) （t≥2） （4）
g(0)=0,g(1)=3
（4）式的特征根方程为：
x2—2x—3=0
其特征根为x1=3,x2= -1
所以该式的递推关系的通解为
g(t)=C1·3t+C2·( -1)t
代入初值g(0)=0,g(1)=3得
C1+C2=0
3C1—C2=3
解此方程组得
所以该递推关系的解为
g(t)=
∴
即
算法1—2
Prog Arithmetic1_2;
Begin
read(t);
n:=trunc(exp(t*ln(3)));
m:=trunc(exp((t+1)*ln(3)));
if odd(t) then begin //判断( -1)t
n:=n-3;
m:=m+3;
end
else begin
n:=n+3;
m:=m-3;
end;
n:=trunc(n/4); // 4|n
m:=trunc(m/4); // 4|m
Write(n);
Write(m);
End. Arithmetic1_2
在模型II中，我们运用组合数学的方法建立了递归函数并转化为非递归函数。它的优点是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。
通过以上两个模型我们可以看出，模型II抓住了问题的本质，尤其成功地运用了组合数学中关于常系数线性齐次递推关系求解的有关知识，因而使算法本身既具有通用性和可计算性，同时达到了零信息冗余。
例2．在平面直角坐标系中，有n个圆心坐标为整点的单位圆，求它们所覆盖区域的总面积。
这是一道计算几何学的问题，关于图形并的问题，较为常用的方法是离散化，但是如果借助于组合数学的有关理论，是否可以设计出更好的算法呢？我们先来看几个简单的例子。
（1）两个圆的交（交集不为ф）
设圆i的圆心坐标为（xi,yi），我们定义一个异型函数（dissmilaruty function）如下：
在讨论两个圆的交的问题时，设两圆为圆1与圆2，它们的交有两种情况
①
设阴影部分面积为S，则
S=
=
=
②
设阴影部分面积为S，则
S=
=
=
由于两个圆的非空交集问题是圆最简单的交问题。所以我们规定 的交为α型交， 的交为β型交，这个规定将在下文的讨论中用到。
2、三个圆的交（交集不为ф）：
经过分析易证，若三个圆的交集不为空，则三个圆中任意两圆的交集一定不为空，反之亦成立。且在任意两圆相交所组成的三个交中，一定有2个α型交，1个β型交。如图所示，阴影部分面积为S，则有：
S=
=
3、四个圆的交（交集不为ф）
经分析可证，若四个圆的交集不为ф。则四个圆的圆心一定围成一个边长为1的正方形，这四个圆心按照顺时针（或逆时针方向）一定形成4个α型交，四个圆的交集如图中阴影部分所示，设其阴影部分面积为S，则：
S=
=
=
可以证明5个或5个以上互不重合的单位圆的交集必为φ。
分析至此，我们可以知道，任意多个单位圆的交集都可以通过2、3、4个圆的交而获得，那么任意多个单位圆的并集呢？由交集到并集，这使我们想起了容斥原理，于是得出：
模型有了，但是平面上的位置关系如何来表示呢？我们用带权有向图来有表示单位圆间的关系，边上的权函数定义如下：
0 Ai∩Aj=φ
C（i,j）= 1 Ai与Aj为α型交
2 Ai与Aj的β型交
于是所有单位圆之间的信息便可由一个三角矩阵表示出来。两个圆、三个圆、四个圆相交的情况可由下图表示：
1
i
1
1 i i i
m
j
j 1 2 2
1
1 j j k 1
k
(1) (2) (3) (4)
（1）图表示两圆为α型交的圆；（2）图表示两圆为β型为圆；（3）图表示3个圆相交的图，在3边中有 边权为2，其余两边权为1；（4）图为四个圆相交时的图。
题目标分析至此，我们便可轻松地设计出算法。
算法2
Func dissmilaruty_function(k1,k2:integer):integer;
Begin
l:=abs(x[k1]-x[k2])+abs(y[k1]-y[k2]);
//计算异型函数的值
if l>2 then return(0)
else return(l);
End; dissmilaruty_function
Proc Arithetic2;
Begin
count1:=0; //count1为а型交的个数
count2:=0; //count2为β型交的个数
area:=n*pi; //当所有圆都不相交时的面积值
for i:=1 to n-1 do
for j:=i+1 to n do
begin
list[i,j]:=dissmilaruty_function(i,j);
if list[i,j]=1 then count1:=count1+1; //两圆为α型交
else if list[i,j]=2 then count2:=count2+1;
//两圆为β型交
end;//判断两个圆的相交情况
area:=area-count1*s1-count2*s2;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
check:=true;
p:=list[i,j]+list[j,k]+list[i,k];
if (list[i,j]=0) or (list[j,k]=0) or (list[i,k]=0)
then check:=false;
if (p=4) and check then //三边的权值都不为0且权值之和为4
begin
count1:=count1+1; //三个圆的交不为空的个数
if list[i,j]=2 then info[i,k]:=2
else if list[j,k]=2 then info[j,k]:=2
else if list[i,k]=2 then info[i,k]:=2;
end;//info供判断四个圆的交的情况时使用
end;//判断三个圆的交的情况
area:=area+s3*count1;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (j<>k) and (info[i,j]=2) and (list[j,k]=1) and (list[i,k]=1) then count1:=count1+1; //四个圆的交的个数
area:=area-s4*count1;
End; Arithetic2
这种算法建立在对问题进行深入分析，数学抽象的基础之上的，因而无论在时间上还是在空间上都是较优的。更为重要的是，这种算法比离散化算法更精确，更具一般性，能够解决诸如图形并等一系列问题。且算法的实质是一种计数问题，具有较强的可计算性。
例3．一场激烈的足球赛开始前，售票工作正在紧张的进行中，每张球票为50元。现有2n个人排队等待购票，其中有n 个人手持50元的钞票，另外n个人手持100元的钞票，假设开始售票时售票处没有零钱。问这2n个人有多少种排队方式，使售票处不至出现找不开钱的局面？
这是一道典型的组合计数问题。从表面上看很难找出规律，下面我们基于本题建立几个模型，最终揭示问题的本质。
I．搜索模型
我们用深度优先搜索（DFS）算法来直观地模拟所有情况。算法中指定一变量k记录售票处有50元钞票的张数，初始时令k=0，若某人手持100元钞票且k=0时则回溯，否则继续递归。若第2n个人购完票即递归进行到第2n层时计数器累加1。递归结束后，计数器中的值便为排队总数。
算法3-1
Proc DFS(i:integer); //I为递归层数
Begin
for j:=0 to 1 do //j=0表示某人手持50元的钞票 ，j=1表示某人手持100元钞票 begin
if (j=0) then begin
k:=k+1; //k表示计数器
m:=m+1; //m表示有多少人手持50元钞票购票
if (m=n) then total:=total+1 //若已有n个人手持50元钞票购票，那么其余手持100元钞票购票的人一定能找开钱。
else dfs(i+1);
k:=k-1;
m:=m-1;
end
else begin //表示手持100元钞票时
if k>0 then
begin
k:=k-1;
dfs(i+1);
k:=k+1;
end;
end;
endfor;
End; dfs
由于本算法的实质是模拟，因此算法实现起来时间复杂度较高，为指数级，这种算法严格限制了问题的规模，因而不是一个好的算法。
II．栈模型
通过对问题的分析我们可以得出这样的结论：在任何时刻，若第n个人手持100元的钞票买票，则在此之前，定有m个人手持50元的钞票买票，使得m≥n，我们通过分析还将得出：售票处收到的50元的钞票最终将全部找出，售票处收到的100元的钞票最终将全部留下，且一旦收到一张面值为100元的钞票，则一定找出一张面值为50元的钞票。由此我们想到了用栈来表示这一过程：若某人手持一张50元的钱币购票，相当于一个元素进栈；若某人手持一张100元的钱币购票，相当于一个元素出栈。则问题转化为：若1~n共n个元素依次进栈，问共有多少种出栈顺序。
n个 元素的全排列共有n!个，那么这n!种方案是否都是可能的出栈顺序呢？答案是否定的，我们可以证明，若a1,a2,……an是可能的依次出栈顺序，则一定不存在这样的情况：使得i<j<k且aj<ak<ai，证明如下：
若i<j<k，说明ai 最先出栈，aj次之，ak最后出栈，下面分两种情况讨论：
（i）如果ai>aj，那么当aj 出栈时，如果ak已在栈中，则ak比aj先入栈，由输入a序列知：ak<aj,所以有ak<aj<ai;当出栈时，如果ak尚未入栈，则由输入序列知aj<ai<ak
（ii）如果ai<aj，那么当aj出栈时，如果ak已入栈，则由输入序列知ak<aj,而ai与ak的关系取决于ai与ak哪个先入栈。但无论怎样，ai与ak均小于aj，当aj出栈时，如果ak尚未入栈，则由输入序列知ai<aj<ak
因此，输出序列中不可能出现当i<j<k时，aj<ak<ai
通过以上分析，我们得出栈模型的算法，算法先产生1~n共n个数的全排列，对于每种排列，若符合前面所讲的出栈规则，那么这n个排列便是一个可能的出栈序列，计数器加1，当n个元素的全排列列举结束时，计数器的值便是问题的解。
在此思想的指导下，为了与模型I的算法进行比较，我们在这里采用递归技术来产生n个元素的全排列，若在每产生一个排列后进行该排列是否为可能输出栈序列的判定，则算法的时间复杂度为O（nn），与模型I的算法比较起来，我们发现模型II中递归的深度降低，栈的使用空间减小，但在构造解答树的过程中，每层扩展的结点数则大量增加，而有些结点的增加是无意义的，所以我们在实际的算法设计中可以一边生成排列一边进行可能输出序列的判定性检验，若不满足条件，则及时剪枝，因而在n较大时该算法的时间复杂度应小于O（nn）
算法3-2
Func check(s:integer):boolean; //判断1～s共s个元素的出栈序列是否为可能的栈输出序列
begin
for a:=1 to s-2 do
for b:=a+1 to s-1 do
if (data[b]<data[s]) and (data[s]<data[a]) then return(false);
reture(true);
end; check
Proc stack(i:integer); //产生n个元素的全排列
begin
for j:=1 to n do
if not(j in flag) then
begin
data[i]:=j;
if check(i) then
begin
flag:=flag+[j];
if i=n then total:=total+1 //计数器加1
else stack(i+1);
flag:=flag-[j];
end;
endfor;
end; stack
但我们应该明确地看到，模型I与模型II在算法实现时解答树中的结点数目都是很多的，结点是栈所储存的信息，大量结点的出现必然影响算法可运行数据的规模，在模型III中，我们着重思考如何对问题进行数学抽象。
III递归算法：
令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。我们分情况来讨论这个问题。
(1)n=0
n=0意味着排队购票的所有人手中拿的都是50元的钱币，那么这m个人的排队总数为1，即f(m,0 )=1
（2）m<n
若排队购票的(m+n)个人中有m个人手持50元的钞票，n个人手持100元的钞票，当m<n时，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，所以这时排队总数为0,即f(m,n)=0
（3）其它情况
我们思考（m+n）个人排队购票的情景，第(m+n)个人站在第（m+n-1）个人的后面，则第（m+n）个人的排队方式可由下列两种情况获得：
①第（m+n）个人手持100元的钞票，则在他之前的（m+n-1）个人中有m个人手持50元的钞票，有（n-1）个人手持100元的钞票，此种情况共有f(m,n-1)
②第（m+n）个人手持50元的钞票，则在他之前的（m+n-1）个人中有（m-1）个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)
由加法原理得f(m,n)=f(m-1,n)+f(m,n-1)
于是我们得到f(m,n)的计算公式：
0 m<n
f(m,n)= 1 n=0 （*）
f(m,n-1)+f(m-1,n)
于是我们可以根据（*）式编写递归算法
算法3-3
Func f(a,b:integer):longint;
begin
if a<b then f:=0
else if b=0 then f:=1
else f:=f(a-1,b)+f(a,b-1);
end; f
IV 递推算法
递归算法是由终止条件向初始条件推导，而递推算法是由初始条件向终止条件推导。可以说，它们本质上是相同的。那么，把递归算法改为递推算法的意义何在呢？我们运用（*）式求解f(4,4)，递归程序执行时构造的解答树如下：
14 f(4，4)
0 f(3，4) f(4，3)
14
5
9 f(3，3) f(4，2)
41
5
0
5 f(2,3) f(3,2) f(3,2) f(4,1)
31
31
2
2 f(2,2) f(3,1) f(2,2) f(3,1)
21
01
21
0 f(1,2) f(2,1) f(1,2) f(2,1)
通过对解答树的仔细观察我们会发现，在树中诸如f（3,2）等结点大量重复计算。由此我们看出，递归算法虽具有通用性和可计算性，但产生了大量的数据冗余，这些大量的数据冗余是限制递归算法规模的主要因素，从而导致模型Ⅲ虽进行了数学抽象，但算法实践起来的效率并不高。那么应如何避免大数据冗余以至最终达到零数据冗余呢？请看如下的二维表格：
m f n
1
2
3
4
5
1
1
0
0
0
0
2
2
2
0
0
0
3
3
5
| 
