1
第 10章 算法优化策略
2
算法设计策略的比较与选择
3
最大子段和问题给定由 n个整数 (可能为负整数 )组成的序列 a1,a2,…,a n,
求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为,
例如,
A=(-2,11,-4,13,-5,-2)
最大子段和为
j
ik
ka
j
ik
knji a1m a x,0m a x
20
4
2
k
ka
4
简单算法public static int maxSum()
{
int n=a.length-1;
int sum=0;
for (int i=1;i<=n;i++) {
int thissum=0;
for (int j=i;j<=n;j++) {
for (int k=i;k<=j;k++) thissum+=a[k];
if (thissum>sum) {
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
thissum+=a[j];
注意到,则可将算法中的最后一个 for循环省去，避免重复计算只需要 O(n2)的计算时间。
1j ik kj ik jk aaa
5
分治算法如果将所给的序列 a[1:n]分为长度相等的 2段 a[1:n/2]和
a[n/2+1:n]，分别求出这 2段的最大子段和，则 a[1:n]的最大子段和有 3种情况。
(1)a[1:n]的最大子段和与 a[1:n/2]最大子段和相同；
(2)a[1:n]的最大子段和与 a[n/2+1:n]最大子段和相同；
(3)a[1:n]的最大子段和为,且 1≤i≤n/2,n/2+1≤j≤n。
对于情形 (3)。容易看出,a[n/2]与 a[n/2+1]在最优子序列中。因此，可以在 a[1:n/2]中计算出,并在
a[n/2+1:n]中计算出 。则 s1＋ s2即为出现情形 (3)时的最优值。据此可设计出求最大子段和的分治算法。
j
ik
ka
2/2/1 ][m ax1 n ikni kas
inknin kas 12/12/ ][m a x2
复杂度分析
T(n)=O(nlogn)
cn
cn
nOnT
OnT
)()2/(2
)1()(
6
动态规划算法记,1? j?n，则所求的最大子段和为当 b[j-1]>0时 b[j]=b[j-1]+a[j]，否则 b[j]=a[j]。由此可得计算 b[j]的动态规划递归式
}][{m a x][ 1?
j
ikji
kajb
][m a x][m a xm a x][m a x 1111 jbkaka njj
ikjinj
j
iknji
b[j]=max{b[j-1]+a[j],a[j]},1? j?n
算法显然需要 O(n)计算时间和 O(n)空间。
public static int maxSum()
{
int n=a.length-1;
int sum=0,
b=0;
for (int i=1;i<=n;i++) {
if (b>0) b+=a[i];
else b=a[i];
if (b>sum)sum=b;
}
return sum;
}
7
最大子矩阵和问题记最大子矩阵和问题的最优值为由于其中，
设,则给定一个 m行 n列的整数矩阵 a，试求矩阵 a的一个子矩阵，使其各元素之和为最大。
2
1
2
1
]][[)2,1,2,1(
i
ii
j
jj
jiajjiis
)2,1,2,1(m a x
211 211
jjiis
njj mii
)2,1(m a x)}2,1,2,1(m a x{m a x)2,1,2,1(m a x 211211211
211 211
iitjjiisjjiis miinjjmii
njj mii
2 1 2 1211211 ]][[m a x)2,1,2,1(m a x)2,1( j jj i iinjjnjj jiajjiisiit
21 ]][[][ i ii jiajb?
2
1211
][m a x)2,1( j
jjnjj
jbiit
由于解最大子段和问题的动态规划算法需要时间 O(n)，故算法的双重 for循环需要计算时间 O(m2n)。
8
最大 m子段和问题给定由 n个整数 (可能为负整数 )组成的序列 a1,a2,…,an,以及一个正整数 m，要求确定序列的 m个不相交子段，使这 m个子段的总和达到最大。
设 b(i,j)表示数组 a的前 j项中 i个子段和的最大值，且第 i个子段含 a[j](1? i?m,i? j?n)。则所求的最优值显然为与最大子段和问题类似地，计算 b(i,j)的递归式为初始时,b(0,j)=0,(1?j?n);b(i,0)=0,(1? i?m)。
),(m ax jmbnjm
),1(]}[),1(m a x],[)1,(m a x {),( 1 njimijatibjajibjib jti
优化：注意到在上述算法中，计算 b[i][j]时只用到数组 b的第 i-1
行和第 i行的值。因而算法中只要存储数组 b的当前行，不必存储整个数组。另一方面,b(i-1,t)的值可以在计算第 i-1行时预先计算并保存起来。计算第 i行的值时不必重新计算，节省了计算时间和空间。
9
动态规划加速原理四边形不等式
10
货物储运问题在一个铁路沿线顺序存放着 n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的
2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，
使总运输费用最少。
设合并 a[i:j],1≤i≤j≤n，所需的最少费用为 m[i,j]，则原问题的最优值为 m[1,n]。由最优子结构性质可知，
ji
ji
tajkmkimjim
j
itjki
]}[],[]1,[{m i n
0
],[
根据递归式，按通常方法可设计计算 m(i,j)的 O(n3)动态规划算法
11
四边形不等式
ji
ji
jkmkimjiwjim jki?
]},[]1,[{m in),(
0],[
货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。
对于,当函数 w(i,j)满足时称 w满足 四边形不等式 。
当函数 w(i,j)满足时称 W关于区间包含关系单调对于满足四边形不等式的单调函数 w，可推知由递归式定义的函数 m(i,j)也满足四边形不等式，即
)',(),'()','(),( jiwjiwjiwjiw
'' jjii
)',(),'( jiwjiw?
)',(),'()','(),( jimjimjimjim
12
四边形不等式定义由函数 m(i,j)的四边形不等式性质可推出函数 s(i,j)的单调性，即根据前面的讨论，当 w是满足四边形不等式的单调函数时，函数 s(i,j)单调，从而
)},(),()1,(),(|m a x {),( jiwjkmkimjimkjis
s(i,j)? s(i,j+1)? s(i+1,j+1),i? j
)},()1,({m in)},()1,({m in ),1()1,( jkmkimjkmkim jiskjisjki
改进后算法 speedDynamicProgramming所需的计算时间为
)(
)),1(),((
)1,(),1(1
2
1
0
1
0
1
0 1
nO
nO
rsnrnsrnO
riisriisO
n
r
n
r
n
r
rn
i
13
问题的算法特征
14
贪心策略
采用每次合并集装箱数最少的相邻 2堆货物的贪心策略，并不能得到最优解。
适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。
最小相容结点对 a[i]和 a[j] 是满足下面条件的结点对：
（ 1）结点 a[i]和 a[j] 之间没有方形结点；
（ 2）在所有满足条件（ 1）的结点中 a[i]+a[j]的值最小；
（ 3）在所有满足条件（ 1）和（ 2）的结点中下标 i 最小；
（ 4）在所有满足条件（ 1）（ 2）和（ 3）的结点中下标 j 最小。
相应的最小相容合并树，如图所示。
15
相同层序定理相同层序定理,存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。
根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。
16
算 法
1,组合阶段,将给定的 n个数作为方形结点依序从左到右排列，
a[1],a[2],…,a[n]。反复删除序列中最小相容结点对 a[i]和 a[j]，
(i<j)，并在位置 i处插入值为 a[i]+a[j]的圆形结点，直至序列中只剩下 1个结点。 O(nlogn)
2,标记层序阶段,将第一阶段结束后留下的惟一结点标记为第 0
层结点。然后以与第一阶段相反的组合顺序标记其余结点的层序。 O(n)
3,重组阶段,根据标记层序阶段计算出的各结点的层序，按下述规则重组。 O(n)
结点 a[i]和 a[j]重组为新结点应满足：
（ 1） a[i]和 a[j]在当前序列中相邻；
（ 2） a[i]和 a[j]均为当前序列中最大层序结点；
（ 3）在所有满足条件（ 1）和（ 2）的结点中，下标 i 最小。
17
优化数据结构
18
带权区间最短路问题
S是直线上 n个带权区间的集合。从区间 I?S到区间 J?S的一条路是 S的一个区间序列 J(1),J(2),…,J(k)，其中 J(1) = I,J(k) =
J，且对所有 1? i? k-1,J(i)与 J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从 I到 J的路中，路长最短的路称为从 I
到 J的最短路。 带权区间图的单源最短路问题要求计算从 S中一个特定的源区间到 S中所有其他区间之间的最短路。
区间集 S(i)的扩展 定义为,S(i)?T，其中 T是满足下面条件的另一区间集。 T中任意区间 I=[a,b]均有 b>b(i)。
设区间 I(k)( k?i )是区间集 S(i)中的一个区间,1? i? n。如果对于
S(i)的任意扩展 S(i)?T，当区间 J?T且在 S(i)?T中有从 I(1)到 J的路时，在 S(i)?T中从 I(1)到 J的任一最短路都不含区间 I(k)，则称区间 I(k)是 S(i)中的 无效区间 。若 S(i)中的区间 I(k)不是无效区间则称其为 S(i)中的 有效区间 。
19
带权区间最短路问题性质 1,区间 I(k)是 S(i)中的有效区间，则对任意 k?j?i，区间 I(k)
是 S(j)中的有效区间。另一方面，若区间 I(k)是 S(i)中的无效区间，
则对任意 j>i，区间 I(k)是 S(j)中的无效区间。
性质 2,集合 S(i)中所有有效区间的并覆盖从 a(1)到 b(j)的线段，
其中 b(j)是 S(i)的最右有效区间的右端点。
性质 3,区间 I(i)是集合 S(i)中的有效区间当且仅当在 S(i)中有一条从 I(1)到 I(i)的路。
性质 4,当 i>k且 dist(i,i)<dist(k,i)时,I(k)是 S(i)中的无效区间。
性质 5,设 I(j(1)),I(j(2)),…,I(j(k))是 S(i)中的有效区间，且
j(1)<j(2)<…<j(k)?i，则 dist(j(1),i)? dist(j(2),i)?…? dist(j(k),i)。
性质 6,如果区间 I(i)包含区间 I(k)（因此 i>k），且
dist(i,i)<dist(k,i)，则 I(k)是 S(i)中的无效区间。
性质 7,当 i>k且 dist(i,i)<dist(k,i-1)时,I(k)是 S(i)中的无效区间。
性质 8,如果区间 I(k)(k>1)不包含 S(k-1)中任一有效区间 I(j)的右端点 b(j)，则对任意 i?k,I(k)是 S(i)中的无效区间。
20
带权区间图的最短路算法算法 shortestIntervalPaths
步骤 1,dist(1,1)←w(1) ；
步骤 2：
for (i=2;i<=n;i++){
(2.1),
j=min{ k | a(i)<b(k);1?k<i };
if (j不存在 ) dist(i,i)←+∞;
else dist(i,i)←dist(j,i -1)+w(i);
(2.2),
for (k<i){
if (dist(i,i)<dist(k,i-1)) dist(k,i)←+∞;
else dist(k,i)←dist(k,i -1);
}
}
步骤 3：
for (i=2;i<=n;i++){
if (dist(i,n)=+∞) {
j=min{ k |
(dist(k,n)<+∞)&&(a(i)<b(k)) };
dist(i,n)=dist(j,n)+w(i);
}
}
上述算法的关键是有效地实现步骤 (2.1)和 (2.2)
21
实现方案 1
用一棵平衡搜索树（ 2-3树）存储当前区间集 S(i)中的有效区间。
以区间的右端点的值为序。如图所示。
(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，
在最坏情况下需要时间 O(logn)。
(2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间 O(logn)。
综上，算法 shortestIntervalPaths用平衡搜索树的实现方案，
在最坏情况下的计算时间复杂性为 O(nlogn)。
22
实现方案 2
采用并查集结构。用整数 k表示区间 I(k),1?k?n。初始时每个元素 k构成一个单元素集，即集合 k是 {k},1?k?n。
(1)每个当前有效区间 I(k)在集合 k中。
(2)对每个集合 S(i)，设
L(S(i))={I(k)|I(k)是 S(i)的无效区间，且 I(k)与 S(i)的任一有效区间均不相交 },L(S(i))中所有区间均位于 S(i)的所有有效区间并的右侧。
(3)用一个栈 AS存放当前有效区间 I(i(1)),I(i(2)),…,I(i(k))。
I(i(k))是栈顶元素。该栈称为当前有效区间栈。
(4)对于 1?k?n，记 prev(I(k))=min{j|a(k)<b(j)}。对给定的区间序列做一次线性扫描确定 prev(I(k))的值。
(5)对于当前区间集 S(i)，用一维数组 dist记录 dist(j,i)的值。
(6)用 dist[k]=-1标记区间 I(k)为无效区间。
在最坏情况下，算法需要 计算时间,其中 是单变量 Ackerman函数的逆函数
))(( nnO? )(n?
23
优化搜索策略
24
最短加法链问题给定一个正整数和一个实数，如何用最少的乘法次数计算出 xn。
例如，可以用 6次乘法逐步计算 x23如下,x,x2,x3,x5,x10,x20,x23
可以证明计算最少需要 6次乘法。计算的幂序列中各幂次 1,2，
3,5,10,20,23组成了一个关于整数 23的加法链。在一般情况下，计算 xn的幂序列中各幂次组成正整数的一个加法链上述最优求幂问题相应于正整数的最短加法链问题，即求 n的一个加法链使其长度达到最小。正整数的最短加法链长度记为 l(n)。
riijkaaa
naaaa
kji
r
,,2,1,,
1 210
25
回溯法问题的状态空间树如图所示。其中第 i层结点 ai的儿子结点 ai+1>ai
由 aj+ak,k?j?i所构成。
private static void backtrack(int step)
{// 解最短加法链问题的标准回溯法
int i,j,k;
if (a[step]==n) // 找到一条加法链
{
if (step<best) 更新最优值
return;
}
// 对当前结点 a[step]的每一个儿子结点递归搜索
for (i=step;i>=1;i--)
if (2*a[i]>a[step])
for (j=i;j>=1;j--){
k=a[i]+a[j];
a[step+1]=k;
if ((k>a[step])&&(k<=n)) backtrack(step+1);
}
}
由于加法链问题的状态空间树的每一个第 k层结点至少有 k+1个儿子结点，因此从根结点到第 k层的任一结点的路径数至少是 k!。用标准的回溯法只能对较小的构造出最短加法链。
26
迭代搜索法
深度优先搜索,算法所搜索到的第一个加法链不一定是最短加法链。
广度优先搜索,算法找到的第一个加法链就是最短加法链，但这种方法的空间开销太大。
迭代搜索算法,既能保证算法找到的第一个加法链就是最短加法链，又不需要太大的空间开销。其基本思想是控制回溯法的搜索深度 d，从 d=1开始搜索，每次搜索后使 d增 1，加深搜索深度，
直到找到一条加法链为止。
private static void iterativeDeepening()
{// 逐步深化的迭代搜索算法
best=n+1;
found=false;
lb=2; // 初始迭代搜索深度
while (!found){
a[1]=1;
backtrack(1);
lb++; // 加深搜索深度
}
}
对于正整数，记?(n)=?logn?，
v(n)=n的 2进制表示中 1的个数。
迄今为止所知道的 l(n)的最好下界是 l(n)≥lb(n)=?(n)+?logv(n)?。利用这个下界，可以从深度 lb(n)开始搜索，大大加快了算法的搜索进程。
27
剪枝函数
设 ai和 aj是加法链中的两个元素，且 ai>2maj。由于加倍是加法链中元素增大的最快的方式，即 ai?2ai-1，所以从 aj到 ai至少需要
m+1步。如果预期在状态空间树 T的第 d层找到关于 n的一条加法链，则以状态空间树第 i层结点 ai为根的子树中，可在第 d层找到一条加法链的必要条件是 2d-iai≥n。
当 时，状态空间树中以结点 ai为根的子树中不可能在第 d层之前找到最短加法链。
设在求正整数 n的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为 d。且正整数可表示为 n=2t(2k+1),k>0，则在状态空间树的第 i层结点 ai处的一个剪枝条件是
na iid )2(23
ditd
tdi
dian
dian
i
i
1
20
/lo g
23/lo g
28
最短加法链长的上界与加法链问题密切相关的幂树给出了 l(n)的更精确的上界。
假设已定义了幂树 T的第 k层结点，则 T的第 k+1层结点可定义如下。依从左到右顺序取第 k层结点 ak，定义其按从左到右顺序排列的儿子结点为 ak+aj,0?j?k。其中 a0,a1,…,ak,是从 T
的根到结点 ak的路径。且 ak+aj在 T中未出现过。
含正整数 n的部分幂树 T容易在线性时间内用迭代搜索方式构造出来。
29
优化算法综合前面的讨论，对构造最短加法链的标准回溯法作如下改进。
(1)采用逐步深化迭代搜索策略；
(2)利用 l(n)的下界 lb(n)对迭代深度作精确估计；
(3)采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜索进程；
(4)用幂树构造 l(n)的精确上界 ub(n)。
当 lb(n)=ub(n)时，幂树给出的加法链已是最短加法链。
当 lb(n)<ub(n)时，用改进后的逐步深化迭代搜索算法，从深度 d=lb(n)开始搜索。
第 10章 算法优化策略
2
算法设计策略的比较与选择
3
最大子段和问题给定由 n个整数 (可能为负整数 )组成的序列 a1,a2,…,a n,
求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为,
例如,
A=(-2,11,-4,13,-5,-2)
最大子段和为
j
ik
ka
j
ik
knji a1m a x,0m a x
20
4
2
k
ka
4
简单算法public static int maxSum()
{
int n=a.length-1;
int sum=0;
for (int i=1;i<=n;i++) {
int thissum=0;
for (int j=i;j<=n;j++) {
for (int k=i;k<=j;k++) thissum+=a[k];
if (thissum>sum) {
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
thissum+=a[j];
注意到,则可将算法中的最后一个 for循环省去，避免重复计算只需要 O(n2)的计算时间。
1j ik kj ik jk aaa
5
分治算法如果将所给的序列 a[1:n]分为长度相等的 2段 a[1:n/2]和
a[n/2+1:n]，分别求出这 2段的最大子段和，则 a[1:n]的最大子段和有 3种情况。
(1)a[1:n]的最大子段和与 a[1:n/2]最大子段和相同；
(2)a[1:n]的最大子段和与 a[n/2+1:n]最大子段和相同；
(3)a[1:n]的最大子段和为,且 1≤i≤n/2,n/2+1≤j≤n。
对于情形 (3)。容易看出,a[n/2]与 a[n/2+1]在最优子序列中。因此，可以在 a[1:n/2]中计算出,并在
a[n/2+1:n]中计算出 。则 s1＋ s2即为出现情形 (3)时的最优值。据此可设计出求最大子段和的分治算法。
j
ik
ka
2/2/1 ][m ax1 n ikni kas
inknin kas 12/12/ ][m a x2
复杂度分析
T(n)=O(nlogn)
cn
cn
nOnT
OnT
)()2/(2
)1()(
6
动态规划算法记,1? j?n，则所求的最大子段和为当 b[j-1]>0时 b[j]=b[j-1]+a[j]，否则 b[j]=a[j]。由此可得计算 b[j]的动态规划递归式
}][{m a x][ 1?
j
ikji
kajb
][m a x][m a xm a x][m a x 1111 jbkaka njj
ikjinj
j
iknji
b[j]=max{b[j-1]+a[j],a[j]},1? j?n
算法显然需要 O(n)计算时间和 O(n)空间。
public static int maxSum()
{
int n=a.length-1;
int sum=0,
b=0;
for (int i=1;i<=n;i++) {
if (b>0) b+=a[i];
else b=a[i];
if (b>sum)sum=b;
}
return sum;
}
7
最大子矩阵和问题记最大子矩阵和问题的最优值为由于其中，
设,则给定一个 m行 n列的整数矩阵 a，试求矩阵 a的一个子矩阵，使其各元素之和为最大。
2
1
2
1
]][[)2,1,2,1(
i
ii
j
jj
jiajjiis
)2,1,2,1(m a x
211 211
jjiis
njj mii
)2,1(m a x)}2,1,2,1(m a x{m a x)2,1,2,1(m a x 211211211
211 211
iitjjiisjjiis miinjjmii
njj mii
2 1 2 1211211 ]][[m a x)2,1,2,1(m a x)2,1( j jj i iinjjnjj jiajjiisiit
21 ]][[][ i ii jiajb?
2
1211
][m a x)2,1( j
jjnjj
jbiit
由于解最大子段和问题的动态规划算法需要时间 O(n)，故算法的双重 for循环需要计算时间 O(m2n)。
8
最大 m子段和问题给定由 n个整数 (可能为负整数 )组成的序列 a1,a2,…,an,以及一个正整数 m，要求确定序列的 m个不相交子段，使这 m个子段的总和达到最大。
设 b(i,j)表示数组 a的前 j项中 i个子段和的最大值，且第 i个子段含 a[j](1? i?m,i? j?n)。则所求的最优值显然为与最大子段和问题类似地，计算 b(i,j)的递归式为初始时,b(0,j)=0,(1?j?n);b(i,0)=0,(1? i?m)。
),(m ax jmbnjm
),1(]}[),1(m a x],[)1,(m a x {),( 1 njimijatibjajibjib jti
优化：注意到在上述算法中，计算 b[i][j]时只用到数组 b的第 i-1
行和第 i行的值。因而算法中只要存储数组 b的当前行，不必存储整个数组。另一方面,b(i-1,t)的值可以在计算第 i-1行时预先计算并保存起来。计算第 i行的值时不必重新计算，节省了计算时间和空间。
9
动态规划加速原理四边形不等式
10
货物储运问题在一个铁路沿线顺序存放着 n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的
2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，
使总运输费用最少。
设合并 a[i:j],1≤i≤j≤n，所需的最少费用为 m[i,j]，则原问题的最优值为 m[1,n]。由最优子结构性质可知，
ji
ji
tajkmkimjim
j
itjki
]}[],[]1,[{m i n
0
],[
根据递归式，按通常方法可设计计算 m(i,j)的 O(n3)动态规划算法
11
四边形不等式
ji
ji
jkmkimjiwjim jki?
]},[]1,[{m in),(
0],[
货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。
对于,当函数 w(i,j)满足时称 w满足 四边形不等式 。
当函数 w(i,j)满足时称 W关于区间包含关系单调对于满足四边形不等式的单调函数 w，可推知由递归式定义的函数 m(i,j)也满足四边形不等式，即
)',(),'()','(),( jiwjiwjiwjiw
'' jjii
)',(),'( jiwjiw?
)',(),'()','(),( jimjimjimjim
12
四边形不等式定义由函数 m(i,j)的四边形不等式性质可推出函数 s(i,j)的单调性，即根据前面的讨论，当 w是满足四边形不等式的单调函数时，函数 s(i,j)单调，从而
)},(),()1,(),(|m a x {),( jiwjkmkimjimkjis
s(i,j)? s(i,j+1)? s(i+1,j+1),i? j
)},()1,({m in)},()1,({m in ),1()1,( jkmkimjkmkim jiskjisjki
改进后算法 speedDynamicProgramming所需的计算时间为
)(
)),1(),((
)1,(),1(1
2
1
0
1
0
1
0 1
nO
nO
rsnrnsrnO
riisriisO
n
r
n
r
n
r
rn
i
13
问题的算法特征
14
贪心策略
采用每次合并集装箱数最少的相邻 2堆货物的贪心策略，并不能得到最优解。
适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。
最小相容结点对 a[i]和 a[j] 是满足下面条件的结点对：
（ 1）结点 a[i]和 a[j] 之间没有方形结点；
（ 2）在所有满足条件（ 1）的结点中 a[i]+a[j]的值最小；
（ 3）在所有满足条件（ 1）和（ 2）的结点中下标 i 最小；
（ 4）在所有满足条件（ 1）（ 2）和（ 3）的结点中下标 j 最小。
相应的最小相容合并树，如图所示。
15
相同层序定理相同层序定理,存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。
根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。
16
算 法
1,组合阶段,将给定的 n个数作为方形结点依序从左到右排列，
a[1],a[2],…,a[n]。反复删除序列中最小相容结点对 a[i]和 a[j]，
(i<j)，并在位置 i处插入值为 a[i]+a[j]的圆形结点，直至序列中只剩下 1个结点。 O(nlogn)
2,标记层序阶段,将第一阶段结束后留下的惟一结点标记为第 0
层结点。然后以与第一阶段相反的组合顺序标记其余结点的层序。 O(n)
3,重组阶段,根据标记层序阶段计算出的各结点的层序，按下述规则重组。 O(n)
结点 a[i]和 a[j]重组为新结点应满足：
（ 1） a[i]和 a[j]在当前序列中相邻；
（ 2） a[i]和 a[j]均为当前序列中最大层序结点；
（ 3）在所有满足条件（ 1）和（ 2）的结点中，下标 i 最小。
17
优化数据结构
18
带权区间最短路问题
S是直线上 n个带权区间的集合。从区间 I?S到区间 J?S的一条路是 S的一个区间序列 J(1),J(2),…,J(k)，其中 J(1) = I,J(k) =
J，且对所有 1? i? k-1,J(i)与 J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从 I到 J的路中，路长最短的路称为从 I
到 J的最短路。 带权区间图的单源最短路问题要求计算从 S中一个特定的源区间到 S中所有其他区间之间的最短路。
区间集 S(i)的扩展 定义为,S(i)?T，其中 T是满足下面条件的另一区间集。 T中任意区间 I=[a,b]均有 b>b(i)。
设区间 I(k)( k?i )是区间集 S(i)中的一个区间,1? i? n。如果对于
S(i)的任意扩展 S(i)?T，当区间 J?T且在 S(i)?T中有从 I(1)到 J的路时，在 S(i)?T中从 I(1)到 J的任一最短路都不含区间 I(k)，则称区间 I(k)是 S(i)中的 无效区间 。若 S(i)中的区间 I(k)不是无效区间则称其为 S(i)中的 有效区间 。
19
带权区间最短路问题性质 1,区间 I(k)是 S(i)中的有效区间，则对任意 k?j?i，区间 I(k)
是 S(j)中的有效区间。另一方面，若区间 I(k)是 S(i)中的无效区间，
则对任意 j>i，区间 I(k)是 S(j)中的无效区间。
性质 2,集合 S(i)中所有有效区间的并覆盖从 a(1)到 b(j)的线段，
其中 b(j)是 S(i)的最右有效区间的右端点。
性质 3,区间 I(i)是集合 S(i)中的有效区间当且仅当在 S(i)中有一条从 I(1)到 I(i)的路。
性质 4,当 i>k且 dist(i,i)<dist(k,i)时,I(k)是 S(i)中的无效区间。
性质 5,设 I(j(1)),I(j(2)),…,I(j(k))是 S(i)中的有效区间，且
j(1)<j(2)<…<j(k)?i，则 dist(j(1),i)? dist(j(2),i)?…? dist(j(k),i)。
性质 6,如果区间 I(i)包含区间 I(k)（因此 i>k），且
dist(i,i)<dist(k,i)，则 I(k)是 S(i)中的无效区间。
性质 7,当 i>k且 dist(i,i)<dist(k,i-1)时,I(k)是 S(i)中的无效区间。
性质 8,如果区间 I(k)(k>1)不包含 S(k-1)中任一有效区间 I(j)的右端点 b(j)，则对任意 i?k,I(k)是 S(i)中的无效区间。
20
带权区间图的最短路算法算法 shortestIntervalPaths
步骤 1,dist(1,1)←w(1) ；
步骤 2：
for (i=2;i<=n;i++){
(2.1),
j=min{ k | a(i)<b(k);1?k<i };
if (j不存在 ) dist(i,i)←+∞;
else dist(i,i)←dist(j,i -1)+w(i);
(2.2),
for (k<i){
if (dist(i,i)<dist(k,i-1)) dist(k,i)←+∞;
else dist(k,i)←dist(k,i -1);
}
}
步骤 3：
for (i=2;i<=n;i++){
if (dist(i,n)=+∞) {
j=min{ k |
(dist(k,n)<+∞)&&(a(i)<b(k)) };
dist(i,n)=dist(j,n)+w(i);
}
}
上述算法的关键是有效地实现步骤 (2.1)和 (2.2)
21
实现方案 1
用一棵平衡搜索树（ 2-3树）存储当前区间集 S(i)中的有效区间。
以区间的右端点的值为序。如图所示。
(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，
在最坏情况下需要时间 O(logn)。
(2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间 O(logn)。
综上，算法 shortestIntervalPaths用平衡搜索树的实现方案，
在最坏情况下的计算时间复杂性为 O(nlogn)。
22
实现方案 2
采用并查集结构。用整数 k表示区间 I(k),1?k?n。初始时每个元素 k构成一个单元素集，即集合 k是 {k},1?k?n。
(1)每个当前有效区间 I(k)在集合 k中。
(2)对每个集合 S(i)，设
L(S(i))={I(k)|I(k)是 S(i)的无效区间，且 I(k)与 S(i)的任一有效区间均不相交 },L(S(i))中所有区间均位于 S(i)的所有有效区间并的右侧。
(3)用一个栈 AS存放当前有效区间 I(i(1)),I(i(2)),…,I(i(k))。
I(i(k))是栈顶元素。该栈称为当前有效区间栈。
(4)对于 1?k?n，记 prev(I(k))=min{j|a(k)<b(j)}。对给定的区间序列做一次线性扫描确定 prev(I(k))的值。
(5)对于当前区间集 S(i)，用一维数组 dist记录 dist(j,i)的值。
(6)用 dist[k]=-1标记区间 I(k)为无效区间。
在最坏情况下，算法需要 计算时间,其中 是单变量 Ackerman函数的逆函数
))(( nnO? )(n?
23
优化搜索策略
24
最短加法链问题给定一个正整数和一个实数，如何用最少的乘法次数计算出 xn。
例如，可以用 6次乘法逐步计算 x23如下,x,x2,x3,x5,x10,x20,x23
可以证明计算最少需要 6次乘法。计算的幂序列中各幂次 1,2，
3,5,10,20,23组成了一个关于整数 23的加法链。在一般情况下，计算 xn的幂序列中各幂次组成正整数的一个加法链上述最优求幂问题相应于正整数的最短加法链问题，即求 n的一个加法链使其长度达到最小。正整数的最短加法链长度记为 l(n)。
riijkaaa
naaaa
kji
r
,,2,1,,
1 210
25
回溯法问题的状态空间树如图所示。其中第 i层结点 ai的儿子结点 ai+1>ai
由 aj+ak,k?j?i所构成。
private static void backtrack(int step)
{// 解最短加法链问题的标准回溯法
int i,j,k;
if (a[step]==n) // 找到一条加法链
{
if (step<best) 更新最优值
return;
}
// 对当前结点 a[step]的每一个儿子结点递归搜索
for (i=step;i>=1;i--)
if (2*a[i]>a[step])
for (j=i;j>=1;j--){
k=a[i]+a[j];
a[step+1]=k;
if ((k>a[step])&&(k<=n)) backtrack(step+1);
}
}
由于加法链问题的状态空间树的每一个第 k层结点至少有 k+1个儿子结点，因此从根结点到第 k层的任一结点的路径数至少是 k!。用标准的回溯法只能对较小的构造出最短加法链。
26
迭代搜索法
深度优先搜索,算法所搜索到的第一个加法链不一定是最短加法链。
广度优先搜索,算法找到的第一个加法链就是最短加法链，但这种方法的空间开销太大。
迭代搜索算法,既能保证算法找到的第一个加法链就是最短加法链，又不需要太大的空间开销。其基本思想是控制回溯法的搜索深度 d，从 d=1开始搜索，每次搜索后使 d增 1，加深搜索深度，
直到找到一条加法链为止。
private static void iterativeDeepening()
{// 逐步深化的迭代搜索算法
best=n+1;
found=false;
lb=2; // 初始迭代搜索深度
while (!found){
a[1]=1;
backtrack(1);
lb++; // 加深搜索深度
}
}
对于正整数，记?(n)=?logn?，
v(n)=n的 2进制表示中 1的个数。
迄今为止所知道的 l(n)的最好下界是 l(n)≥lb(n)=?(n)+?logv(n)?。利用这个下界，可以从深度 lb(n)开始搜索，大大加快了算法的搜索进程。
27
剪枝函数
设 ai和 aj是加法链中的两个元素，且 ai>2maj。由于加倍是加法链中元素增大的最快的方式，即 ai?2ai-1，所以从 aj到 ai至少需要
m+1步。如果预期在状态空间树 T的第 d层找到关于 n的一条加法链，则以状态空间树第 i层结点 ai为根的子树中，可在第 d层找到一条加法链的必要条件是 2d-iai≥n。
当 时，状态空间树中以结点 ai为根的子树中不可能在第 d层之前找到最短加法链。
设在求正整数 n的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为 d。且正整数可表示为 n=2t(2k+1),k>0，则在状态空间树的第 i层结点 ai处的一个剪枝条件是
na iid )2(23
ditd
tdi
dian
dian
i
i
1
20
/lo g
23/lo g
28
最短加法链长的上界与加法链问题密切相关的幂树给出了 l(n)的更精确的上界。
假设已定义了幂树 T的第 k层结点，则 T的第 k+1层结点可定义如下。依从左到右顺序取第 k层结点 ak，定义其按从左到右顺序排列的儿子结点为 ak+aj,0?j?k。其中 a0,a1,…,ak,是从 T
的根到结点 ak的路径。且 ak+aj在 T中未出现过。
含正整数 n的部分幂树 T容易在线性时间内用迭代搜索方式构造出来。
29
优化算法综合前面的讨论，对构造最短加法链的标准回溯法作如下改进。
(1)采用逐步深化迭代搜索策略；
(2)利用 l(n)的下界 lb(n)对迭代深度作精确估计；
(3)采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜索进程；
(4)用幂树构造 l(n)的精确上界 ub(n)。
当 lb(n)=ub(n)时，幂树给出的加法链已是最短加法链。
当 lb(n)<ub(n)时，用改进后的逐步深化迭代搜索算法，从深度 d=lb(n)开始搜索。
