Matlab 版 (精华区)
发信人: zjliu (秋天的萝卜), 信区: Matlab
标 题: 算法学习之二
发信站: BBS 哈工大紫丁香站 (Sun May 9 16:18:17 2004)
发信站: 我爱南开站
六、贪婪法
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可
以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时
间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪
法不要回溯。
例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有
各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面
值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用
贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙
安排。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币。按贪
婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的
解应是3个5单位面值的硬币。
【问题】 装箱问题
问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n种物品，体积分别为
v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均
不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。
装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以
找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是
无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物
品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常
好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-
1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结
果对物品重新编号即可。装箱算法简单描述如下：
{ 输入箱子的容积；
输入物品种数n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for (i=0;i<n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一个箱子，并将物品i放入该箱子；
box_count++；
}
else
将物品i放入箱子j；
}
}
上述算法能求出需要的箱子数box_count，并能求出各箱子所装物品。下面的
例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、
20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各
箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子
装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构
记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链
表。以下是按以上算法编写的程序。
【程序】
# include <stdio.h>
# include <stdlib.h>
typedef struct ele
{ int vno;
struct ele *link;
} ELE;
typedef struct hnode
{ int remainder;
ELE *head;
Struct hnode *next;
} HNODE;
void main()
{ int n, i, box_count, box_volume, *a;
HNODE *box_h, *box_t, *j;
ELE *p, *q;
Printf(“输入箱子容积\n”);
Scanf(“%d”,&box_volume);
Printf(“输入物品种数\n”);
Scanf(“%d”,&n);
A=(int *)malloc(sizeof(int)*n);
Printf(“请按体积从大到小顺序输入各物品的体积：”);
For (i=0;i<n;i++) scanf(“%d”,a+i);
Box_h=box_t=NULL;
Box_count=0;
For (i=0;i<n;i++)
{ p=(ELE *)malloc(sizeof(ELE));
p->vno=i;
for (j=box_h;j!=NULL;j=j->next)
if (j->remainder>=a[i]) break;
if (j==NULL)
{ j=(HNODE *)malloc(sizeof(HNODE));
j->remainder=box_volume-a[i];
j->head=NULL;
if (box_h==NULL)
box_h=box_t=j;
else box_t=boix_t->next=j;
j->next=NULL;
box_count++;
}
else j->remainder-=a[i];
for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);
if (q==NULL)
{ p->link=j->head;
j->head=p;
}
else
{ p->link=NULL;
q->link=p;
}
}
printf(“共使用了%d只箱子”，box_count);
printf(“各箱子装物品情况如下：”);
for (j=box_h,i=1;j!=NULL;j=j->next,i++)
{ printf(“第%2d只箱子，还剩余容积%4d，所装物品有；
\n”,I,j->remainder);
for (p=j->head;p!=NULL;p=p->link)
printf(“%4d”,p->vno+1);
printf(“\n”);
}
}
【问题】 马的遍历
问题描述：在8×8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一
格并且只经过一次的一条路径。
马在某个方格，可以在一步内到达的不同位置最多有8个，如图所示。如用二
维数组board[ ][ ]表示棋盘，其元素记录马经过该位置时的步骤号。另对马的8种可能
走法（称为着法）设定一个顺序，如当前位置在棋盘的（i，j）方格，下一个可能的位
置依次为（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-
1）、（i-1，j-2）、（i+1，j-2）、（i+2，j-1），实际可以走的位置尽限于还未走过
的和不越出边界的那些位置。为便于程序的同意处理，可以引入两个数组，分别存储各
种可能走法对当前位置的纵横增量。
4 3
5 2
马
6 1
7 0
对于本题，一般可以采用回溯法，这里采用Warnsdoff策略求解，这也是一种
贪婪法，其选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位
置。如马的当前位置（i，j）只有三个出口，他们是位置（i+2，j+1）、（i-2，j+1）
和（i-1，j-2），如分别走到这些位置，这三个位置又分别会有不同的出口，假定这三
个位置的出口个数分别为4、2、3，则程序就选择让马走向（i-2，j+1）位置。
由于程序采用的是一种贪婪法，整个找解过程是一直向前，没有回溯，所以
能非常快地找到解。但是，对于某些开始位置，实际上有解，而该算法不能找到解。对
于找不到解的情况，程序只要改变8种可能出口的选择顺序，就能找到解。改变出口选择
顺序，就是改变有相同出口时的选择标准。以下程序考虑到这种情况，引入变量start，
用于控制8种可能着法的选择顺序。开始时为0，当不能找到解时，就让start增1，重新
找解。细节以下程序。
【程序】
# include <stdio.h>
int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];
int exitn(int i,int j,int s,int a[ ])
{ int i1,j1,k,count;
for (count=k=0;k<8;k++)
{ i1=i+delta_i[(s+k)%8];
j1=i+delta_j[(s+k)%8];
if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)
a[count++]=(s+k)%8;
}
return count;
}
int next(int i,int j,int s)
{ int m,k,mm,min,a[8],b[8],temp;
m=exitn(i,j,s,a);
if (m==0) return –1;
for (min=9,k=0;k<m;k++)
{ temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
if (temp<min)
{ min=temp;
kk=a[k];
}
}
return kk;
}
void main()
{ int sx,sy,i,j,step,no,start;
for (sx=0;sx<8;sx++)
for (sy=0;sy<8;sy++)
{ start=0;
do {
for (i=0;i<8;i++)
for (j=0;j<8;j++)
board[i][j]=0;
board[sx][sy]=1;
I=sx; j=sy;
For (step=2;step<64;step++)
{ if ((no=next(i,j,start))==-1)
break;
I+=delta_i[no];
j+=delta_j[no];
board[i][j]=step;
}
if (step>64) break;
start++;
} while(step<=64)
for (i=0;i<8;i++)
{ for (j=0;j<8;j++)
printf(“%4d”,board[i][j]);
printf(“\n\n”);
}
scanf(“%*c”);
}
}
七、分治法
1、分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，
越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1
时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，
…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时
是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问
题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题
的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问
题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，
可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接
求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在
算法设计之中，并由此产生许多高效算法。
2、分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问
题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问
题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足
的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问
题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可
以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立
的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，
但一般用动态规划法较好。
3、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide_and_Conquer（P）
if |P|≤n0
then return（ADHOC（P））
将P分解为较小的子问题P1、P2、…、Pk
for i←1 to k
do
yi ← Divide-and-Conquer（Pi） △ 递归解决Pi
T ← MERGE（y1，y2，…，yk） △ 合并子问题
Return（T）
其中 |P| 表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易
直接解出，不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规
模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC（P）求解。
算法MERGE（y1，y2，…，yk）是该分治法中的合并子算法，用于将P的子问题P1、P2、
…、Pk的相应的解y1、y2、…、yk合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应
该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治
法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k
个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的
做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方
法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没
有统一的模式，需要具体问题具体分析。
【问题】 大整数乘法
问题描述：
通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，
即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的
常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在
某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处
理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到
限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必
须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来
设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1
位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面
我们用分治法来设计一个更有效的大整数乘积算法。
图6-3 大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的
幂），如图6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
如果按式（1）计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3
次不超过n位的整数加法（分别对应于式（1）中的加号），此外还要做2次移位（分别对
应于式（1）中乘2n和乘2n/2）。所有这些加法和移位共用O（n）步运算。设T（n）是2
个n位整数相乘所需的运算总数，则由式（1），我们有：
（2）
由此可得T（n）=O（n2）。因此，用（1）式来计算X和Y的乘积并不比小学生的方法更有
效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
虽然，式（3）看起来比式（1）复杂些，但它仅需做3次n/2位整数的乘法（AC，BD和
（A-B）（D-C）），6次加、减法和2次移位。由此可得：
（4）
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式（3），并
考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}
begin
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左边n/2位;
B=X的右边n/2位;
C=Y的左边n/2位;
D=Y的右边n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次
数。
【问题】 最接近点对问题
问题描述：
在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何
对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题
中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这
个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着
重考虑平面上的最接近点对问题。
最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点的所有点
对中，该点对的距离最小。
严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，
找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。我们
能否找到问题的一个O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的
集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接
近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最
接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最
接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。
但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构
成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此
思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：
T(n)=2T(n/2)+O(n2)
它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递
归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在
合并步骤上。
为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的
n个实数x1、x2、…、xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可
以先将x1、x2、…、xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方
法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这
种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分
治法来求解，并希望能推广到二维的情形。
假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S
| x>m}。这样一来，对于所有p∈S1和q∈S2有p<q。
递归地在S1和S2上找出其最接近点对{p1，p2}和{q1，q2}，并设δ=min{|p1-p2|，|q1-
q2|}，S中的最接近点对或者是{p1，p2}，或者是{q1，q2}，或者是某个{p3，q3}，其中
p3∈S1且q3∈S2。如图1所示。
图1 一维情形的分治法
我们注意到，如果S的最接近点对是{p3，q3}，即 | p3-q3 | < δ，则p3和q3两者与m的
距离不超过δ，即 | p3-m | < δ，| q3-m | < δ，也就是说，p3∈(m-δ，m)，q3∈(m
，
m+δ)。由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于
δ），并且m是S1和S2的分割点，因此(m-δ，m)中至多包含S中的一个点。同理，(m，m+δ
)
中也至多包含S中的一个点。由图1可以看出，如果(m-δ，m)中有S中的点，则此点就是S1
中最大点。同理，如果(m，m+δ)中有S中的点，则此点就是S2中最小点。因此，我们用线
性时间就能找到区间(m-δ，m)和(m，m+δ)中所有点，即p3和q3。从而我们用线性时间就
可以将S1的解和S2的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时
间内完成。这样是否就可以得到一个有效的算法了呢？
还有一个问题需要认真考虑，即分割点m的选取，及S1和S2的划分。选取分割点m的一个
基本要求是由此导出集合S的一个线性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1 {x | x≤
m}；S2 {x | x>m}。容易看出，如果选取m=[max（S）+min（S）]/2，可以满足线性分割
的要求。选取分割点后，再用O(n)时间即可将S划分成S1={x∈S | x≤m}和S2={x∈S |
x>m}。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏
情况下，|S1|=1，|S2|=n-1，由此产生的分治法在最坏情况下所需的计算时间T（n）应
满足递归方程：
T（n）=T（n-1）+O（n）
它的解是T（n）=O（n2）。这种效率降低的现象可以通过分治法中“平衡子问题”的方
法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和S2中有大致相等个数的
点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的
选取中位数的线性时间算法使我们可以在O（n）时间内确定一个平衡的分割点m。
至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法pair如下。
Float pair（S）;
{ if | S | =2 δ= | x[2]－x[1] | /*x[1..n]存放
的是S中n个点的坐标*/
else
{ if ( | S | =1) δ=∞
else
{ m=S中各点的坐标值的中位数;
构造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
δ1=pair(S1);
δ2=pair(S2);
p=max(S1);
q=min(S2);
δ=min(δ1，δ2，q-p);
}
return(δ);
}
由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计
算时间T(n)满足递归方程：
解此递归方程可得T(n)=O(nlogn)。
【问题】循环赛日程表
问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日
程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能参赛一次；
（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入
第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个
选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下
两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以
了。
1 2
3 4 5 6 7
1 2 3
4 5 6 7 8
2 1 4
3 6 7 8 5
3 4 1
2 7 8 5 6
1 2
3 4 3 2
1 8 5 6 7
1 2 3
4 5 6 7
8 1 4 3 2
1 2 1 4
3 6 5 8
7 2 1 4 3
1 2 3 4 1
2 7 8 5
6 3 2 1 4
2 1 4 3 2
1 8 7 6
5 4 3 2 1
（1） （2） （3）
图1 2个、4个和8个选手的比赛日程表
图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别
为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按
其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样
我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将
这个比赛日程表推广到具有任意多个选手的情形。
八、动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子
问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，
问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解
有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先
用实例说明动态规划方法的使用。
【问题】 求两字符序列的最长公共字符子序列
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个
字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，
xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列
<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=
“ABCBDAB”，Y=“BCDB”是X的一个子序列。
给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求
已知两序列A和B的最长公共子序列。
如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子
序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，
b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以
下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，
…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，
a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，
a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，
a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则
要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公
共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序
列，再取两者中较长者作为A和B的最长公共子序列。
定义c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的
长度，计算c[i][j]可递归地表述如下：
（1）c[i][j]=0
如果i=0或j=0；
（2）c[i][j]= c[i-1][j-1]+1 如果I，j>0，
且a[i-1]=b[j-1]；
（3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖
于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过
程，逆向构造出最长公共子序列。细节见程序。
# include <stdio.h>
# include <string.h>
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[i][0]=0;
for (i=0;i<=n;i++) c[0][i]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[i][j]==c[i-1][j]) i--;
else if (c[i][j]==c[i][j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (“Enter two string（<%d）!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
1、动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划
也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
（1）最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，
对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最
优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
图2
例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最
优路线。这可用反证法证明：假设有另一路径J’是B到C的最优路径，则A到C的路线取I
和J’比I和J更优，矛盾。从而证明J’必是B到C的最优路径。
最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用
动态规划方法计算。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题
的基本方法。
（2）无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态
无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过
去历史的一个完整总结。这就是无后向性，又称为无后效性。
（3）子问题的重叠性
动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是
一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所
以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上
可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。
所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不
是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比
就不具备优势。
2、动态规划的基本思想
前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状
态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题
时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问
题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题
可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足
最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小
的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的
算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相
似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依
赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向
下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子
子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成
问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪
心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，
重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多
种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若
存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求
解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些
子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解
作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要
重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题
呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到
时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
3、动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶
段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出
来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移
有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所
以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来
做，根据相邻两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表
达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规
划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规
划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的
框架如下：
标准动态规划的基本框架
1. 对fn+1(xn+1)初始化; {边界条件}
for k:=n downto 1 do
for 每一个xk∈Xk do
for 每一个uk∈Uk(xk) do
begin
5. fk(xk):=一个极值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {状态转移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
end;
9. t:=一个极值; {∞或－∞}
for 每一个x1∈X1 do
11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}
12. 输出t;
但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进
行：
（1）分析最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）
可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）
中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快
速地构造出一个最优解。
【问题】 凸多边形的最优三角剖分问题
问题描述：多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾
相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的
连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该
多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点
构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形
的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。
也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形
的内部或边界上。
通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=<v0，v1，…，vn-1>表示
具有n条边v0v1，v1v2，…，vn-1vn的一个凸多边形，其中，约定v0=vn 。
若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形
分割成凸的两个子多边形<vi，vi+1，…，vj>和<vj，vj+1，…，vi>。多边形的三角剖
分是一个将多边形分割成互不重迭的三角形的弦的集合T。图1是一个凸多边形的两个不
同的三角剖分。
(a) (b)
图1 一个凸多边形的2个不同的三角剖分
在凸多边形P的一个三角剖分T中，各弦互不相交且弦数已达到最大，即P的任一不在T中
的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角刮分中，恰好有n-3条弦和
n-2个三角形。
凸多边形最优三角剖分的问题是：给定一个凸多边形P=<v0，v1，…，vn-1>以及定义在
由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使
得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数ω。例如：定义ω(△vivjvk)=| vivj |+| vivk |+|
vkvj |，其中，| vivj |是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为
最小弦长三角剖分。
（1）最优子结构性质
凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸（n+1）边形P=<v0，
v1 ，…，vn>的一个最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分
权的和，即三角形v0vkvn的权，子多边形<v0，v1，…，vk>的权和<vk，vk+1，…，vn>
的权之和。可以断言由T所确定的这两个子多边形的三角剖分也是最优的，因为若有
<v0，v1，…，vk>或<vk，vk+1，…，vn>的更小权的三角剖分，将会导致T不是最优三角
剖分的矛盾。
（2）最优三角剖分对应的权的递归结构
首先，定义t[i，j]（1≤i<j≤n）为凸子多边形<vi-1，vi，…，vj>的最优三角剖分所
对应的权值，即最优值。为方便起见，设退化的多边形<vi-1，vi>具有权值0。据此定
义，要计算的凸（n+1）边多边形P对应的权的最优值为t[1，n]。
t[i，j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0，
所以t[i，i]=0，i=1，2，…，n 。当j一i≥1时，子多边形<vi-1，vi，…，vj>至少有3
个顶点。由最优于结构性质，t[i，j]的值应为t[i，k]的值加上t[k+1，j]的值，再加上
△vi-1vkvj的权值，并在i≤k≤j-1的范围内取最小。由此，t[i，j]可递归地定义为：
（3）计算最优值
下面描述的计算凸（n+1）边形P=<v0，v1，…，vn>的三角剖分最优权值的动态规划算法
MINIMUM_WEIGHT，输入是凸多边形P=<v0，v1，…，vn>的权函数ω，输出是最优值t[i，
j]和使得t[i，k]+t[k+1，j]+ω（△vi-1vkvj）达到最优的位置（k=）s[i，j]，1≤i≤j
≤n 。
Procedure MINIMUM_WEIGHT(P，w)；
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q<t[i,j] then
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_占用θ(n2)空间，耗时θ(n3)。
（4）构造最优三角剖分
如我们所看到的，对于任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在计算每一个子多边形
<vi-1，vi，…，vj>的最优三角剖分所对应的权值t[i，j]的同时，还在s[i，j]中记录
了此最优三角剖分中与边（或弦）vi-1vj构成的三角形的第三个顶点的位置。因此，利
用最优子结构性质并借助于s[i，j]，1≤i≤j≤n ，凸（n+l）边形P=<v0，v1，…，vn>
的最优三角剖分可容易地在Ο(n)时间内构造出来。
习题：
1、汽车加油问题：
设有路程长度为L公里的公路上，分布着m个加油站，它们的位置分别为p[i]（i=1，2，
……，m），而汽车油箱加满油后（油箱最多可以加油k升），可以行驶n公里。设计一个
方案，使汽车经过此公路的加油次数尽量少（汽车出发时是加满油的）。
2、最短路径：
设有一个网络，要求从某个顶点出发到其他顶点的最短路径
3、跳马问题：
在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过
一次的一条路径。
4、二叉树的遍历
5、背包问题
6、用分治法实现两个大整数相乘
7、设x1，x2，…，xn是直线上的n个点，若要用单位长度的闭区间去覆盖这n个点，至少
需要多少个这样的单位闭区间？
8、用关系“＜”和“＝”将3个数A、B和C依次排列时，有13种不同的序关系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要将n个数依序进行排列，试设计一个动态规划算法，计算出有多少钟不同的序关系。
9、有一种单人玩的游戏：设有n(2<=n<=200)堆薄片，各堆顺序用0至 n-1编号，极端情
况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到
该堆的相邻堆上。如指定
I堆k张 k 移到I-1(I>0)堆，和将k 张薄片移至I+1(I<n-1)堆。所以当有两个堆与 I 堆
相邻 时，I堆原先至少有2k 张薄片；只有一个堆与 I 堆相邻 时， I 堆原先至少有k张
薄片。
游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使 各
堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估
算：
设
ci:I堆的薄片数(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片数；
ai:I堆的相邻堆可以从I堆得到的薄片数。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
这里并不希望准确地求出A0 至an-1，而是作以下处理：若令 a0 为0，能按上述算式计
算出 A1至 an-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去的
薄片数大于等于0。
实际操作采用以下贪心策略：
（1）每次从第一堆出发顺序搜索每一堆，若发现可从 I堆移走薄片，就完成一次移动。
即， I堆的相邻堆从 I堆取走 ai片薄片。可从I 堆移薄片到相邻堆取于 I堆薄片数：
若I 堆是处于两端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中间堆，则要求
ci>=2ai。
（2）因在ai>0的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数
也最多。在用策略（1）搜索移动时，当发生没有满足条件（1）的可移走薄片的堆时，
采用本策略，让在ai>0的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。
--
╔═══════════════════╗
║★★★★★友谊第一 比赛第二★★★★★║
╚═══════════════════╝
※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.162]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：205.276毫秒