图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

此新闻共有11页 上一页 1 2 3 4 5 6 7 8 9 10 11 下一页