算法分析与设计：算法分析与设计2005改1

算法和数据结构 1
算法分析与设计
郭彦宏
2005年改
算法设计与分析 2
程序 =算法 +数据结构
?软件：刻画现实世界，解决现实世界中
的问题
?语言：实现的工具
?算法：解的描述（程序的灵魂）
?数据结构：现实世界的数据模型
?程序 =算法 +数据结构
算法设计与分析 3
算法
?定义
– 为了完成特定任务指令的有穷序列
?好的算法的特性
– 确定性
– 有穷性
– 可行性
– 健壮性
– 输入、效率和存储要求
– 输出
算法设计与分析 4
算法的复杂度与评价
? 时间与空间
? 方法,
1、事后分析
2、事前分析
算法设计与分析 5
几个例子（问题）
? 表达式解释
– 6+5*4=？
? 字符串匹配
– 串,ABCAC”出现在另一个串,ABCABCACAC”的第几个位
置上
? 排序
– 一个序列，如何最快地对其进行排序
? 压缩编码
– AAAABBBCDDE??
? 图的最短路径
– 地理研究中的交通网络
算法设计与分析 6
?A[1…10]={1,3,5,6,7,10,22,27,34,56}
?在 A中搜索 x＝ 22
例 1.1
算法设计与分析 7
算法 1.1
? Linearsearch
? j← 1
? While（ j<n) and (x≠A[ j])
?j ← j+1
? End while
? If x=A[j] then return j else return 0
算法设计与分析 8
例 1.2
template<class T>
int Max(T a[],int n)
{// 寻找 a [ 0, n - 1 ]中的最大元素
int pos = 0;
for (int i = 1; i < n; i++)
if (a[pos] < a[i])
pos = i;
return pos;
}
算法设计与分析 9
?算法 1.2 binarysearch
? low ←1;high ←n;j ←0
? while (low≤high) and (j=0)
? mid ← ? (low+high)/2?
? if x=A[mid] then j ←mid
? else if x<A[mid] then high ←mid -1
? else low ←mid+1
? end while
? return j
二分搜索
算法设计与分析 10
1
10
27 4
5
22 7
8
9
15
23
12
32
35
??Logn ?+1
算法设计与分析 11
合并两个已排列的表
? A=[3,5,7,18,19,46]
? B=[1,4,6,16,17,23,31,45,47]
? C=[ 3,
5,6,7,16,17,18,19,23,31,45,46,47]
1,4,
算法设计与分析 12
? Comment,B [[ p…r ]
? s ←p;t ←q+1;k ←p
? while s ≤q and t ≤r
? if A[s ] ≤A[t ] then
? B[k ] ←A[s ]
? s ←s+1
? else
? B[k ] ←A[t]
? t ←t+1
? end if
? k ←k+1
? end while
? if s=q+1 then B[k…r] ←A[[t…r ]
? else B[k…r] ←A[s…q]
? end if
? A[p…r] ←B[p…r]
算法设计与分析 13
? template<class T> //(C语言）
? void Merge(T c[],T d[],int l,int m,int r)
? {// 把 c [l,m] 和 c [m,r] 归并到 d [l, r] ;,
? int i = l,
? j = m+1,
? k = l;
? while ((i <= m) && (j <= r))
? if (c[i] <= c[j]) d[k++] = c[i++];
? else d[k++] = c[j++];
? if (i > m) for (int q = j; q <= r; q++)
? d[k++] = c[q];
? else for (int q = i; q <= m; q++)
? d[k++] = c[q];
? }
算法设计与分析 14
选择排序
? for i←1 to n -1
? k ←i
? for j ←i+1 to n
? if A[j]<A[k] then k ←j
? end for
? if k≠i then
?end for
算法设计与分析 15
? template<class T> //(C语言）
? void SelectionSort(T a[],int n)
? {// 及时终止的选择排序
? bool sorted = false;
? for (int size = n; !sorted && (size > 1); size- -) {
? int pos = 0;
? sorted = true;
? // 找最大元素
? for (int i = 1; i < size; i++)
? if (a[pos] <= a[i]) pos = i;
? else sorted = false; // 未按序排列
? Swap(a[pos],a[size - 1 ] ) ;
? }
? }
算法设计与分析 16
插入排序
?例如，如果向数组 a[0:5] = [1,2,6,
8,9,11 ]中插入 4，所得到的结果为
a[0:6] = [1,2,4,6,8,9,11 ]。
当我们为新元素找到欲插入的位置时，
必须把该位置右边的所有元素分别向右
移动一个位置。对于本例，需要移动 11,
9,8和 6，并把 4插入到新空出来的位置
a [ 2 ]中。
算法设计与分析 17
插入排序
? for i ←2 to n
? x ←A [i]
? j ←i -1
? while (j>0) and (A [j]>x)
? A[j+1] ←A [j]
? j ←j -1
? end while
? A[j+1] ←x
? end for
算法设计与分析 18
template<class T>
? void Insert(T a[],int n,const T& x)
? {// 向有序数组 a [0, n - 1]中插入元素 x
? int i;
? for (i = n-1; i >= 0 && x < a[i]; i- -)
? a[i+1] = a[i];
? a[i+1] = x;
? }
? template<class T>
? void InsertionSort(T a[],int n)
? {// 对 a [ 0, n-1 ]进行排序
? for (int i = 1; i < n; i++) {
? T t = a[i];
? Insert(a,i,t);
? }
? }
算法设计与分析 19
插入排序
? template<class T>
? void InsertionSort(T a[],int n)
? for (int i = 1; i < n; i++) {
? / /将 a [ i ]插入 a [ 0, i-1 ]
? T t = a[i];
? int j;
? for (j = i-1; j >= 0 && t < a[j]; j- -)
? a[j+1] = a[j];
? a[j+1] = t;
? }
? }
算法设计与分析 20
自底向上合并排序
6 10 9
5
2 5 3 11 4 8 1
5 10 6
3 10 9 6
2 1 8 4 11 3 9
8 4
7
7
7 2 1 11
3 6 5 4 8 11 10 9 7 2 1
1 4 3 2 5 8 7 6 11 10 9
算法设计与分析 21
自底向上合并排序
? t ←1
?while t<n
? s ←t; t ←2s; i ←0
? while i+t≤n
? merge (A,i+1,i+s,i+t)
? i ←i+t
? end while
?If i+s<n then merge (A,i+1,i+s,i+t)
?end while
算法设计与分析 22
n3 n2
nlogn
n
logn
运
行
时
间
输入大小
算法设计与分析 23
时间复杂性
? 定义 1.1
计算总是以一个时间常量为上界
? 定义 1.2
f(n) ＝ O(g(n))
? 定义 1.3
f(n) =Ω(g(n))
? 定义 1.4
f(n)= Θ(g(n)) C )( )( lim ??? ng nfn
)( )( l im ???? ng nfn
0 )( )( lim ??? ng nfn
算法设计与分析 24
s ←
for j ←2 to s
if j 划分 n then return false
end for
return true
? ?n
算法设计与分析 25
– S（ n）
– 空间耗费的度量方法通常定义为,
算法在运行时所占用内存单元的总数
即：存放数据的 变量单元, 程序代码,
工作变量, 常数 以及运行时的 引用型
变量 所占用的空间和 递归栈 空间的总和
举例说明
空间复杂性
算法设计与分析 26
Char 1 - 128 ~ 127
unsigned char 1 0 ~ 255
short 2 -32768~32767
int 2 -32768~32767
unsigned int 2 0~65 535
long 4 - 231~ 231- 1
unsigned long 4 0 ~ 232- 1
float 4 ± 3.4 E± 38
double 8 ± 1.7 E± 308
long double 10 3,4E-4932~1.1E+4932
pointer 2 ( near,_cs,_ds,_es,_ss指针 )
pointer 4 ( far,huge 指针 )
注意：在 32位 Borland C++程序中,int类型的长度为 4
空间复杂性
算法设计与分析 27
空间复杂性
? double a[100];
int maze[rows][cols]
? Rsum(a,n)
Rsum(a,n-1)
Rsum(a,n-2)
,,,
Rsum(a,1)
Rsum(a,0)
算法设计与分析 28
估算运行时间
? count←0
?while n≥1
? for j ←1 to n
? count ←count+1
? end for
? n ←n/2
? end while
? Return count
算法设计与分析 29
估算运行时间
? count←0
? for i ←1 to n
? m ← ?n/i?
? for j ←1 to m
? count ←count+1
? end for
? end for
? Return count
算法设计与分析 30
?count ←0
?for i←1 to n
? j←2
? while j≤n
? j←j 2
? count ←count+1
? end while
? end for
? return count
算法设计与分析 31
? k←
? for j ←1 to k
? sum [j] ←0
? for i ←1 to j 2
? sum [j] ←sum [j]+i
? end for
? end for
?Return sum[1…k]
n
算法设计与分析 32
运算频度
? for i ←2 to n
? x ←A [i]
? k ←modbinaryserch(A[1…i -1],x)
? for j ←i -1 downto k
? A[j+1] ←A [j]
? end for
? A [k] ←x
?End for
算法设计与分析 33
执行步数
? T Sum(T a[],int n) 0 0 0
? { 0 0 0
? T tsum = 0; 1 1 1
? for(int i=0;i<n;i++) 1 n + 1 n + 1
? tsum += a[i]; 1 n n
? return tsum; 1 1 1
? } 0 0 0
?总计 2 n + 3
算法设计与分析 34
? T Rsum(T a[],int n) 0 0 0
? { 0 0 0
? if(n> 0) 1 n + 1 n + 1
? return Rsum(a,n-1) + a[n-1]; 1 n n
? return 0; 1 1 1
? } 0 0 0
?总计 2 n + 2
算法设计与分析 35
运算频度
? prod ←1;sum ←0
?for j ←1 to k
? prod ←prod × A [j]
?end for
?for j ←k+1 to n
? sum ←sum + A [j]
?End for
算法设计与分析 36
? For j ←1 to n
? x ←A [j]
? 将 x加入表中
? if x为偶数 then
? while pred(x）为奇数
? 删除 pred（ x）
? end while
? end if
? End for
算法设计与分析 37
? sum ←0
?for j ←1 to n
? sum ←sum +A [j]
?end for
?Return sum
算法设计与分析 38
? sum ←0
?for j ←1 to n
? sum ←sum + j
?end for
?Return sum
算法设计与分析 39
数学预备知识
? 定理 1
? f(x)单调递增函数，
且 f(x)是整数
? ?? ? ? ? ? ?? ? ? ?
? ? ? ?
? ?? ? ? ?xx
xx
xfxfxfxf
l o gl o g
)()()()(
?
?
?? 且
算法设计与分析 40
数学预备知识
? 定理 2
? 如果把 n个球分别放在 m个盒子
? 1、一个盒子至少装
?
?
? 2、一个盒子至多装
? ?mn /
? ?mn /
算法设计与分析 41
选择排序
? If i<n then
? k←i
? for j ←i+1 to n
? If a[j]<a[k] then k ←j
? End for
? If k≠i then 互换 A[i]和 A[k]
? sort (i+1)
? end if
归纳法
)(
2
)1(
)()(
2
1
1
1
2
0
)1()1(
{
n
nn
jncnc
n
j
n
nnnC
?
?
??? ?
?
?
?
????
算法设计与分析 42
插入排序
? if i >1 then
? x ←A [i]
? sort (i-1)
? j ←i -1
? while (j>0) and (A [j]>x)
? A[j+1] ←A [j]
? j ←j -1
? end while
? A[j+1] ←x
? end if
算法设计与分析 43
插入排序
template<class T>
? void Insert(T a[],int n,const T& x)
? {// 向有序数组 a [0, n - 1]中插入元素 x
? int i;
? for (i = n-1; i >= 0 && x < a[i]; i- -)
? a[i+1] = a[i];
? a[i+1] = x;
? }
? template<class T>
? void InsertionSort(T a[],int n)
? {// 对 a [ 0, n-1 ]进行排序
? for (int i = 1; i < n; i++) {
? T t = a[i];
? Insert(a,i,t);
? }
? }
算法设计与分析 44
基数排序
? 1349,3285,5655,3322,8574
? 3322,8574,3285,5655,1349
? 3322,1349,5655,8574,3285
? 3285,3322,1349,8574,5655
? 1349,3285,3322,5655,8574
算法设计与分析 45
基数排序
? for j ←1 to k
? 准备 10个空表 L0,L1…L 9
? while L非空
? a ←L 中的下一个元素；删除 a
? i ←a 中的第 j位数字；将 a加入表 Li中
? end while
? L ← L 0
? for i ←1 to 9
? L ←L,L i
? end for
? end for
? Return L
)(n?
算法设计与分析 46
整数幂 (EXPREC)
? if m=0 then y ←1
? else
? y ←power(x,)
? y ←y 2
? if m为奇数 then y ←xy
? end if
? return y
? ?2/m
)( lo g n?
算法设计与分析 47
整数幂 (EXP)
? y ←1
? 将 n用二进制数 dkdk-1….d 0
? for y ←k downto 0
? y ←y 2
? if dj =1 then y ←xy
? end for
? return y
)( lo g n?
算法设计与分析 48
Horner 法则采用如下的分解
式计算一个多项式
?Pn(x)=a n xn+a n -1 xn-1+…+a1x+a0
?Pn(x) =(…((( anx + an -1) x +an -2) x
+a n -3 ) x + …) x + a0
算法设计与分析 49
Horner
? p ←a n
? for i ←1 to n
? p ←xp+a n-i
? end for
? return p
算法设计与分析 50
Horner 法则计算多项式
? template <class T>
? T Horner(T coeff[],int n,const T& x)
? { / /计算 n次多项式的值,coeff[0:n]为多
项式的系数
? T value= coeff [ n ] ;
? for( int i = 1; i <= n; i++)
? value = value * x + coeff [ n-i ] ;
? return value;
? }
算法设计与分析 51
生成排序（ 1）
? for j ←1 to n
? p[j] ←j
? end for
? perm 1(1)
算法设计与分析 52
生成排序（ 1,perm 1(m) ）
? if m=n then output P[1…n]
? else
? for j ←m to n
? 互换 P[j]和 P[m]
? perml(m+1)
? 互换 P[j]和 P[m]
? comment,这时 P[m…n]=m,m+1…n
? end for
? end if
算法设计与分析 53
生成排序（ 2 ）
? for j ←1 to n
? p[j] ←0
? end for
? perm 2 (n)
算法设计与分析 54
生成排序（ 2,perm 2(m) ）
? if m=n then output P[1…n]
? else
? for j ←1 to n
? if P[j]=0 then
? P[j] ←m
? perm 2(m-1)
? P[j] ←0
? end if
? end for
? end if
算法设计与分析 55
寻找多数元素
? c ←candidate(1)
? count ←0
? for j ←1 to n
? if A[j]=c then count ←count+1
? end for
? if count> then return c
? else return none
? ?2/m
算法设计与分析 56
寻找多数元素
? j ←m;c ←A[m];count ←1
? while j<n and count>0
? j ←j+1
? if A[j]=c then count ←count+1
? else count ←count -1
? end while
? if j=n then return c
? else return candidate(j+1)
算法设计与分析 57
递归原理
递归是一种把若干类似问题转化成相同的
子问题, 通过对子问题的反复调用以达
到求解的过程 。
主程序
Call A
1,
子程序 A
主程序
Call A
1,
主程序
Call A
1,
主程序
Call B
1,
子程序 A
子程序 A
Call B
2,
子程序 A 子程序 A
子程序 B
Call A
2,
算法设计与分析 58
递归程序
五人的年龄
问第五个人的年龄，说比第四个大 2岁，
每问一个人都比前一个人大 2岁，最后
一个人说 10岁
1)(n 10
1)(n 21)-ag e( n{a g e ( n )
?
???
算法设计与分析 59
递归程序
template<class T>
void age(n)
int n;
{int c;
if(n==1)c=10;
else c=age(n-1)+2
return(c);
}
算法设计与分析 60
递归程序
?求 n!
1)(n 1
1)(n )!1*({!
?
??? nnn
算法设计与分析 61
递归程序
template<class T>
void float fac(n)
{
float f;
if(n<=0)printf(”n<=0,data error!”);
else if(n= =1)f =1;
else f =fac(n-1)*n;
Return(f);
}
算法设计与分析 62
递归算法设计
? Hanoi
0n 0
0n 1)1(2{)(
?
???? nm o ve snm o v e s
算法设计与分析 63
递归算法设计
? void TowersOfHanoi(int n,int x,int y,int
z)
? { //把 n 个碟子从塔 x移动到塔 y，可借助于塔 z
? if (n > 0)
? {
? TowersOfHanoi(n-1,x,z,y);
? cout << "Move top disk from tower " << x
<<" to top of tower " << y << endl;
? TowersOfHanoi(n-l,z,y,x);
? }
? }
算法设计与分析 64
算法思想
?例 6-1 [找出伪币 ] 给你一个装有 16个
硬币的袋子。 16个硬币中有一个是伪造
的，并且那个伪造的硬币比真的硬币要
轻一些。你的任务是找出这个伪造的硬
币。为了帮助你完成这一任务，将提供
一台可用来比较两组硬币重量的仪器，
利用这台仪器，可以知道两组硬币的重
量是否相同。
第六章 分治算法
算法设计与分析 65
算法思想
?例 6-2 [金块问题 ] 有一个老板有一
袋金块。每个月将有两名雇员会因
其优异的表现分别被奖励一个金块。
按规矩，排名第一的雇员将得到袋
中最重的金块，排名第二的雇员将
得到袋中最轻的金块。
算法设计与分析 66
算法思想
?例 6-3 [矩阵乘法 ] 两个 n× n 阶的矩阵 A
与 B的乘积是另一个 n× n 阶矩阵 C,C可
表示为
? C所需要的操作次数为 n3 m+n2 (n- 1) a，
其中 m表示一次乘法,a 表示一次加法
或减法。
?
?
?????
n
k
njnijkBkiAjic
1
1,1),,(*),(),(
算法设计与分析 67
算法思想
?为了得到两个矩阵相乘的分治之算法，
需要,
? 1) 定义一个小问题，并指明小问题是如
何进行乘法运算的；
? 2) 确定如何把一个大的问题划分成较小
的问题，并指明如何对这些较小的问题
进行乘法运算；
? 3) 最后指出如何根据小问题的结果得到
大问题的结果。
算法设计与分析 68
算法思想
? n/2 n/2
n/2
n/2
A1 A2
A3 A4
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
4 3
2 1
4 3
2 1
*
4 3
2 1
CC
CC
BB
BB
AA
AA
算法设计与分析 69
算法思想
? C1＝ A1B1＋ A2B3
? C2＝ A1B2＋ A2B4
? C3＝ A3B1＋ A4B3
? C4＝ A3B2＋ A4B4
?根据上述公式，经过 8次 n/ 2× n/ 2阶矩
阵乘法和 4次 n/ 2× n/ 2阶矩阵的加法，
就可以计算出 A与 B的乘积。
算法设计与分析 70
算法思想
? S t r a s s e n方法得到 7个小矩阵
? D＝ A1（ B2－ B4）
? E＝ A4（ B3－ B1）
? F＝（ A3＋ A4） B1
? G＝（ A1＋ A2） B4
? H＝（ A3－ A1）（ B1＋ B2)
? I＝（ A2－ A4）（ B3＋ B4）
? J＝（ A1＋ A4）（ B1＋ B4）
算法设计与分析 71
算法思想
? C1＝ E＋ I＋ J－ G
? C2＝ D＋ G
? C3＝ E＋ F
? C4＝ D＋ H＋ J－ F
knd
kncnnt
nt ?
??
?,
,)2/(7 2
{)(
算法设计与分析 72
分治法
? x ←A[1];y ←A[1]
? for i ←2 to n
? if A[i]<x then x ←A[i]
? if A[i]>y then y ←A[i]
? end for
? return (x,y)
第六章 分治算法
算法设计与分析 73
minmax
? if high-low=1 then
if a[low]<a[high] then return(A[low],A[high])
else return(A[high],A[low])
end if
else
mid ← ? (low+high)/2?
(x1,y1) ←minmax(low,mid)
(x2,y2) ←minmax(mid+1,high)
x←min{x1,x2}
y ←max{y1,y2}
return (x,y)
end if
第六章 分治算法
算法设计与分析 74
22/3
22)2/(2)2(222...
22)2/(224)4/(4
2)2)4/(2(22)2/(2)(
)(
1
1
12
2111
2
2
1
2)2/(2
{
??
????????
??????
?????
?
?
?
?
?
????
?
?
?
n
nC
nCnC
nCnCnC
nC
k
k
j
jk
kkkk
n
n
nC
K=logn
第六章 分治算法
算法设计与分析 75
算法思想
?例 6-4 [金块问题 ] 用例 6 - 2的算法
寻找 8个金块中最轻和最重金块的
工作可以用图中的二叉树来表示。
算法设计与分析 76
B
b
B
B
a
E
c
F
G
f
G
g d e h
算法设计与分析 77
算法思想
? 1) 从图中的二叉树由根至叶的过程中把
一个大问题划分成许多个小问题，小问
题的大小为 1或 2。
? 2) 比较每个大小为 2的问题中的金块，
确定哪一个较重和哪一个较轻。在节点
D,E,F和 G 上完成这种比较。大小
为 1的问题中只有一个金块，它既是最
轻的金块也是最重的金块。
? 3) 对较轻的金块进行比较以确定哪一个
金块最轻，对较重的金块进行比较以确
定哪一个金块最重。对于节点 A到 C执行
这种比较 。
算法设计与分析 78
算法思想
?找出最小值和最大值的非递归程序
? template<class T>
? bool MinMax(T w[],int n,T& Min,T&
Max)
? {
? if (n < 1) return false;
? if (n == 1) {Min = Max = 0;
? return true;}
? int s;
? if (n % 2) {
算法设计与分析 79
? Min = Max = 0;
? s = 1;}
? else {
? if (w[0] > w[1]) {
? Min = 1;
? Max = 0;}
? else {Min = 0;
? Max = 1;}
? s = 2;}
? for (int i = s; i < n; i += 2) {
算法设计与分析 80
? if (w[i] > w[i+1]) {
? if (w[i] > w[Max]) Max = i;
? if (w[i+1] < w[Min]) Min = i + 1;}
? else {
? if (w[i+1] > w[Max]) Max = i + 1;
? if (w[i] < w[Min]) Min = i;}
? }
? return true;
? }
算法设计与分析 81
二分搜索
? If low >high then return 0
? else
? mid ← ? (low+high)/2?
? if x=A[mid] then return mid
else if x<A[mid] then return
binarysearch(low,mid-1)
? else return binarysearch(mid+1,high)
? end if
第六章 分治算法
算法设计与分析 82
归并排序
?可以运用分治之方法来解决排序问题，
该问题是将 n 个元素排成非递减顺序。
分治之方法通常用以下的步骤来进行排
序算法：若 n 为 1，算法终止；否则，将
这一元素集合分割成两个或更多个子集
合，对每一个子集合分别排序，然后将
排好序的子集合归并为一个集合。
算法设计与分析 83
归并排序
?假设仅将 n 个元素的集合分成两个子集
合。现在需要确定如何进行子集合的划
分。一种可能性就是把前面 n- 1个元素
放到第一个子集中（称为 A），最后一
个元素放到第二个子集里（称为 B）。
按照这种方式对 A递归地进行排序。
算法设计与分析 84
归并排序
?例 6-5 考虑 8个元素，值分别为 [ 1 0,4，
6,3,8,2,5,7 ]。如果选定 k = 2，
则 [ 1 0,4,6,3 ]和 [ 8,2,5,7 ]将被分
别独立地排序。结果分别为 [ 3,4,6,
10 ]和 [ 2,5,7,8 ]。从两个序列的头部
开始归并这两个已排序的序列。元素 2
比 3更小，被移到结果序列； 3与 5进行
比较,3被移入结果序列； 4与 5比较,4
被放入结果序列； 5和 6比较,.。
算法设计与分析 85
归并排序
?如果选择 k= 4，则序列 [ 1 0,4 ]和 [ 6,3,
8,2,5,7 ]将被排序。排序结果分别为
[ 4,1 0 ]和 [ 2,3,5,6,7,8 ]。
?当这两个排好序的序列被归并后，即可
得所需要的排序序列。
算法设计与分析 86
归并排序
? if low<high then
? mid← ? (low+high)/2?
? mergesort(A,low,mid)
? mergesort(A,mid+1,high)
? MERGE(A,low,mid,high)
? end if
第六章 分治算法
算法设计与分析 87
归并排序
? template<class T>
? void sort( T E,int n)
? {
? if (n >= k) {
? i = n/k;
? j = n-i;
? s o r t ( A,i ) ;
? s o r t ( B,j ) ;
? m e rge(A,B,E,i,j,);
? }
? Else
? }
算法设计与分析 88
归并排序
? template<class T>
? M e rgeSort( T a[],int left,int right)
? {
? if (left < right) {
? int i = (left + right)/2;
? MergeSort(a,left,i);
? MergeSort(a,i+1,right);
? Merge(a,b,left,i,right);
? Copy(b,a,left,right); /
? }
? }
算法设计与分析 89
归并排序
? template<class T>
? void MergeSort(T a[],int n)
? {
? T *b = new T [n];
? int s = 1;
? while (s < n) {
? MergePass(a,b,s,n);
? s += s;
? MergePass(b,a,s,n);
? s += s;
? }
? }
算法设计与分析 90
归并排序
? template<class T>
? void MergePass(T x[],T y[],int s,int n)
? {
? int i = 0;
? while (i <= n - 2 * s) {
? Merge(x,y,i,i+s-1,i+2*s-1);
? i = i + 2 * s;
? }
? if (i + s < n) Merge(x,y,i,i+s-1,n-1);
? else for (int j = i; j <= n-1; j++)
? y[j] = x[j];
? }
算法设计与分析 91
? template<class T>
? void Merge(T c[],T d[],int l,int m,int r)
? {// 把 c[l:m]] 和 c[m:r] 归并到 d [ l, r ],
? int i = l,
? j = m+1,
? k = l;
? while ((i <= m) && (j <= r))
? if (c[i] <= c[j]) d[k++] = c[i++];
? else d[k++] = c[j++];
? if (i > m) for (int q = j; q <= r; q++)
? d[k++] = c[q];
? else for (int q = i; q <= m; q++)
? d[k++] = c[q];
? }
算法设计与分析 92
寻找中项和第 k小元素
? 对于给定的 n 个元素的数组 a [ 0, n - 1 ]，要
求从中找出第 k小的元素。当 a [ 0, n - 1 ]被排
序时，该元素就是 a [ k - 1 ]。
? 假设 n = 8，每个元素有两个域 k e y和 I D，其
中 k e y是一个整数,I D是一个字符。
? 假设这 8个元素为 [ ( 1 2,a),( 4,b),( 5,c)，
( 4,d),( 5,e),( 1 0,f),( 2,g),( 2 0,h)],排
序后得到数组 [ ( 2,g),( 4,d),( 4,b),( 5,c)，
( 5,e),( 1 0,f),( 1 2,a),( 2 0,h) ]。
算法设计与分析 93
寻找中项和第 k小元素
? p←high -low+1
? if p<44 then 将 A排序 return（ A[k])
? 令 q← ?p/5?
? 将 q组的每一组单独排序
? mm← select（ M,1,q,）
? 将 A[low…high]
? Case
? End case
? ?2/q
算法设计与分析 94
寻找中项和第 k小元素
? template<class T>
? T Select(T a[],int n,int k)
? {
? if (k < 1 || k > n) throw OutOfBounds();
? return select(a,0,n-1,k);
? }
? template<class T>
? T select(T a[],int l,int r,int k)
? {
? if (l >= r) return a[l];
算法设计与分析 95
? int i = l,
? j = r + 1;
? T pivot = a[l];
? while (true) {
? do {
? i = i + 1;
? } while (a[i] < pivot);
? do {
? j = j - 1;
? } while (a[j] > pivot);
算法设计与分析 96
? if (i >= j) break;
? Swap(a[i],a[j]);
? }
? if (j - l + 1 == k) return pivot;
? a[l] = a[j];
? a[j] = pivot;
? if (j - l + 1 < k)
? return select(a,j+1,r,k-j+l-1);
? else return select(a,l,j-1,k);
? }
算法设计与分析 97
寻找中项和第 k小元素
? 例 6-6 [中间的中间 ] 考察如下情形,r=5,n=27,
并且 a= [ 2,6,8,1,4,1 0,2 0,6,2 2，
11,9,8,4,3,7,8,1 6,11,1 0,8,2，
6,1 5,1,1 2,5,4 ]。这 2 7个元素可以被
分为 6组 [ 2,6,8,1,4 ],[ 1 0,2 0,6,2 2,
11 ],[ 9,8,4,3,7 ],[ 8,1 6,11,1 0,8 ]，
[ 2,6,1 5,1,1 2 ]和 [ 5,4 ]，每组的中间元
? 素分别为 4,11,7,1 0,1 2和 4。 [ 4,11,7,1
0,1 2,4 ]的中间元素为 7。这个中间元素 7被
取为支点元素。
算法设计与分析 98
寻找中项和第 k小元素
? 由此可以得到 l e ft= [ 2,6,1,4,6,4,3,2,
1,5,4 ],m i d d l e= [ 7 ],r i g h t= [ 8,1 0,2
0,2 2,11,9,8,8,1 6,11,1 0,8,6,1 5,1
2 ]。
? 如果要寻找第 k个元素且 k< 1 2，则仅仅需要
在 l e f t中寻找；如果 k= 1 2，则要找的元素就
是支点元素；如果 k> 1 2，则需要检查 r i g h t
中的 1 5个元素。在最后一种情况下，需在 r i
g h t中寻找第 (k- 1 2 )个元素 。
算法设计与分析 99
快速排序
? 分治之方法还可以用于实现另一种完全不同
的排序方法，这种排序法称为快速排序
? （ quick sort）。在这种方法中,n 个元素被
分成三段（组）：左段 l e f t，右段 r i g h t和
中段 m i d d l e。中段仅包含一个元素。左段
中各元素都小于等于中段元素，右段中各元
素都大于等于中段元素。
? 因此 l e f t和 r i g h t中的元素可以独立排序，
并且不必对 l e f t和 r i g h t的排序结果进行合
并。 m i d d l e中的元素被称为支点 ( p i v o t )
算法设计与分析 100
快速排序
? 快速排序的伪代码如下 。
? / /使用快速排序方法对 a[ 0,n- 1 ]排序
? 从 a[ 0,n- 1 ]中选择一个元素作为 m i d d l e，
该元素为支点
? 把余下的元素分割为两段 left 和 r i g h t，使得
l e f t中的元素都小于等于支点，而 right 中的
元素都大于等于支点
? 递归地使用快速排序方法对 left 进行排序
? 递归地使用快速排序方法对 right 进行排序
? 所得结果为 l e f t + m i d d l e + r i g h t
算法设计与分析 101
划分算法 ? i ←low
? x ←A[low]
? for j ←low+1 to high
? if A[j]≤x then
? i ←i+1
? if i≠j then 互换 A[i]和 A[j]
? end if
? end for
? 互换 A[low]和 A[i]
? w ←i
? return A和 w
算法设计与分析 102
快速排序
? if low<high then
? split(A[low…high],w)
? quicksort(A,low,w-1)
? quicksort(A,w+1,high)
? end if
算法设计与分析 103
快速排序
? template<class T>
? void QuickSort(T*a,int n)
? {
? {
? quickSort(a,0,n-1);
? template<class T>
? void quickSort(T a[],int l,int r)
? {
? if (l >= r) return;
? int i = l,
? j = r + 1;
? T pivot = a[l];
算法设计与分析 104
? while (true) {
? do {//
? i = i + 1;
? } while (a[i] < pivot);
? do {
? j = j - 1;
? } while (a[j] > pivot);
? if (i >= j) break;
? Swap(a[i],a[j]);
? }
算法设计与分析 105
? a[l] = a[j];
? a[j] = pivot;
? quickSort(a,l,j-1);
? quickSort(a,j+1,r);
? }
算法设计与分析 106
距离最近的点对
?例 6-7 假设在一片金属上钻 n 个大小一
样的洞，如果洞太近，金属可能会断。
若知道任意两个洞的最小距离，可估计
金属断裂的概率。这种最小距离问题实
际上也就是距离最近的点对问题。
?通过检查所有的 n(n- 1 ) / 2对点，并计算
每一对点的距离，可以找出距离最近的
一对点。这种方法所需要的时间为 (n2 )。
我们称这种方法为直接方法。
算法设计与分析 107
距离最近的点对
? if (n较小 ) {用直接法寻找最近点对
? R e t u r n ; }
? // n较大
?将点集分成大致相等的两个部分 A和 B
?确定 A和 B中的最近点对
?确定一点在 A中、另一点在 B中的最近点
对
?从上面得到的三对点中，找出距离最小
的一对点
算法设计与分析 108
距离最近的点对
F
A
B
I
C
L
G
M
J
E
K H
D
N
算法设计与分析 109
距离最近的点对
? 1,选择数据结构为了实现上述的分治之
算法，需要确定什么是“小问题”以及
如何表示点。由于集合中少于两点时不
存在最近点对，因此必须保证分解过程
不会产生少于两点的点集。如果将少于
四点的点集做为“小问题”，就可以避
免产生少于两点的点集。
算法设计与分析 110
距离最近的点对
?每个点可有三个参数：标号,x 坐标,
y 坐标。假设标号为整数，每个点可用
P o i n t l类来表示。为了便于按 x 坐标
对各个点排序，可重载操作符＜ =。
归并排序程序如下所示。
算法设计与分析 111
? if high-low+1≤3 then 用直接方法计算 δ
? else
? mid ← ? (low+high)/2?
? x0 ← x(s[mid])
? δl←cp(low,mid)
? δr←cp(mid+1,high)
? δ←min{ δl,δr}
? k←0
? for i←1 to n
? if |x(y[i])-x0| ≤δ then
? k←k+1
? T[k] ←y[i]
? end if
? end for
算法设计与分析 112
? δ’←2 δ
? for i←1 to k -1
? for j←i+1 to min{i+7,k}
? if d(T[i],T[j]<δ,then δ’ ←d(T[i],T[j])
? end for
? end for
? δ←min{ δ,δ’}
? end if
? return δ
算法设计与分析 113
? class Point1 {
? friend float dist(const Point1&,const
point1&);
? friend void close(Point1 *,Point2 *,Point2 *,
int,int,Point1&,Point1&,float&);
? friend bool closest(Point1 *,int,Point1&,
Point1&,float&);
? friend void main();
? p u b l i c,
? int operator<=(Point1 a) const
? {return (x <= a.x);}
? p r i v a t e,
? int ID; // 点的编号
? float x,y; // 点坐标
? } ;
算法设计与分析 114
? class Point2 {
? friend float dist(const Point2&,const
Point2&)；
? friend void close(Point1 *,Point2 *,Point2 *,
int,int,Point1&,Point1&,float&);
? friend bool closest(Point1 *,int,Point1&,
Point1&,float&);
? friend void main();
? p u b l i c,
? int operator<=(Point2 a) const
? {return (y <= a.y);}
? p r i v a t e,
? int p; // 数组 X中相同点的索引
? float x,y; // 点坐标
? } ;
算法设计与分析 115
距离最近的点对
? 计算两点距离
? template<class T>
? inline float dist(const T& u,const T& v)
? { / /计算点 u 和 v之间的距离
? float dx = u.x-v,x ;
? float dy = u.y-v,y ;
? return sqrt(dx * dx + dy * dy);
? }
算法设计与分析 116
距离最近的点对
? 预处理及调用 c l o s e
? bool closest(Point1 X[],int n,Point1& a,
Point1& b,float& d)
? {
? if (n < 2) return false;
? M e r g e S o r t ( X,n ) ;
? Point2 *Y = new Point2 [n];
? for (int i = 0; i < n; i++) {
? Y[i].p = i;
? Y[i].x = X[i].x;
? Y[i].y = X[i].y;
? }
算法设计与分析 117
距离最近的点对
? M e r g e S o r t ( Y,n); // 按 y坐标排序
? Point2 *Z = new Point2 [n];
? c l o s e ( X,Y,Z,0,n - 1,a,b,d ) ;
? delete [] Y;
? delete [] Z;
? return true;
? }
算法设计与分析 118
? 计算最近点对
? void close(Point1 X[],Point2 Y[],Point2
Z[],int l,int r,Point1& a,Point1& b,float&
d)
? {
? if (r-l == 1) {
? a = X[l];
? b = X[r];
? d = dist(X[l],X[r]);
? r e t u r n ; }
? if (r-l == 2) {
? float d1 = dist(X[l],X[l+1]);
? float d2 = dist(X[l+1],X[r]);
? float d3 = dist(X[l],X[r]);
算法设计与分析 119
? if (d1 <= d2 && d1 <= d3) {
? a = X[l];
? b = X[l+1];
? d = d1;
? r e t u r n ; }
? if (d2 <= d3) {a = X[l+1];
? b = X[r];
? d = d2;}
? else {a = X[l];
? b = X[r];
? d = d3;}
? r e t u r n ; }
? int m = (l+r)/2;
算法设计与分析 120
? int f = l,
? g = m+1;
? for (int i = l; i <= r; i++)
? if (Y[i].p > m) Z[g++] = Y[i];
? else Z[f++] = Y[i];
? c l o s e ( X,Z,Y,l,m,a,b,d ) ;
? float dr;
? Point1 ar,br;
? c l o s e ( X,Z,Y,m + 1,r,a r,b r,d r ) ;
? if (dr < d) {a = ar;
? b = br;
? d = dr;}
算法设计与分析 121
? M e r g e ( Z,Y,l,m,r);
? int k = l;
? for (i = l; i <= r; i++)
? if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];
? for (i = l; i < k; i++){
? for (int j = i+1; j < k && Z[j].y - Z[i].y < d;
? j + + ) {
? float dp = dist(Z[i],Z[j]);
? if (dp < d) {
? d = dp;
? a = X[Z[i].p];
? b = X[Z[j].p];}
? } } }
算法设计与分析 122
距离最近的点对
?令 t (n) 代表处理 n 个点时，函数 close 所
需要的时间。当 n＜ 4时,t (n) 等于某个
常数 d。当 n≥4时，需花费 (n) 时间来完
成以下工作：将点集划分为两个部分，
两次递归调用后重构 Y，淘汰距分割线
很远的点，寻找更好的第三类点对。
?因而可得到如下递归式,
4n
4n ])2/([])2/([{)(
?
????
d
cnntntnt
算法设计与分析 123
算法思想
? 现在计算 xi 值，步骤如下：若 f ( 1,c) =f ( 2,c)，
则 x1 = 0，否则 x1 = 1。接下来需从剩余容量
c-w1中寻求最优解，用 f (2,c-w1) 表示最优解。
依此类推，可得到所有的 xi (i= 1.n) 值。
? 在该例中，可得出 f ( 2,11 6 ) = 3 3≠f ( 1,11
6 )，所以 x1 = 1。接着利用返回值 3 8 -p1=18
计算 x2 及 x3，此时 r = 11 6 -w1 = 1 6，又由 f
( 2,1 6 ) = 1 8，得 f ( 3,1 6 ) = 1 4≠f ( 2,1 6 )，
因此 x2 = 1，此时 r= 1 6 -w2 = 2，所以 f (3,2)
=0，即得 x3 = 0。
第 7章 动态规划
算法设计与分析 124
算法思想
? 动态规划方法采用最优原则（ principle of
optimality）来建立用于计算最优解的递归式。
? 所谓最优原则即不管前面的策略如何，此后
的决策必须是基于当前状态（由上一次决策
产生）的最优决策。由于对于有些问题的某
些递归式来说并不一定能保证最优原则，因
此在求解问题时有必要对它进行验证。若不
能保持最优原则，则不可应用动态规划方法。
在得到最优解的递归式之后，需要执行回溯
（ t r a c e b a c k）以构造最优解。
第 7章 动态规划
算法设计与分析 125
最长公共子序列
? for i←0 to n
? L[i,0] ←0
? end for
? for j ←0 to m
? L[0,j] ←0
? end for
? for i ←1 to n
? for j ←1 to m
? if ai=bj then L[i,j] ←L[i -1,j-1]+1
? else L[i,j] ←max{L[i,j -1],L[i-1,j]}
? end if
? end for
? end for
? return L[n,m]
算法设计与分析 126
矩阵乘法链
? 例 7-1 假定 A为 1 0 0× 1矩阵,B为 1× 1 0 0矩
阵,C为 1 0 0× 1矩阵，则 A*B的时间耗费为
10 0 0 0，得到的结果 D为 1 0 0× 1 0 0矩阵，
再与 C相乘所需的时间耗费为 1 000 000，因此
计算 (A*B) *C的总时间为 1 010 000。 B*C的时
间耗费为 10 000，得到的中间矩阵为 1× 1矩阵，
再与 A相乘的时间消耗为 1 0 0，因而计算 A*
（ B*C）的时间耗费竟只有 10 100！而且，计
算（ A*B） *C时，还需 10000个单元来存储
A*B，而 A*（ B*C）计算过程中，只需用 1个
单元来存储 B*C。
第 7章 动态规划
算法设计与分析 127
矩阵乘法链
?选择合适秩序计算 A*B*C矩阵的实例：
考虑两个 3维图像的匹配。图像匹配问
题的要求是，确定一个图像需旋转、平
移和缩放多少次才能逼近另一个图像。
实现匹配的方法之一便是执行约 1 0 0次
迭代计算，每次迭代需计算 1 2× 1个向
量 T,T=?A(x,y,z) *B(x,y,z)*C(x,y,z )
其中 A,B和 C分别为 1 2× 3,3× 3和
3× 1矩阵。 (x,y,z) 为矩阵中向量的坐
标 。
第 7章 动态规划
算法设计与分析 128
矩阵乘法链
?现在要介绍一种采用动态规划方法获得
矩阵乘法次序的最优策略。这种方法可
将算法的时间消耗降为 (q3 )。用 Mi j 表
示链 Mi×,× Mj （ i≤j）的乘积。设 c(i,j)
为用最优法计算 Mi j 的消耗,k a y(i,j)
为用最优法计算 Mi j的最后一步
? Mi k× Mk+1,j 的消耗。因此 Mij 的最优
算法包括如何用最优算法计算 Mik 和 Mkj
以及计算 Mik× Mkj 。根据最优原理，可
得到如下的动态规划递归式,
第 7章 动态规划
算法设计与分析 129
矩阵乘法链
第 7章 动态规划
qssqi
ksiik a y
rrrsikckiciic
qiiiik a yrrriic
qijic
siki
siki
iii
?????
??
??????
??????
???
???
???
??
1,1
),(
}),1(),({)1,(
1,)1,(;)1,(
1,0),(
11
21
m i n
获得上述最小值的
算法设计与分析 130
矩阵乘法链
?例 7-2 设 q= 5和
? r =（ 1 0,5,1,10,2,10）,
?由动态规划的递归式得,
? C(1,5)=min{
c(1,1)+c (2,5)+500,c(1,2)+c(3,5)+100,
c(1,3)+c(4,5)+1000,c(1,4)+c(5,5)+200}
算法设计与分析 131
矩阵乘法链
? 式中待求的 c 中有四个 c的 s= 0或 1，因此用动
态规划方法可立即求得它们的值,c( 1,1 )
=c( 5,5 ) = 0 ;c(1,2)=50; c( 4,5 ) = 200。
? 现计算 C( 2,5 ),
? c( 2,5 ) = m i n {c( 2,2 ) +c(3,5)+50,c( 2,3 )
+c(4,5)+500,c( 2,4 ) +c( 5,5 ) + 1 0 0 }
? 其中 c( 2,2 ) =c( 5,5 ) = 0； c( 2,3 ) = 5 0；
c(4,5)=200 。
第 7章 动态规划
算法设计与分析 132
矩阵乘法链
?再计算 c( 3,5 )及 c( 2,4 ),
? c( 3,5 ) = m i n {c( 3,3 ) +c(4,5)+100,
c( 3,4 ) +c( 5,5 ) + 2 0 } = m i n { 0 + 2
0 0 + 1 0 0,2 0 + 0 + 2 0 } = 4 0
? c( 2,4 ) = m i n {c( 2,2 ) +c( 3,4 ) + 1
0,c( 2,3 ) +c( 4,4 ) + 1 0 0 } = m i n { 0
+ 2 0 + 1 0,5 0 + 1 0 + 2 0 } = 3 0
?由以上计算还可得 k a y( 3,5 ) = 4,k
ay( 2,4 ) = 2。
算法设计与分析 133
矩阵乘法链
? 现在,计算 c(2,5) 所需的所有中间值都已求得,
? 将它们代入式得,
? c(2,5)=min{0+40+50,50+200+500,
30+0+100}=90且 k a y( 2,5 ) = 2
? 计算 c( 1,5 )，在此之前必须算出 c( 3,5 )、
c(1,3) 和 c( 1,4 )。同上述过程，亦可计算出
它们的值分别为 4 0,15 0和 9 0，相应的 k a y
值分别为 4,2和 2。代入式得：
c(1,5)=min{0+90+500,50+40+100,
150+200+1000,90+0+200}=190
? 且 k a y( 1,5 ) = 2
算法设计与分析 134
矩阵乘法链
? 此最优乘法算法的消耗为 1 9 0，由 k a y(1,5)
值可推出该算法的最后一步,k a y(1,5) 等于 2,
? 因此最后一步为 M1 2× M3 5，而 M12 和 M35
都是用最优法计算而来。由 k a y( 1,2 ) = 1知
M12 等于 M11× M2 2，同理由 k a y( 3,5) = 4
得知 M35 由 M3 4× M55 算出。依此类推，
M34 由 M3 3× M44 得出。因而此最优乘法算
法的步骤为,
? M11× M22 = M12
? M33× M44 = M34
? M34× M55 = M35
? M12× M35 = M15
算法设计与分析 135
? for i ←1 to n
? c[i,j] ←0
? end for
? for d ←1 to n -1
? for i ←1 to n -d
? j ←i+d
? comment:下列三行计算 c[i,j]
? c[i,j] ← ∞
? for k ←i+1 to j
? c[i,j] ←min{c[i,j],c[i,k -1]+c[k,j]+r[i]r[k]r[j+1]}
? end for
? end for
? end for
? return c[1,n]
算法设计与分析 136
矩阵乘法链 (递归 )
? int C(int i,int j)
? {
? if (i==j) return 0;
? if (i == j-1) {
? kay[i][i+1] = i;
? return r[i]*r[i+1]*r[r+2];}
? int u = C(i,i) + C(i+1,j) + r[i]*r[i+1]*r[j+1];
? kay[i][j] = i;
? for (int k = i+1; k < j; k++) {
? int t = C(i,k) + C(k+1,j) + r[i]*r[k+1]*r[j+1];
? if (r < u) {
算法设计与分析 137
? u = t;
? kay[i][j] = k;
? }
? return u;
? }
? void Traceback (int i,int j,int **kay)
? {
? if ( i == j) return;
? Traceback(i,kay[i][j],kay);
? Traceback(kay[i][j]+1,j,kay);
? cout << "Multiply M" << i << ","<< kay[i][j];
? cout << " and M " << (kay[i][j]+1) << "," << j
<< end1;}
算法设计与分析 138
矩阵乘法链 (无重复计算递归 )
? int C(int i,int j)
? {
? if （ c[i][j] >u） return c[i][j];
? if(i==j) return 0;
? i f ( i = = j - 1 ) {
? kay[i][i+1]=i;
? c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;
? return c[i][j];}
? int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];
? k a y [ i ] [ j ] = i ;
算法设计与分析 139
? for (int k==i+1; k<j;k++){
? int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];
? if (t<u) {
? u = t ;
? k a y [ i ] [ j ] = k ; }
? }
? c [ i ] [ j ] = u ;
? return u;
? }
算法设计与分析 140
矩阵乘法链 (迭代 )
? void MatrixChain(int r[],int q,int **c,int **kay)
? {
? for (int i = 1; i < q; i++) {
? c[i][i] = 0;
? c[i][i+1] = r[i]*r[i+1]*r[i+2];
? kay[i][i+1] = i;
? }
? c[q][q] = 0;
? for (int s = 2; s < q; s++)
? for (int i = 1; i <= q - s; i++) {
算法设计与分析 141
? c[i][i+s]=c[i][i]+c[i+1][i+s]+r[i]*r[i+1]*r[i+s+1];
? kay[i][i+s] = i;
? for (int k = i+1; k < i + s; k++) {
? int t = c[i][k] + c[k+1][i+s] + r[i]*r[k+1]*r[i+s+1];
? if (t < c[i][i+s]) {
? c[i][i+s] = t;
? kay[i][i+s] = k;}
? }
? }
? }
算法设计与分析 142
最短路径
? 假设 G为有向图，其中每条边都有一个长度
（或耗费），图中每条有向路径的长度等于
该路径中各边的长度之和。
? 例 7-3 从顶点 1到顶点 3的路径
1 3 6 8
9 7 4
5 2 10 1
20 8
7
3 2 1
1
1
2 3 2
2 4
6
算法设计与分析 143
最短路径
?设图 G中 n 个顶点的编号为 1到 n。
?令 c (i,j,k)表示从 i 到 j 的最短路径的长
度，其中 k 表示该 路径中的最大顶点。
因此，如果 G中包含边 <i,j>,
则 c(i,j,0) =边 <i,j> 的长度；
若 i= j,则 c(i,j,0)=0；如果 G中不包含边
<i,j>,则 c (i,j,0)= +∞。 c(i,j,n) 则是
从 i 到 j 的最短路径的长度。
算法设计与分析 144
最短路径
?例 7-4 图。若 k=0,1,2,3,
?则 c (1,3,k)= ∞； c (1,3,4)= 2 8；
?若 k = 5,6,7，则 c (1,3,k) = 1 0；
?若 k=8,9,10，则 c (1,3,k) = 9。
?因此 1到 3的最短路径长度为 9。
算法设计与分析 145
最短路径
?对于任意 k＞ 0，如何确定 c (i,j,k) 呢？
中间顶点不超过 k 的 i 到 j 的最短路径有
两种可能,
?该路径含或不含中间顶点 k。若不含，
则该路径长度应为 c(i,j,k- 1 )，否则长
度为 c(i,k,k- 1) +c (k,j,k- 1 )。 c(i,j,k)
可取两者中的最小值。
?因此可得到如下递归式,
? c( i,j,k)= m i n {c(i,j,k-1),c (i,k,k- 1)
+c (k,j,k- 1 ) },k＞ 0
算法设计与分析 146
最短路径
? D ← l
? for k ←1 to n
? for i ←1 to n
? for j ←1 to n
? D[i,j] =min{D[i,j],D[i,k]+D[k,j]}
? end for
? end for
? end for
算法设计与分析 147
最短路径
for （ int i=1； i < = n ; i + +）
? for (int j=1; j<=n; j+ + )
? c ( i,j,0 ) = a ( i,j);
? for(int k=1;k<=n;k++)
? for (int i=1;i<=n;i++)
? for (int j= 1 ;j< = n ;j+ + )
? if (c(i,k,k-1)+c(k,j,k - 1 ) < c ( i,j,k - 1 ) )
? c ( i,j,k ) = c ( i,k,k - 1 ) + c ( k,j,k -
1 ) ;
? else c(i,j,k ) = c ( i,j,k - 1 ) ;
算法设计与分析 148
最短路径
? c 和 kay 的计算
? template<class T>
? void AdjacencyWDigraph<T>::Allpairs(T
**c,int **kay)
? {
? for (int i = 1; i <= n; i++)
? for (int j = 1; j <= n; j++) {
? c[i][j] = a[i][j];
? kay[i][j] = 0;
? }
? for (i = 1; i <= n; i++)
算法设计与分析 149
? c[i][i] = 0;
? for (int k = 1; k <= n; k++)
? for (int i = 1; i <= n; i++)
? for (int j = 1; j <= n; j++) {
? T t1 = c[i][k];
? T t2 = c[k][j];
? T t3 = c[i][j];
? if (t1 != NoEdge && t2 != NoEdge && (t3
== NoEdge || t1 + t2 < t3)) {
? c[i][j] = t1 + t2;
? kay[i][j] = k;}
? }
? }
算法设计与分析 150
? 输出最短路径
? void outputPath(int **kay,int i,int j)
? {
? if (i == j) return;
? if (kay[i][j] == 0) cout << j << ' ';
? else {outputPath(kay,i,kay[i][j]);
? o u t p u t P a t h ( k a y,kay[i][j],j);}
? }
? template<class T>
? void OutputPath(T **c,int **kay,T
NoEdge,int i,int j)
? {
算法设计与分析 151
? if (c[i][j] == NoEdge) {
? cout << "There is no path from " << i
<< " to " << j << endl;
? r e t u r n ; }
? cout << "The path is" << endl;
? cout << i << '';
? o u t p u t P a t h ( k a y,i,j ) ;
? cout << endl;
? }
第 7章 动态规划
算法设计与分析 152
0/1背包
?简单的 0/1背包
在该问题中需要决定 x1,,xn的值。假设
按 i = 1,2,.,n 的次序来确定 xi 的值。
如果臵 x1 = 0，则问题转变为相对于其
余物品（即物品 2,3,.,n），背包容
量仍为 c 的背包问题。若臵 x1 = 1，问题
就变为关于最大背包容量为 c-w1 的问题。
现设 r ?{c,c-w1 } 为剩余的背包容量 。
算法设计与分析 153
算法设计
?假设 f (i,y) 表 0/1中剩余容量为 y，剩余物
品为 i,i + 1,.,n 时的最优解的值
Wiy } ),1(),,1({ m a x
Wiy0 ),1(
WnyP n
Wny0 0
{),(
{),(
?????
???
?
??
?
?
PiWiyifyif
yif
yif
ynf
算法设计与分析 154
0/1背包
? for i←0 to n
? F[i,0] ←0
? end for
? for j ←0 to C
? F[0,j] ←0
? end for
? for i ←1 to n
? for j ←1 to C
? F[i,j] ←F[i -1,j]
? if si≤j then F[i,j] ←max{F[i,j],F[i -1,j-si]+Fi}
? end for
? end for
? return F[n,C]
算法设计与分析 155
算法设计
? int F(int i,int y)
? {// 返回 f ( i,y ),
? if (i == n) return (y < w[n])? 0, p[n];
? if (y < w[i]) return F(i+1,y);
? return max(F(i+1,y),F(i+1,y-w[i]) + p[i]);
? }
算法设计与分析 156
背包问题
?1,递归策略
?例 7-5 设 n= 5,p= [ 6,3,5,4,6 ]，
w=[2,2,6,5,4] 且 c= 1 0,求 f ( 1,1 0 )。为
了确定 f ( 1,1 0 )，调用函数 F ( 1,1 0 )
第 7章 动态规划
算法设计与分析 157
10
6
10
10
10
8
8
8
8
2
6
6 2 8 0
5 10 6 3 1 8 2 3 8 1 2 6 0
背包问题
1,递归策略
第 7章 动态规划
算法设计与分析 158
背包问题
? 2,权为整数的迭代方法
? template<class T>
? void Knapsack(T p[],int w[],int c,int n,
T** f)
? {// 对于所有 i和 y计算 f [ i ] [ y ]
? //初始化 f [ n ] [ ]
? for (int y = 0; y <= yMax; y++)
? f[n][y] = 0;
? for (int y = w[n]; y <= c; y++)
? f[n][y] = p[n];
? // 计算剩下的 f
第 7章 动态规划
算法设计与分析 159
? for (int i = n - 1; i > 1; i--) {
? for (int y = 0; y <= yMax; y++)
? f[i][y] = f[i+1][y];
? for (int y = w[i]; y <= c; y++)
? f[i][y] = max(f[i+1][y],f[i+1][y-w[i]] + p[i]);
? }
? f[1][c] = f[2][c];
? if (c >= w[1])
? f[1][c] = max(f[1][c],f[2][c-w[1]] + p[1]);
? }
第 7章 动态规划
算法设计与分析 160
? template<class T>
? void Traceback(T **f,int w[],int c,int n,
int x[])
? {// 计算 x
? for (int i = 1; i < n; i++)
? if (f[i][c] == f[i+1][c]) x[i] = 0;
? else {x[i] = 1;
? c -= w[i];}
? x[n] = (f[n][c])? 1, 0;
? }
第 7章 动态规划
算法设计与分析 161
图像压缩
? 1) 图像线性化根据图中的折线将 m× m
维图像转换为 1× m2 维矩阵 。
第 7章 动态规划
算法设计与分析 162
图像压缩
? 2) 分段将像素组分成若干个段，分段原则
是：每段中的像素位数相同。每个段是相
邻像素的集合且每段最多含 2 5 6个像素，
因此，若相同位数的像素超过 2 5 6个的话，
则用两个以上的段表示。
? 3) 创建文件创建三个文件,S e g m e n t L
e n g t h,BitsPerPixel 和 P i x e l s。第一个
文件包含在 2 )中所建的段的长度 (减 1 )，文
件中各项均为 8位长。文件 BitsPerPixel 给
出了各段中每个像素的存储位数（减 1），
文件中各项均为 3位。文件 Pixels 则是以变
长格式存储的像素的二进制串。
第 7章 动态规划
算法设计与分析 163
图像压缩
? 4) 压缩文件压缩在 3) 中所建立的文件，
以减少空间需求。
?上述压缩方法的效率（用所得压缩率表
示）很大程度上取决于长段的出现频率
第 7章 动态规划
算法设计与分析 164
图像压缩
?例 7-6 考察图的 4× 4图像 。
第 7章 动态规划
10 9 12 40
12 15 35 50
8 10 9 15
240 160 130 11
算法设计与分析 165
图像压缩
? 文件 SegmentLength 为 2,2,6,2；文件
BitsPerSegment 的内容为 3,5,3,7；文件 P
i x e l s包含了按蛇形行主次序排列的 1 6个灰
度值，其中头三个各用 4位存储，接下来三个
各用 6位，再接下来的七个各用 4位，最后三
个各用 8位存储。因此存储单元中前 3 0位存储
了前六个像素,
? 1010 1001 1100 111000 110010 100011
? 这三个文件需要的存储空间分别为：文件
SegmentLength 需 3 2位； BitsPerSegment 需 1
2位； Pixels 需 8 2位，共需 1 2 6位。而如果每
个像素都用 8位存储，则存储空间需 8× 1 6 = 1
2 8位，因而在本例图像中，节省了 2位的空间 。
第 7章 动态规划
算法设计与分析 166
图像压缩
?例 7-7 如果将例 7 - 6中的第 1段和第 2段
合并，合并后，文件 Segment Length变为
5,6,2,BitsPerSegment 变为 5,3,7。
而文件 Pixels 的前 3 6位存储的是合并后
的第一段,
? 001010 001001 001100 111000 110010
100011
第 7章 动态规划
算法设计与分析 167
图像压缩
? 令 Sq 为前 q 个段的最优合并所需要的空间。
定义 S0 = 0。考虑第 i 段 (i＞ 0 )，假如在最优合
并 C中，第 i 段与第 i- 1,i- 2,.,i-r+1 段相合
并，而不包括第 i-r 段。合并 C所需要的空间
消耗等于：第 1段到第 i-r 段所需空间 + l s u m
(i-r+ 1,i) * b m a x (i-r+ 1,i) + 11
? 其中 l s u m(a,b)=
? bmax (a,b)= m a x {ba,...,bb }。
?
?
b
aj
jl
第 7章 动态规划
算法设计与分析 168
图像压缩
? 假如在 C中第 1段到第 i-r 段的合并不是最优合
并，那么需要对合并进行修改，以使其具有
更小的空间需求。因此还必须对段 1到段 i-r 进
行最优合并，也即保证最优原则得以维持。
故 C的空间消耗为,
? Si = Si-r +l s u m（ i-r +1,i） *b m a x（ i-r+1,i）
+ 11
11)},1m a x (*),1({m i n
2 5 6),1(
1
?????? ?
???
??
ikibikils u mSSi ki
ikil s u m
ik
第 7章 动态规划
算法设计与分析 169
图像压缩
? 例 7-9 假定在 2) 中得到五个段，它们的长度为
[ 6,3,1 0,2,3 ]，像素位数为 [ 1,2,3，
2,1 ]，要用公式（ 7 - 3）计算 Sn，必须先求
出 Sn-1,.,S0 的值。 S0 为 0，现计算 s1,S1
=S0 +l1 *b1+ 11 = 17
? k a y1 = 1s2 由下式得出,
? s2 = m i n {s1 +l2 b2,s0 + (l1 +l2 ) * m a x {b1,
b2} } + 11 = m i n { 17 + 6,0 + 9 * 2 } + 11 = 29
? k a y2 = 2以此类推，可得 s1.s5 = [ 17,29,67，
73,82], k a y1.k a y5 = [ 1,2,2,3,4 ]。
第 7章 动态规划
算法设计与分析 170
图像压缩
? 1,递归方法
? int S(int i)
? {
? if (i == 0 ) return 0;
? int lsum = l[i],bmax = b[i];
? int s = S(i-1) + lsum * bmax;
? kay[i] = 1;
? for (int k = 2; k <= i && lsum+l[i-k+1] <= L;
k++) {
? lsum += l[i-k+1];
? if (bmax < b[i-k+1]) bmax = b[i-k+1];
? int t = S(i-k);
第 7章 动态规划
算法设计与分析 171
? if (s > t + lsum * bmax) {
? s = t + lsum * bmax;
? kay[i] = k;}
? }
? return s + header;
? }
? void Traceback(int kay[],int n)
? {
? if (n == 0) return;
? Tr a c e b a c k ( k a y,n-kay[n]);
? cout << "New segment begins at " << (n -
kay[n] + 1) << endl;
? }
第 7章 动态规划
算法设计与分析 172
图像压缩
? 2,无重复计算的递归方法
? int S(int i)
? {
? if (i == 0) return 0;
? if (s[i] > 0) return s[i]; //已计算完
? int lsum = l[i],bmax = b[i];
? s[i] =S(i-1) + lsum * bmax;
? kay[i] = 1;
? for (int k = 2; k <= i && lsum+l[i-k+1] <= L;
k++) {
第 7章 动态规划
算法设计与分析 173
? lsum += l[i-k+1];
? if (bmax < b[i-k+1]) bmax = b[i-k+1];
? int t = S(i-k);
? if (s[i] > t + lsum * bmax) {
? s[i] = t + lsum * bmax;
? kay[i] = k;}
? }
? s[i] += header;
? return s[i];
? }
第 7章 动态规划
算法设计与分析 174
图像压缩 ? 3,迭代方法
? void Vbits (int l[ ],int b[ ],int n,int
s[ ],int kay[ ])
? {int L = 256,header = 11 ;
? s[0] = 0;
? for (int i = 1; i <= n; i++) {
? int lsum = l{i},
? bmax = b[i];
? s[i] = s[i-1] + lsum * bmax;
? kay[i] = 1;
第 7章 动态规划
算法设计与分析 175
? for (int k=2; k<= i && lsum+l[i-k+1]<=
L; k++) {
? lsum += l[i-k+1];
? if (bmax < b[i-k+1]) bmax = b[i-k+1];
? if (s[i] > s[i-k] + lsum * bmax){
? s[i] = s[i-k] + lsum * bmax;
? kay[i] = k; }
? }
? s[i] += header;
? }
? }
第 7章 动态规划
算法设计与分析 176
最优化问题
?例 8-1 [ 渴婴问题 ] 有一个非常渴的、聪
明的小婴儿，她可能得到的东西包括
一杯水、一桶牛奶、多罐不同种类的
果汁、许多不同的装在瓶子或罐子中
的苏打水，即婴儿可得到 n 种不同的饮
料。
?
第八章：贪婪法
?
?
n
i
S iX i
1
?
?
?
n
i
tXi
1
aiXi ??0
?
?
?
n
i
tai
1
算法设计与分析 177
最优化问题
?例 8-2 [装载（背包）问题 ] 有一艘大船
准备用来装载货物。所有待装货物都装
在货箱中且所有货箱的大小都一样，但
货箱的重量都各不相同。设第 i 个货箱
的重量为 wi（ 1≤i≤n），而货船的最大载
重量为 c，我们的目的是在货船上装入
最多的货物。
第 八 章：贪婪法
?
CW iX i
n
i
?
?
?
1
?
?
n
i
Xi
1
算法设计与分析 178
template<class T>
? void ContainerLoading(int x[],T w[],T c,int
n)
? {
? int *t = new int [n+1];
? I n d i r e c t S o r t ( w,t,n);
? for (int i = 1; i <= n; i++)
? x[i] = 0;
? for (i = 1; i <= n && w[t[i]] <= c; i++) {
? x[t[i]] = 1;
? c -= w[t[i]];} // 剩余容量
? delete [] t;
? } O (nl o gn),O (n),O (nl o gn)。
第 八 章：贪婪法
算法设计与分析 179
最优化问题
? 假设 n =8,
[w1,...w8 ]=[100,200,50,90,150,50,20,80],c= 4
0 0。利用贪婪算法时，所考察货箱的顺序为
7,3,6,8,4,1,5,2。货箱 7,3,6,8,4,1
的总重量为 3 9 0个单位且已被装载，剩下的
装载能力为 1 0个单位，小于剩下的任何一个
货箱。在这种贪婪解决算法中得到 [x1,...,x8 ]
= [ 1,0,1,1,0,1,1,1 ]
? 且 = 6。
第 八 章：贪婪法
?
?
n
i
Xi
1
算法设计与分析 180
最优化问题
? 例 8-3 [找零钱 ] 一个小孩买了价值少于 1美元
的糖，并将 1美元的钱交给售货员。售货员希
望用数目最少的硬币找给小孩。假设提供了数
目不限的面值为 2 5美分,1 0美分,5美分、
及 1美分的硬币。售货员分步骤组成要找的零
钱数，每次加入一个硬币。 选择硬币时所采
用的贪婪准则如下,每一次选择应使零钱数
尽量增大。为保证解法的可行性（即：所给
的零钱等于要找的零钱数），所选择的硬币
不应使零钱总数超过最终所需的数目 。
第 八 章：贪婪法
算法设计与分析 181
最优化问题
? 例 8-4 [机器调度 ] 现有 n 件任务和无限多台的
机器，任务可以在机器上得到处理。每件任
务的开始时间为 si，完成时间为 fi, si < fi 。
[si,fi ] 为处理任务 i 的时间范围。两个任务 i，
j 重叠是指两个任务的时间范围区间有重叠，
而并非是指 i,j 的起点或终点重合。例如：区
间 [ 1,4 ]与区间 [ 2,4 ]重叠，而与区间 [ 4，
7 ]不重叠。一个可行的任务分配是指在分配
中没有两件重叠的任务分配给同一台机器。
因此，在可行的分配中每台机器在任何时刻
最多只处理一个任务。最优分配是指使用的
机器最少的可行分配方案。
第 八 章：贪婪法
算法设计与分析 182
最优化问题
第 八 章：贪婪法
任
务
a b c d e f g
开
始
0 3 4 9 7 1 6
完
成
2 7 7 11 10 5 8
算法设计与分析 183
最优化问题
第 八 章：贪婪法
0 1 2 3 4 5 6 7 8 9 10 11
M3
M2
M1
算法设计与分析 184
最优化问题
? 例 8-5 [最小代价通讯网络 ] 计算机之间所有可
能的通信连接可被视作一个无向图，图的每
条边都被赋予一个权值，权值表示建成由这
条边所表示的通信连接所要付出的代价。包
含图中所有顶点（计算机）的连通子图都是
一个可行解。设所有的权值都非负，则所有
可能的可行解都可表示成无向图的一组生成
树，而最优解是其中具有最小代价的生成树。
在这个问题中，需要选择一个无向图中的边
集合的子集，这个子集必须满足如下限制条
件：所有的边构成一个生成树。而优化函数
是子集中所有边的权值之和。
第 八 章：贪婪法
算法设计与分析 185
最优化问题
?情形 A t=1 v=1 (二分图的边染色）
?情形 B t? v=1
第 八 章：贪婪法
算法设计与分析 186
最优化问题
情形 C t? v?
第 八 章：贪婪法
算法设计与分析 187
最优化问题
?在 0 / 1背包问题中，需对容量为 c 的背
包进行装载。从 n 个物品中选取装入
背包的物品，每件物品 i 的重量为 wi,
价值为 pi 。对于可行的背包装载，背
包中物品的总重量不能超过背包的容
量，最佳装载是指所装入的物品价值
最高 Xi [ 0,1 ] ( 1≤i≤n)
第 八 章：贪婪法
?
?
n
i
P iX i
1
?
?
?
n
i
CW iX i
1
?
算法设计与分析 188
最优化问题
?一种贪婪准则为,从剩余的物品中，选出可
以装入背包的价值最大的物品
?例如，考虑 n=2,w=[100,10,10],p =[20,15,15],
c = 1 0 5。当利用价值贪婪准则时，获得的解
为 x= [ 1,0,0 ]，这种方案的总价值为 2 0。而
最优解为 [ 0,1,1 ]，其总价值为 3 0。
第 八 章：贪婪法
算法设计与分析 189
最优化问题
?另一种方案是重量贪婪准则是,从剩下
的物品中选择可装入背包的重量最小的
物品。
? n=2,w=[10,20],p=[5,100],c= 2 5。当利
用重量贪婪策略时，获得的解为 x =[1,0],
比最优解 [ 0,1 ]要差。
第 八 章：贪婪法
算法设计与分析 190
最优化问题
?价值密度 pi /wi 贪婪算法选择准则为,
从剩余物品中选择可装入包的 pi /wi 值
最大的物品，这种策略也不能保证得到
最优解。
?解 n =4,w=[2,4,6,7],p=[6,10,12,13],c =
11时的最优解。
第 八 章：贪婪法
算法设计与分析 191
骑士巡游问题 (即最短路径 )
? x←{1};y←v -{1}
?对每个 v都包含于 y，如果存在从 1到 v的
边，则令 λ [v]为边的长度；否则令
λ [v]=∞,并设 λ [1]=0
?While y≠{ }
? 令 t包含于 y，使得 λ [t]为最小
? 将 t从 y移到 x
? 更新那些在 y中与 t相邻的顶点的标记
? end while (察看 7）
算法设计与分析 192
Kruskal算法
(1) 算法思想
? K r u s k a l算法每次选择 n- 1条边，所使用的
贪婪准则是：从剩下的边中选择一条不会产
生环路的具有最小耗费的边加入已选择的边
的集合中。注意到所选取的边若产生环路则
不可能形成一棵生成树。 K r u s k a l算法分 e
步，其中 e 是网络中边的数目。按耗费递增的
顺序来考虑这 e 条边，每次考虑一条边。当考
虑某条边时，若将其加入到已选边的集合中
会出现环路，则将其抛弃，否则，将它选入。
算法设计与分析 193
? / /在一个具有 n 个顶点的网络中找到一棵最小
生成树
? 令 T为所选边的集合，初始化 T=
? 令 E 为网络中边的集合
? w h i l e(E≠ )&&(| T |≠n- 1 ) {
? 令 (u,v)为 E中代价最小的边
? E=E- { (u,v) } / /从 E中删除边
? i f( (u,v)加入 T中不会产生环路）将（ u,v）加
入 T
? }
? i f(| T | = =n-1) T是最小耗费生成树
? e l s e 网络不是互连的，不能找到生成树
算法设计与分析 194
Kruskal算法所需要的数据类型
? template <class T>
? class EdgeNode {
? p u b l i c,
? operator T() const {return weight;}
? p r i v a t e,
? T weight;//边的高度
? int u,v;//边的端点
? } ;
算法设计与分析 195
WNetwork类
? template<class T>
? class WNetwork, virtual public Network
? {
? public,
? virtual void First(int i,int& j,T& c)=0;
? virtual void Next(int i,int& j,T& c)=0;
? } ;
算法设计与分析 196
Kr u s k a l算法的 C + +代码
? template<class T>
? bool UNetwork<T>::Kruskal(EdgeNode<T> t[])
? {// 使用 K r u s k a l算法寻找最小耗费生成树
? // 如果不连通则返回 false
? // 如果连通，则在 t [ 0, n - 2 ]中返回最小生成
树
? int n = Ve r t i c e s ( ) ;
? int e = Edges();
? / /设置网络边的数组
? InitializePos(); // 图遍历器
? EdgeNode<T> *E = new EdgeNode<T> [e+1];
? int k = 0; // E的游标
算法设计与分析 197
? for (int i = 1; i <= n; i++) { // 使所有边附属于 i
? int j;
? T c;
? First(i,j,c);
? while (j) { // j 邻接自 i
? if (i < j) {// 添加到达 E的边
? E[++k].weight = c;
? E[k].u = i;
? E[k].v = j;}
? Next(i,j,c);
? }
? }
算法设计与分析 198
? // 把边放入最小堆
? MinHeap<EdgeNode<T> > H(1);
? H.Initialize(E,e,e);
? UnionFind U(n); // 合并 /搜索结构
? // 根据耗费的次序来抽取边
? k = 0; // 此时作为 t的游标
? while (e && k < n - 1) {
? // 生成树未完成，尚有剩余边
? EdgeNode<T> x;
算法设计与分析 199
? H.DeleteMin(x); // 最小耗费边
? e - - ;
? int a = U.Find(x.u);
? int b = U.Find(x.v);
? if (a != b) {// 选择边
? t[k++] = x;
? U, U n i o n ( a,b ) ; }
? }
? D e a c t i v a t e P o s ( ) ;
? H, D e a c t i v a t e ( ) ;
? return (k == n - 1);
? }
算法设计与分析 200
Prim算法
?与 Kr u s k a l算法类似,P r i m算法通过
每次选择多条边来创建最小生成树。选
择下一条边的贪婪准则是：从剩余的边
中，选择一条耗费最小的边，并且它的
加入应使所有入选的边仍是一棵树。最
终，在所有步骤中选择的边形成一棵树。
相反，在 Kruskal 算法中所有入选的边集
合最终形成一个森林。
算法设计与分析 201
? / /假设网络中至少具有一个顶点
? 设 T为所选择的边的集合，初始化 T=
? 设 T V为已在树中的顶点的集合，置 T V= { 1 }
? 令 E为网络中边的集合
? w h i l e(E< > ) & & (| T | < > n-1) {
? 令（ u,v）为最小代价边，其中 u T V,v T V
? i f（没有这种边） b re a k
? E=E- { (u,v) } / /从 E中删除此边
? 在 T中加入边（ u,v）
? }
? if (| T | = =n- 1 ) T是一棵最小生成树
? else 网络是不连通的，没有最小生成树
算法设计与分析 202
旅行商问题的最小耗费
? template<class T>
? T AdjacencyWDigraph<T>::BBTSP(int v[])
? {// 旅行商问题的最小耗费算法
? // 定义一个最多可容纳 1000个活节点的最小
堆
? MinHeap<MinHeapNode<T> > H(1000);
? T *MinOut = new T [n+1];
? // 计算 MinOut[i] = 离开顶点 i的最小耗费边的
耗费
? T MinSum = 0; // 离开顶点 i的最小耗费边的数
目
算法设计与分析 203
? for (int i = 1; i <= n; i++) {
? T Min = NoEdge;
? for (int j = 1; j <= n; j++)
? if (a[i][j] != NoEdge &&(a[i][j] < Min || Min ==
NoEdge))
? Min = a[i][j];
? if (Min == NoEdge) return NoEdge; //此路不
通
? MinOut[i] = Min;
? MinSum += Min;
? }
? // 把 E-节点初始化为树根
算法设计与分析 204
? MinHeapNode<T> E;
? E.x = new int [n];
? for (i = 0; i < n; i++)
? E.x[i] = i + 1;
? E.s = 0; // 局部旅行路径为 x [ 1, 0 ]
? E.cc = 0; // 其耗费为 0
? E.rcost = MinSum;
? T bestc = NoEdge; // 目前没有找到旅行路径
? // 搜索排列树
? while (E.s < n - 1) {// 不是叶子
? if (E.s == n - 2) {// 叶子的父节点
? // 通过添加两条边来完成旅行
算法设计与分析 205
? // 检查新的旅行路径是不是更好
? if (a[E.x[n-2]][E.x[n-1]] != NoEdge &&
a[E.x[n-1]][1] != NoEdge && (E.cc +a[E.x[n-
2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc
== NoEdge)) {
? // 找到更优的旅行路径
? bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-
1]][1];
? E.cc = bestc;
? E.lcost = bestc;
? E, s + + ;
? H, I n s e r t ( E ) ; }
? else delete [] E.x;}
算法设计与分析 206
? else {// 产生孩子
? for (int i = E.s + 1; i < n; i++)
? if (a[E.x[E.s]][E.x[i]] != NoEdge) {
? // 可行的孩子,限定了路径的耗费
? T cc = E.cc + a[E.x[E.s]][E.x[i]];
? T rcost = E.rcost - MinOut[E.x[E.s]];
? T b = cc + rcost; //下限
? if (b < bestc || bestc == NoEdge) {
? // 子树可能有更好的叶子
? // 把根保存到最大堆中
? MinHeapNode<T> N;
? N.x = new int [n];
算法设计与分析 207
? for (int j = 0; j < n; j++)
? N.x[j] = E.x[j];
? N.x[E.s+1] = E.x[i];
? N.x[i] = E.x[E.s+1];
? N.cc = cc;
? N.s = E.s + 1;
? N.lcost = b;
? N.rcost = rcost;
? H, I n s e r t ( N ) ; }
? } // 结束可行的孩子
? delete [] E.x;} // 对本节点的处理结束
? try {H.DeleteMin(E);} // 取下一个 E-节点
算法设计与分析 208
? catch (OutOfBounds) {break;} // 没有未处理
的节点
? }
? if (bestc == NoEdge) return NoEdge; // 没有
旅行路径
? // 将最优路径复制到 v[1:n] 中
? for (i = 0; i < n; i++)
? v[i+1] = E.x[i];
? while (true) {// 释放最小堆中的所有节点
? delete [] E.x;
? try {H.DeleteMin(E);}
? catch (OutOfBounds) {break;}
? }return bestc;}
算法设计与分析 209
在互联网中计算一个最小生成
树的简单快速分布式算法
?广域网中一个核心问题是有效的多播
一条消息到目标组的所有成员。一种
最有效的多播一条消息的方法是沿着
连接组的所有成员的生成树的边发送
消息。在一般的通讯网络中构造一棵
最小生成树（ MST）。
算法设计与分析 210
算法设计与分析 211
? 一般的 MST算法
? 假定 G＝（ V,E）表示一个无向连通图，这
里 V代表顶点集,E代表边集。然后，假定 E中
的每条边关联了一个权值并且没有两个权值
是相等的。构造一个 MST的一般算法见图 1。
算法从创建｜ V｜个不同的子图开始，每个子
图包含一个顶点，接着，每个子图独立的选
择具有最小权值的边（该边把他和另外一个
子图连接起来），然后与该边现关联的两个
子图沿着这条边连接起来。步骤 4－ 6重复直
到所有的顶点都被连接起来。
算法设计与分析 212
? 通讯网络中的 MST算法
? 我们把通讯网络建模为一个无向连接图 G=
（ V,E）。这里节点集 V代表工作站（或处
理器）集，边集 E代表虚连接子集。如果两台
工作站（节点）之间存在一条可以交换消息
的通讯路径，那么我们说这两台工作站是虚
连接的。对每条路径，我们关联一个权值,权
值的大小为消息在两个端节点之间的往返时
间（ RTT）。
? MST算法分为两个阶段,初始化 阶段和 构
造 阶段。初始化阶段为图中的每一条边计算
往返时间 RTT并确保所有的权值都是唯一的。
构造阶段实现图 1中所给出的一般算法。以下
两节给出这两个阶段的细节。
算法设计与分析 213
算法设计与分析 214
?l label-树的标记,指出该消息是在
哪棵树中进行传递的。；
?l min_bridge_wt-最小桥权值,用于
计算本棵树的最小桥权值；
? 除此之外，每个节点还要管理以下数
据结构,
?l label-本节点所属树的标记 ；
算法设计与分析 215
? l cand_mst_heap-候选 MST堆,由和本节
点不属于同一棵树中的所有邻接点构成，这
些邻节点按照其与本节点相关联的边的权值
大小升序存储。更加确切的说，给定节点 vi的
不和 vi在同一棵树上的邻节点集 n1,n2,…,n m,则
vi的候选 MST堆 cand_mst_heap为有序的邻节
点序列,ni1,ni2,…,n im使得
weight(vi,ni1)<weight(vi,ni2)<…<weight(v i,nim)(
这里，,<”由 (1)式定义 ),
算法设计与分析 216
? l loc_min_bridge_wt-本节点最小桥权值,
把当前节点和另外一棵树中的某节点连接起
来的最小桥权值（也就是与本节点的候选
MST堆中的第一个结点相关联的边的权值）。
若无这样的边（ cand_mst_heap为空），就把
loc_min_bridge_wt设为 ∞。注意,最小桥权值
（ min_bridge_wt） 是该树中所有 本节点最小
权值 （ loc_min_bridge_wt） 的 最小值 。
算法设计与分析 217
?l mst_adj_list-最小生成树邻节点列
表,由和本节点属于同一棵树中的所有
邻接点构成。这样，所有在 候选 MST堆
中的节点集 并 (∪ )上所有 最小生成树邻
节点列表 中的节点集就是图 G中当前节
点的所有邻节点的集合。
算法设计与分析 218
算法设计与分析 219
算法设计与分析 220
算法设计与分析 221
算法设计与分析 222
算法设计与分析 223
图的遍历
?图（ g r a p h）是一个用线或边连接在
一起的顶点或节点的集合。正式一点的
说法是，图 G= (V,E) 是一个 V和 E的有限
集合，元素 V称为顶点（ vertice,也叫作
节点或点），元素 E称为边（ edge,也叫
作弧或连线）,E中的每一条边连接 V中
两个不同的顶点。可以用（ i,j）来表
示一条边，其中 i 和 j 是 E所连接的两个
顶点。
算法设计与分析 224
无向图的抽象数据类型描述
? 抽象数据类型 Graph {
? 顶点集合 V和边集合 E
? 操作
? C reate (n)：创建一个具有 n 个顶点、没有边的无向图
? Exist (i,j)：如果存在边（ i,j）则返回 t r u e，否则返
回 f a l s e
? Edges ( )：返回图中边的数目
? Ve rtices ( )：返回图中顶点的数目
? Add (i,j)：向图中添加边（ i,j）
? Delete (i,j)：删除边（ i,j）
? D e g ree (i)：返回顶点 i 的度
? I n D e g ree (i)：返回顶点 i 的度
? O u t D e g ree (i)：返回顶点 i 的度
算法设计与分析 225
有向图的抽象数据类型描述
? 抽象数据类型 Graph {
? C re a t e(n)：创建一个具有 n个顶点、没有边的有向
图
? E x i s t(i,j)：如果存在边（ i,j）则返回 t r u e，否则返
回 f a l s e
? E d g e s( )：返回图中边的数目
? Ve rt i c e s( )：返回图中顶点的数目
? A d d(i,j)：向图中添加边（ i,j）
? D e l e t e(i,j)：删除边（ i,j）
? D e g re e(i)：返回顶点 i 的度
? I n D e g re e(i)：返回顶点 i的入度
? O u t D e g r e e (i)：返回顶点 i的出度
算法设计与分析 226
无向图和有向图的描述
?一个 n顶点的图 G= (V,E)的邻接矩阵
（ adjacency matrix）是一个 n× n 矩阵 A，
A中的每一个元素是 0或 1。假设 V={1,
2,...,n}。
算法设计与分析 227
无向图和有向图的描述
? 1,将邻接矩阵映射到数组
?使用映射 A(i,j) =a[i ][ j ]可以将 n× n的邻
接矩阵映射到一个 (n+ 1 )× (n+1) 的整型
数组 a 中
? 2,时间需求
?使用邻接矩阵时，需要用 (n)时间来确定
邻接至或邻接于一个给定节点的集合。
寻找图中的边数也需要 (n)的时间
算法设计与分析 228
无向图和有向图的描述
?在 G（ G =(V,E),| V |= n,| e |= e）的邻接
压缩表（ p a c k e d - e d j a c e n c y - l i s
t）的定义中，使用了两个一维数组
h[ 0,n+ 1 ]和 l [ 0,x]，如果 G是有向图，
则 x=e- 1；如果 G是无向图，则 x= 2e- 1。
首先将所有邻接于顶点 1的顶点加入到 l
中，然后将所有邻接于顶点 2的顶点加
入到 l 中，再将邻接于顶点 3的顶点加入
到 l 中
算法设计与分析 229
无向图和有向图的描述
?在邻接链表（ l i n k e d - e d j a c e n c y -
l i s t）中，邻接表是作为链表保存的，
可以用类 C h a i n < i n t >（见程序 3 - 8）
来实现。另外，可使用一个 Chain<int>
类型的头节点数组 h 来跟踪这些邻接表。
? h[i].first 指向顶点 i 的邻接表中的第一个
节点。如果 x 指向链表 h[i] 中的一个节点，
那么 (i,x→data) 是图中的一条边。
算法设计与分析 230
加权有向图的耗费邻接矩阵
? template<class T>
? class AdjacencyWDigraph {
? friend AdjacencyWGraph<T>;
? p u b l i c,
? AdjacencyWDigraph (int Vertices = 10,T
noEdge = 0);
? ~AdjacencyWDigraph()
{Delete2DArray(a,n+1);}
? bool Exist(int i,int j) const;
? int Edges() const {return e;}
? int Vertices() const {return n;}
算法设计与分析 231
? AdjacencyWDigraph<T>& Add (int i,int j,
const T& w);
? AdjacencyWDigraph<T>& Delete(int i,int j);
? int OutDegree(int i) const;
? int InDegree(int i) const;
? p r i v a t e,
? T NoEdge; // 用于没有边存在的情形
? int n; // 顶点数目
? int e; // 边数
? T **a; // 二维数组
? } ;
算法设计与分析 232
? template<class T>
? AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices,T
noEdge)
? {// 构造函数
? n = Ve r t i c e s ;
? e = 0;
? NoEdge = noEdge;
? Make2DArray(a,n+1,n+1);
? / /初始化为没有边的图
? for (int i = 1; i <= n; i++)
? for (int j = 1; j <= n; j++)
? a[i][j] = NoEdge;
? }
? template<class T>
? bool AdjacencyWDigraph<T>::Exist(int i,int j) const
? {// 边 (i,j)存在吗?
? if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge) return false;
? return true;
? }
算法设计与分析 233
? template<class T>
? AdjacencyWDigraph<T>&
AdjacencyWDigraph<T>,:Add(int i,int j,const
T& w)
? {// 如果边 (i,j) 不存在，则将该边加入有向图
中
? if (i < 1 || j < 1 || i > n ||
? j > n || i == j || a[i][j] != NoEdge)
? throw BadInput();
? a[i][j] = w;
? e + + ;
? return *this;
? }
算法设计与分析 234
? template<class T>
? int AdjacencyWDigraph<T>::OutDegree(int i)
const
? {// 返回顶点 i的出度
? if (i < 1 || i > n) throw BadInput();
? // 计算顶点 i的出度
? int sum = 0;
? for (int j = 1; j <= n; j++)
? if (a[i][j] != NoEdge) sum++;
? return sum;
? }
算法设计与分析 235
? template<class T>
? int AdjacencyWDigraph<T>::InDegree(int i)
const
? {// 返回顶点 i的入度
? if (i < 1 || i > n) throw BadInput();
? // 计算顶点 i的入度
? int sum = 0;
? for (int j = 1; j <= n; j++)
? if (a[j][i] != NoEdge) sum++;
? return sum;
? }
算法设计与分析 236
? template<class T>
? AdjacencyWDigraph<T>&
AdjacencyWDigraph<T>,:Delete(int i,int j)
? { / /删除边 ( i,j ),
? if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)
? throw BadInput();
? a[i][j] = NoEdge;
? e - - ;
? return *this;
? }
算法设计与分析 237
加权图的耗费邻接矩阵
? template<class T>
? class AdjacencyWGraph, public AdjacencyWDigraph<T>
{
? p u b l i c,
? AdjacencyWGraph(int Vertices = 10,T noEdge = 0),
AdjacencyWDigraph<T>(Vertices,noEdge) {}
? AdjacencyWGraph<T>& Add(int i,int j,const T& w)
? { A d j a c e n c y W D i g r a p h < T >,, A d d ( i,j,w ) ;
? a[j][i] = w;
? return *this;}
? AdjacencyWGraph<T>& Delete(int i,int j)
? { A d j a c e n c y W D i g r a p h < T >,, D e l e t e ( i,j ) ;
? a[j][i] = NoEdge;
? return *this;}
? int Degree(int i) const {return OutDegree(i);}
? } ;
算法设计与分析 238
有向图的邻接矩阵
? class AdjacencyDigraph, public
AdjacencyWDigraph<int> {
? p u b l i c,
? AdjacencyDigraph(int Vertices = 10),
AdjacencyWDigraph<int>(Vertices,0) {}
? AdjacencyDigraph& Add(int i,int j)
? { A d j a c e n c y W D i g r a p h < i n t >,, A d d ( i,
j,1 ) ;
? return *this;}
? AdjacencyDigraph& Delete(int i,int j)
? { A d j a c e n c y W D i g r a p h < i n t >,, D e l e t e
( i,j ) ;
? return *this;}
? } ;
算法设计与分析 239
图的邻接矩阵
? class AdjacencyGraph, public AdjacencyWGraph<int>
? {
? p u b l i c,
? AdjacencyGraph(int Vertices = 10),
AdjacencyWGraph<int>(Vertices,0) {}
? AdjacencyGraph& Add(int i,int j)
? { A d j a c e n c y W G r a p h < i n t >,, A d d ( i,j,
1 ) ;
? return *this;}
? AdjacencyGraph& Delete(int i,int j)
? { A d j a c e n c y W G r a p h < i n t >,, D e l e t e ( i,
j ) ;
? return *this;}
? } ;
算法设计与分析 240
从链表中删除元素
? template<class T>
? Chain<T>& Chain<T>::Delete(T& x)
? {// 删除与 x匹配的元素
? // 如果不存在相匹配的元素，则引发异常 B a d
I n p u t
? ChainNode<T> *current = first,
? *trail = 0; // 指向 c u r r e n t之后的节点
? / /搜索匹配元素
? while (current && current->data != x) {
? trail = current;
? current = current->link;}
算法设计与分析 241
? if (!current) throw BadInput(); // 不存在匹配元
素
? / /在节点 c u r r e n t中找到匹配元素
? x = current->data; // 保存匹配元素
? // 从链表中删除 current 节点
? if (trail) trail->link = current->link;
? else first = current->link;
? delete current; // 释放节点
? return *this;
? }
算法设计与分析 242
邻接链描述的基类
? template<class T>
? class LinkedBase {
? friend class LinkedDigraph;
? friend class LinkedGraph;
? friend LinkedWDigraph<int>;
? friend LinkedWGraph<int>;
? p u b l i c,
? LinkedBase(int Vertices = 10)
? {n = V e r t i c e s ;
? e = 0;
算法设计与分析 243
? h = new Chain<T> [n+1];}
? ~LinkedBase() {delete [] h;}
? int Edges() const {return e;}
? int Vertices() const {return n;}
? int OutDegree(int i) const
? {if (i < 1 || i > n) throw OutOfBounds();
? return h[i].Length();}
? p r i v a t e,
? int n; //顶点数
? int e; // 边数
? Chain<T> *h; // 邻接矩阵
? } ;
算法设计与分析 244
图的遍历
? 邻接矩阵的遍历函数
? void InitializePos() {pos = new int [n+1];}
? void DeactivatePos() {delete [] pos;}
? template<class T>
? int AdjacencyWDigraph<T>::Begin(int i)
? { / /返回第一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? // 查找第一个邻接顶点
? for (int j = 1; j <= n; j++)
? if (a[i][j] != NoEdge) {// j 是第一个
? pos[i] = j;
? return j;}
? pos[i] = n + 1; // 没有邻接顶点
? return 0;
? }
算法设计与分析 245
? template<class T>
? int AdjacencyWDigraph<T>::NextVertex(int i)
? {// 返回下一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? // 寻找下一个邻接顶点
? for (int j = pos[i] + 1; j <= n; j++)
? if (a[i][j] != NoEdge) {// j 是下一个顶点
? pos[i] = j; return j;}
? pos[i] = n + 1; // 不存在下一个顶点
? return 0;
? }
算法设计与分析 246
加入到 L i n k e d B a s e类中
? void InitializePos()
? {pos = new ChainIterator<T> [n+1];}
? void DeactivatePos() {delete [] pos;}
算法设计与分析 247
邻接链表的遍历函数
? int LinkedDigraph::Begin(int i)
? {// 返回第一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? int *x = pos[i].Initialize(h[i]);
? return (x)? *x, 0;
? }
? int LinkedDigraph::NextVertex(int i)
? {// 返回下一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? int *x = pos[i].Next();
? return (x)? *x, 0;
? }
算法设计与分析 248
链接加权有向图的遍历函数
? template<class T> ? int LinkedWDigraph<T>::Begin(int i)
? {// 返回第一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? GraphNode<T> *x = pos[i].Initialize(h[i]);
? return (x)? x->vertex, 0;
? }
? template<class T>
? int LinkedWDigraph<T>::NextVertex(int i)
? {// 返回下一个与顶点 i邻接的顶点
? if (i < 1 || i > n) throw OutOfBounds();
? GraphNode<T> *x = pos[i].Next();
? return (x)? x->vertex, 0;
? }
算法设计与分析 249
抽象类 N e t w o r k
? class Network {
? p u b l i c,
? virtual int Begin(int i) = 0;
? virtual int NextVertex(int i) = 0;
? virtual void InitializePos() = 0;
? virtual void DeactivatePos() = 0;
? }
算法设计与分析 250
图的搜索算法
1
2
3
4
6
5
8
7
9
算法设计与分析 251
图的搜索算法
? 1 宽度优先搜索 伪代码。
? / /从顶点 v 开始的宽度优先搜索
? 把顶点 v标记为已到达顶点；
? 初始化队列 Q，其中仅包含一个元素 v;
? while (Q不空 ) {
? 从队列中删除顶点 w;
? 令 u 为邻接于 w 的顶点 ;
? while (u) {
? if ( u 尚未被标记 ) {
? 把 u 加入队列；
? 把 u 标记为已到达顶点； }
? u = 邻接于 w 的下一个顶点；
? }
? }
算法设计与分析 252
BFS代码
? void Network::BFS(int v,int reach[],int label) ? {// 宽度优先搜索
? LinkedQueue<int> Q;
? InitializePos(); //初始化图遍历器数组
? reach[v] = label;
? Q, A d d ( v ) ;
? while (!Q.IsEmpty()) {
? int w;
? Q.Delete(w); // 获取一个已标记的顶点
? int u = Begin(w);
? while (u) {// 访问 w的邻接顶点
? if (!reach[u]) {// 一个未曾到达的顶点
? Q, A d d ( u ) ;
? reach[u] = label;} // 标记已到达该顶点
? u = NextVertex(w); // 下一个与 w邻接的顶点
? }
? }
? DeactivatePos(); // 释放遍历器数组
? }
算法设计与分析 253
邻接矩阵描述中 B F S的直接实现
? template<class T>
? void AdjacencyWDigraph<T>::BFS (int v,int reach[],int label)
? {// 宽度优先搜索
? LinkedQueue<int> Q;
? reach[v] = label;
? Q, A d d ( v ) ;
? while (!Q.IsEmpty()) {
? int w;
? Q.Delete(w); // 获取一个已标记的顶点
? // 对尚未标记的、邻接自 w的顶点进行标记
? for (int u = 1; u <= n; u++)
? if (a[w][u] != NoEdge && !reach[u]) {
? Q.Add(u); // u 未被标记
? reach[u] = label;}
? }
? }
算法设计与分析 254
链接图和有向图 B F S的直接实现
? void LinkedDigraph::BFS(int v,int reach[],int label) ? {// 宽度优先搜索
? LinkedQueue<int> Q;
? reach[v] = label;
? Q, A d d ( v ) ;
? while (!Q.IsEmpty()) {
? int w;
? Q.Delete(w); // 获取一个已标记的顶点
? // 使用指针 p沿着邻接表进行搜索
? ChainNode<int> *p;
? for (p = h[w].First(); p; p = p->link) {
? int u = p->data;
? if (!reach[u]) {// 一个尚未到达的顶点
? Q, A d d ( u ) ;
? reach[u] = label;}
? }
? }
? }
算法设计与分析 255
深度优先搜索
算法设计与分析 256
深度优先搜索 DFS代码
? void Network::DFS(int v,int reach[],int label)
? {// 深度优先搜索
? InitializePos(); // 初始化图遍历器数组
? d f s ( v,reach,label); // 执行 d f s
? DeactivatePos(); // 释放图遍历器数组
? }
? void Network::dfs(int v,int reach[],int label)
? {// 实际执行深度优先搜索的代码
? reach[v] = label;
? int u = Begin(v);
? while (u) {// u邻接至 v
? if (!reach[u]) dfs(u,reach,label);
? u = NextVe r t e x ( v ) ; }
? }
算法设计与分析 257
应用
?寻找路径
?连通图及其构件
?生成树
算法设计与分析 258
在图中寻找一个路径
? bool Network::FindPath (int v,int w,int &length,int path[]) ? {// 寻找一条从 v 到 w的路径,返回路径的长度，并将路径存入数组 p a t
h [ 0, l e n g t h ]
? / /如果不存在路径，则返回 false
? / /路径中的第一个顶点总是 v
? path[0] = v;
? length = 0; // 当前路径的长度
? if (v == w) return true;
? / /为路径的递归搜索进行初始化
? int n = Ve r t i c e s ( ) ;
? InitializePos(); // 遍历器
? int *reach = new int [n+1];
? for (int i = 1; i <= n; i++)
? reach[i] = 0;
? // 搜索路径
? bool x = findPath(v,w,length,path,reach);
? D e a c t i v a t e P o s ( ) ;
? delete [] reach;
? return x;
? }
算法设计与分析 259
? bool Network::findPath(int v,int w,int &length,int path[],int
reach[])
? {// 实际搜索 v到 w的路径，其中 v != w,
? // 按深度优先方式搜索一条到达 w的路径
? reach[v] = 1;
? int u = Begin(v);
? while (u) {
? if (!reach[u]) {
? l e n g t h + + ;
? path[length] = u; // 将 u 加入 p a t h
? if (u == w) return true;
? if (findPath(u,w,length,path,reach))
? return true;
? // 不存在从 u 到 w的路径
? length--; //删除 u
? }
? u = NextVe r t e x ( v ) ; }
? return false;
? }
算法设计与分析 260
确定无向图是否连通
? class Undirected, virtual public Network { ? p u b l i c,
? bool Connected();
? } ;
? bool Undirected::Connected()
? {// 当且仅当图是连通的，则返回 true
? int n = Ve r t i c e s ( ) ;
? // 置所有顶点为未到达顶点
? int *reach = new int [n+1];
? for (int i = 1; i <= n; i++)
? reach[i] = 0;
? // 对从顶点 1出发可到达的顶点进行标记
? DFS(1,reach,1);
? // 检查是否所有顶点都已经被标记
? for (int i = 1; i <= n; i++)
? if (!reach[i]) return false;
? return true;
? }
算法设计与分析 261
构件标识
? int Undirected::LabelComponents(int L[]) ? {// 构件标识
? // 返回构件的数目,并用 L [ 1, n ]表示构件标号
? int n = Ve r t i c e s ( ) ;
? // 初始时，所有顶点都不属于任何构件
? for (int i = 1; i <= n; i++)
? L[i] = 0;
? int label = 0; // 最后一个构件的 ID
? // 识别构件
? for (int i = 1; i <= n; i++)
? if (!L[i]) {// 未到达的顶点
? // 顶点 i 属于一个新的构件
? l a b e l + + ;
? BFS(i,L,label);} // 标记新构件
? return label;
? }
算法设计与分析 262
算法设计与分析 263
算法思想
?回溯（ b a c k t r a c k i n g）
是一种系统地搜索问题解答的方法。
?解空间（ solution space）
?组织解空间
第九章 回溯
算法设计与分析 264
3× 3迷宫的解空间
第九章 回溯
算法设计与分析 265
0 / 1背包问题
第九章 回溯
算法设计与分析 266
迷宫老鼠
0 0 0
0 1 1
0 0 0
a
1 1 0
0 1 1
0 0 0
b
1 1 1
0 1 1
0 0 0
c
第九章 回溯
算法设计与分析 267
迷宫老鼠
? bool FindPath（）
? {path = new Stack<Position>(m * m - 1);
? Position off s e t [ 4 ] ;
? o ffset[0].row = 0; offset[0].col = 1;
? o ffset[l].row = 1; offset[l].col = 0;
? o ffset[2].row = 0; offset[2].col = -1;
? o ffset[3].row = -1; offset[3].col = 0;
? for (int i = 0; i <= m+l; i++) {
? maze [0] [i] = maze[m+l] [i] = 1;
? maze [i] [0] = maze[i] [m+l] = 1;
? }
? Position here;
? here.row = 1;
? here.col = 1;
算法设计与分析 268
迷宫老鼠
maze [i] [i] = 1;
int option = 0;
int LastOption = 3;
while (here.row != m || here.col != m) {
int r,c;
while (option <= LastOption) {
r = here.row + off s e t [ o p t i o n ], r o w ;
c = here.col + off s e t [ o p t i o n ], c o l ;
if (maze[r][c] == 0) break;
option++;
}
if (option <= LastOption)
{
算法设计与分析 269
迷宫老鼠
p a t h - > A d d ( h e r e ) ;
here.row = r; here.col = c;
maze [r] [c] = 1;
option = 0;
}
else {
if (path->IsEmpty()) return false;
Position next;
p a t h - > D e l e t e ( n e x t ) ;
if (next.row == here,row)
option = 2 + next.col - here.col;
else option = 3 + next.row - here.row;
here = next;
}
}
return true;
}
算法设计与分析 270
[0/1背包问题 ] 考察如下背包
问题,
n= 3,
w= [ 2 0,1 5,1 5 ],
p= [ 4 0,2 5,2 5 ]
且 c= 3 0。
算法设计与分析 271
0 / 1背包问题
算法设计与分析 272
旅行商问题
?在这个问题中，给出一个 n 顶点网络
（有向或无向），要求找出一个包含所
有 n 个顶点的具有最小耗费的环路。任
何一个包含网络中所有 n 个顶点的环路
被称作一个旅行（ t o u r）。在旅行商
问题中，要设法找到一条最小耗费的旅
行
算法设计与分析 273
旅行商问题
1
4
2
3
6
4 5
10
20
30
算法设计与分析 274
旅行商问题
D
F
A
N
B
I
O
C
H
L
G
M
J
E
P
K
Q
算法设计与分析 275
小结
? 1) 定义一个解空间，它包含问题的解。
? 2) 用适于搜索的方式组织该空间。
? 3) 用深度优先法搜索该空间，利用限界函数
避免移动到不可能产生解的子空间。
? 回溯算法的一个有趣的特性是在搜索执行的
同时产生解空间。在搜索期间的任何时刻，
仅保留从开始节点到当前 E-节点的路径。因
此，回溯算法的空间需求为 O（从开始节点起
最长路径的长度）。这个特性非常重要，因
为解空间的大小通常是最长路径长度的指数
或阶乘。所以如果要存储全部解空间的话，
再多的空间也不够用。
算法设计与分析 276
3着色问题
算法设计与分析 277
3着色问题
算法设计与分析 278
8皇后问题
算法设计与分析 279
8皇后问题
算法设计与分析 280
一般回溯
?货箱装船
?考察了用最大数量的货箱装船的问题。
现在对该问题做一些改动。在新问题中，
有两艘船,n 个货箱。第一艘船的载重
量是 c1，第二艘船的载重量是 c2,wi 是
货箱 i 的重量
算法设计与分析 281
货箱装船
?当 n= 3,c1 =c2 = 5 0,w=[10,40,40] 时，
可将货箱 1,2装到第一艘船上，货箱 3装
到第二艘船上。如果 w= [ 2 0,4 0,4 0 ]，
则无法将货箱全部装船
算法设计与分析 282
货箱装船
?第一种回溯算法
?假定 n= 4,w= [ 8,6,2,3 ],c1 = 1 2。
算法设计与分析 283
货箱装船
算法设计与分析 284
货箱装船
? template<class T>
? class Loading {
? friend MaxLoading(T [],T,int);
? p r i v a t e,
? void maxLoading(int i);
? int n;
? T *w,
? c,
? c w,
? bestw;
? } ;
算法设计与分析 285
货箱装船
? template<class T>
? void Loading<T>::maxLoading(int i)
? {
? if (i > n) {
? if (cw > bestw) bestw = cw;
? r e t u r n ; }
? if (cw + w[i] <= c) {
? cw += w[i];
? m a x L o a d i n g ( i + 1 ) ;
? cw -= w[i];}
? maxLoading(i+1);
? }
算法设计与分析 286
货箱装船
? template<class T>
? T MaxLoading(T w[],T c,int n)
? {
? Loading<T> X; X.w = w;
? X.c = c;
? X.n = n;
? X.bestw = 0;
? X.cw = 0;
? X, m a x L o a d i n g ( 1 ) ;
? return X.bestw;
? }
算法设计与分析 287
货箱装船
? 第二种回溯方法
? 通过不移动到不可能包含比当前最优解还要
好的解的右子树，能提高函数 m a x L o a d i
n g的性能。令 b e s t w为目前最优解的重量,
Z为解空间树的第 i 层的一个节点,c w的定义
如前。以 Z为根的子树中没有叶节点的重量会
超过 c w + r，其中
为剩余货箱的重量。因此，当 c w + r≤bestw时，
没有必要去搜索 Z的右子树。
?
??
?
n
ij
jwr
1
][
算法设计与分析 288
货箱装船
? template<class T>
? void Loading<T>::maxLoading(int i)
? {if (i > n) {
? bestw = cw;
? r e t u r n ; }
? r -= w[i];
? if (cw + w[i] <= c) {
? cw += w[i];
? m a x L o a d i n g ( i + 1 ) ;
? cw -= w[i];}
? if (cw + r > bestw)
? m a x L o a d i n g ( i + 1 ) ;
? r += w[i];
? }
算法设计与分析 289
货箱装船
template<class T>
T MaxLoading(T w[],T c,int n)
{
Loading<T> X;
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
X, m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
算法设计与分析 290
货箱装船 (最优装载 ) ? template<class T>
? void Loading<T>::maxLoading(int i)
? { if (i > n) {
? for (int j = 1; j <= n; j++)
? bestx[j] = x[j];
? bestw = cw; return;}
? r -= w[i];
? if (cw + w[i] <= c) {
? x[i] = 1;
? cw += w[i];
? m a x L o a d i n g ( i + 1 ) ;
? cw -= w[i];}
? if (cw + r > bestw) {
? x[i] = 0;
? m a x L o a d i n g ( i + 1 ) ; }
? r += w[i];
? }
算法设计与分析 291
货箱装船 (最优装载 )
? template<class T>
? T MaxLoading(T w[],T c,int n,int bestx[])
? {Loading<T> X;
? X.x = new int [n+1];
? X.w = w;
? X.c = c;
? X.n = n;
? X.bestx = bestx;
? X.bestw = 0;
? X.cw = 0;
? X.r = 0;
? for (int i = 1; i <= n; i++)
? X.r += w[i];
? X, m a x L o a d i n g ( 1 ) ;
? delete [] X.x;
? return X.bestw;
? }
算法设计与分析 292
货箱装船
? bestx 可以被更新 O ( 2n )次，故
axLoading 的复杂性为 O (n2n )。使用下
列方法之一，复杂性可降为 O ( 2n ),
? 1) 首先运行程序 2的代码，以决定最优
装载重量，令其为 W。然后运行程序 3的
一个修改版本。该版本以 b e s t w = W开
始运行，当 c w + r≥b e s t w时搜索右子
树，第一次到达一个叶节点时便终止
（即 i > n）。
算法设计与分析 293
货箱装船
2) 修改程序 3的代码以不断保留从根到当
前最优叶的路径。尤其当位于 i 层节点
时，则到最优叶的路径由 x [j]（ 1≤j<i）
和 b e s tx [ j ]（ j≤i≤n）给出。按照这种
方法，算法每次回溯一级，并在 bestx中
存储一个 x [ i ]。由于算法回溯所需时间
为 O ( 2n )，因此额外开销为 O ( 2n )。
算法设计与分析 294
货箱装船 (迭代 )
? template<class T>
? T MaxLoading(T w[],T c,int n,int bestx[])
? {
? int i = 1;
? int *x = new int [n+1];
? T bestw = 0,
? cw = 0,
? r = 0;
? for (int j = 1; j <= n; j++)
? r += w[j];
算法设计与分析 295
? while (true) {
? while (i <= n && cw + w[i] <= c) {
? r -= w[i];
? cw += w[i];
? x[i] = 1;
? i + + ;
? }
? if (i > n) {
? for (int j = 1; j <= n; j++)
? bestx[j] = x[j];
? bestw = cw;}
? else {
? r -= w[i];
? x[i] = 0;
? i + + ; }
算法设计与分析 296
? while (cw + r <= bestw) {
? i - - ;
? while (i > 0 && !x[i]) {
? r += w[i];
? i - - ;
? }
? if (i == 0) {delete [] x;
? return bestw;}
? x[i] = 0;
? cw -= w[i];
? i + + ;
? }
? }
? }
算法设计与分析 297
0/1背包问题
?考察一个背包例子,n= 4,c= 7,p=
[ 9,1 0,7,4 ],w= [ 3,5,2,1 ]。这些
对象的收益密度为 [ 3,2,3, 5,4 ]。
算法设计与分析 298
0 / 1背包问题
算法设计与分析 299
K n a p
? template<class Tw,class Tp>
? class Knap {
? friend Tp Knapsack(Tp *,Tw *,Tw,int);
? p r i v a t e,
? Tp Bound(int i);
? void Knapsack(int i);
? Tw c;
? int n;
? Tw *w;
? Tp *p;
? Tw cw;
? Tp cp;
? Tp bestp;
? } ;
算法设计与分析 300
B o u n d (限界函数 )
? template<class Tw,class Tp>
? Tp Knap<Tw,Tp>::Bound(int i)
? {
? Tw cleft = c - cw;
? Tp b = cp;
? while (i <= n && w[i] <= cleft) {
? cleft -= w[i];
? b += p[i];
? i + + ;
? }
? if (i <= n) b += p[i]/w[i] * cleft;
? return b;
? }
算法设计与分析 301
Knapsack (迭代函数 )
? template<class Tw,class Tp>
? void Knap<Tw,Tp>::Knapsack(int i)
? {
? if (i > n) {
? bestp = cp;
? r e t u r n ; }
? if (cw + w[i] <= c) {
? cw += w[i];
? cp += p[i];
? K n a p s a c k ( i + 1 ) ;
? cw -= w[i];
? cp -= p[i];}
? if (Bound(i+1) > bestp)
? K n a p s a c k ( i + 1 ) ;
? }
算法设计与分析 302
Object类 (按密度排序 )
? class Object {
? friend int Knapsack(int *,int *,int,int);
? p u b l i c,
? int operator<=(Object a) const
? {return (d >= a.d);}
? p r i v a t e,
? int ID;
? float d;
? } ;
算法设计与分析 303
? template<class Tw,class Tp>
? Tp Knapsack(Tp p[],Tw w[],Tw c,int n)
? {
? Tw W = 0;
? Tp P = 0;
? Object *Q = new Object [n];
? for (int i = 1; i <= n; i++) {
? Q[i-1].ID = i;
? Q[i-1].d = 1.0*p[i]/w[i];
? P += p[i];
? W += w[i];
? }
算法设计与分析 304
? if (W <= c) return P;
? MergeSort(Q,n);
? K n a p < Tw,Tp> K;
? K.p = new Tp [n+1];
? K.w = new Tw [n+1];
? for (i = 1; i <= n; i++) {
? K.p[i] = p[Q[i-1].ID];
? K.w[i] = w[Q[i-1].ID];
? }
算法设计与分析 305
? K.cp = 0;
? K.cw = 0;
? K.c = c;
? K.n = n;
? K.bestp = 0;
? K, K n a p s a c k ( 1 ) ;
? delete [] Q;
? delete [] K.w;
? delete [] K.p;
? return K.bestp;
? }
算法设计与分析 306
最大完备子图
1
4
2
3
5
1
2
5
3 4
算法设计与分析 307
最大完备子图 ? void AdjacencyGraph::maxClique(int i)
? {
? if (i > n) {
? for (int j = 1; j <= n; j++)
? bestx[j] = x[j];
? bestn = cn;
? r e t u r n ; }
? int OK = 1;
? for (int j = 1; j < i; j++)
? if (x[j] && a[i][j] == NoEdge) {
? OK = 0;
? b r e a k ; }
算法设计与分析 308
? if (OK) {
? x[i] = 1;
? c n + + ;
? m a x C l i q u e ( i + 1 ) ;
? x[i] = 0;
? c n - - ; }
? if (cn + n - i > bestn) {
? x[i] = 0;
? m a x C l i q u e ( i + 1 ) ; }
? }
算法设计与分析 309
? int AdjacencyGraph::MaxClique(int v[])
? {
? x = new int [n+1];
? cn = 0;
? bestn = 0;
? bestx = v;
? m a x C l i q u e ( 1 ) ;
? delete [] x;
? return bestn;
? }
算法设计与分析 310
旅行商问题 (预处理程序 )
? template<class T>
? T AdjacencyWDigraph<T>::TSP(int v[])
? {x = new int [n+1];
? for (int i = 1; i <= n; i++)
? x[i] = i;
? bestc = NoEdge;
? bestx = v;
? cc = 0;
? t S P ( 2 ) ;
? delete [] x;
? return bestc;
? }
算法设计与分析 311
旅行商问题 (迭代回溯算法 )
? void AdjacencyWDigraph<T>::tSP(int i)
? {
? if (i == n) {
? if (a[x[n-1]][x[n]] != NoEdge &&
? a[x[n]][1] != NoEdge &&
? (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc ||
? bestc == NoEdge)) {
? for (int j = 1; j <= n; j++)
? bestx[j] = x[j];
? bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}
? }
算法设计与分析 312
? else {
? for (int j = i; j <= n; j++)
? if (a[x[i-1]][x[j]] != NoEdge &&
? (cc + a[x[i-1]][x[i]] < bestc ||
? bestc == NoEdge)) {
? Swap(x[i],x[j]);
? cc += a[x[i-1]][x[i]];
? t S P ( i + 1 ) ;
? cc -= a[x[i-1]][x[i]];
? Swap(x[i],x[j]);}
? }
? }
算法设计与分析 313
电路板排列
?例 11 令 n=8,m= 5。集合 B和 L如下,
? B= {b1,b2,b3,b4,b5,b6,b7,b8 }
? L= {N1,N2,N3,N4,N5 }
? N1 = {b4,b5,b6 }
? N2 = {b2,b3 }
? N3 = {b1,b3 }
? N4 = {b3,b6 }
? N5 = {b7,b8 }
算法设计与分析 314
电路板排列
?令 x 为电路板的一个排列。电路板 xi 被
放臵到机箱的插槽 i 中。 d e n s i t y(x) 为
机箱中任意一对相邻插槽间所连电线数
目中的最大值。
? b1 b2 b3 b4 b5 b6 b7 b8
? 1 2 3 4 5 6 7 8
N1
N2 N4 N5
N3
算法设计与分析 315
电路板排列 Board的类定义
? class Board {
? friend ArrangeBoards(int**,int,int,int []);
? p r i v a t e,
? void BestOrder(int i,int cd);
? int *x,
? * b e s t x,
? * t o t a l,
? * n o w,b e s t d,
? n,
? m,
? * * B ;
? } ;
算法设计与分析 316
电路板排列 搜索排列树
? void Board::BestOrder(int i,int cd)
? {
? if (i == n) {
? for (int j = 1; j <= n; j++)
? bestx[j] = x[j];
? bestd = cd;}
? else
? for (int j = i; j <= n; j++) {
? int ld = 0;
? for (int k = 1; k <= m; k++) {
? now[k] += B[x[j]][k];
算法设计与分析 317
? if (now[k] > 0 && total[k] != now[k])
? l d + + ;
? }
? if (cd > ld) ld = cd;
? if (ld < bestd) {
? Swap(x[i],x[j]);
? BestOrder(i+1,ld);
? Swap(x[i],x[j]);}
? for (k = 1; k <= m; k++)
? now[k] -= B[x[j]][k];
? }
? }
算法设计与分析 318
电路板排列 BestOrder的预处理
? int ArrangeBoards(int **B,int n,int m,int
bestx[ ])
? {
? Board X;
? X.x = new int [n+1];
? X.total = new int [m+1];
? X.now = new int [m+1];
? X.B = B;
? X.n = n;
? X.m = m;
? X.bestx = bestx;
? X.bestd = m + 1;
第九章 回溯
算法设计与分析 319
? for (int i = 1; i <= m; i++) {
? X.total[i] = 0;
? X.now[i] = 0;
? }
? for (i = 1; i <= n; i++) {
? X.x[i] = i;
? for (int j = 1; j <= m; j++)
? X.total[j] += B[i][j];
? }
? X, B e s t O r d e r ( 1,0 ) ;
? delete [] X.x;
? delete [] X.total;
? delete [] X.now;
? return X.bestd;
第九章 回溯
算法设计与分析 320
分枝定界
? 算法思想
? 分枝定界（ branch and bound）是另一种系
统地搜索解空间的方法，它与回溯法的主要
区
别在于对 E-节点的扩充方式。每个活节点有
且仅有一次机会变成 E-节点。当一个节点变
为 E-节点时，则生成从该节点移动一步即可
到达的所有新节点。在生成的节点中，抛弃
那些不可能导出（最优）可行解的节点，其
余节点加入活节点表，然后从表中选择一个
节点作为下一个 E-节点。从活节点表中取出
所选择的节点并进行扩充，直到找到解或活
动表为空，扩充过程才结束。
算法设计与分析 321
算法思想
? 1) 先进先出（ F I F O） 即从活节点表中取出
节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
? 2) 最小耗费或最大收益法在这种模式中，每
个节点都有一个对应的耗费或收益。如果查
? 找一个具有最小耗费的解，则活节点表可用
最小堆来建立，下一个 E-节点就是具有最小
耗费的活节点；如果希望搜索一个具有最大
收益的解，则可用最大堆来构造活节点表，
下一个 E-节点是具有最大收益的活节点
算法设计与分析 322
算法思想
? 例 8-1 [迷宫老鼠 ] 考察图 4-3a 给出的迷宫老鼠
例子和图 4 - 1的解空间结构。使用 F I F O分
枝定界，初始时取（ 1,1）作为 E-节点且活
动队列为空。迷宫的位臵（ 1,1）被臵为 1，
以免再次返回到这个位臵。（ 1,1）被扩充，
它的相邻节点（ 1,2）和（ 2,1）加入到队
列中（即活节点表）。为避免再次回到这两
个位臵，将位臵（ 1,2）和（ 2,1）臵为 1。
此时迷宫如图 8 - 1 a所示,E-节点（ 1,1）被
删除。
算法设计与分析 323
算法思想
? 1 1 0 1 1 1 1 1 1
? 1 1 1 1 1 1 1 1 1
? 0 0 0 0 0 0 1 0 0
? a） b） c）
?图 8-1 迷宫问题的 F I F O分枝定界方法
算法设计与分析 324
算法思想
? 例 8-2 [0/1背包问题 ] 下面比较分别利用 F I F
O分枝定界和最大收益分枝定界方法来解决如
下背包问题,n=3,w=[20,15,15],p=[40,25,25],
c= 3 0。 F I F O分枝定界利用一个队列来记录
活节点，节点将按照 F I F O顺序从队列中取
出；而最大收益分枝定界使用一个最大堆，
其中的 E-节点按照每个活节点收益值的降序，
或是按照活节点任意子树的叶节点所能获得
的收益估计值的降序从队列中取出
算法设计与分析 325
算法设计与分析 326
算法思想
?可以看到，工作在解空间树上的 F I F O
分枝定界方法非常象从根节点出发的宽
度优先搜索。
?它们的主要区别是在 F I F O分枝定界中
不可行的节点不会被搜索。
?最大收益分枝定界算法以解空间树中的
节点 A作为初始节点。
算法设计与分析 327
算法思想
?例 8-3 [旅行商问题 ] 对于 图 4 - 4的四城市
旅行商问题，其对应的解空间为 图 4 - 5
所示的排列树。
算法设计与分析 328
应用
?货箱装船
? 1,FIFO分枝定界
?第 4章的货箱装船问题主要是寻找第一
条船的最大装载方案。这个问题是一个
子集选择问题，它的解空间被组织成一
个子集树。对程序 4 - 1进行改造，即得
到程序 8 - 1中的 F I F O分枝定界代码。
程序 8 - 1只是寻找最大装载的重量。
算法设计与分析 329
货箱装船
? template<class T>
? void AddLiveNode(LinkedQueue<T> &Q,T wt,
T& bestw,int i,int n)
? {if (i == n) {// 叶子
? if (wt > bestw) bestw = wt;}
? else Q.Add(wt); // 不是叶子
? }
? template<class T>
? T MaxLoading(T w[],T c,int n)
算法设计与分析 330
? {// 返回最优装载值
? // 使用 F I F O分枝定界算法
? // 为层次 1 初始化
? LinkedQueue<T> Q; // 活节点队列
? Q.Add(-1); //标记本层的尾部
? int i = 1; // E-节点的层
? T Ew = 0,// E-节点的权值
? bestw = 0; // 目前的最优值
? // 搜索子集空间树
? while (true) {
? // 检查 E-节点的左孩子
? if (Ew + w[i] <= c) // x[i] = 1
算法设计与分析 331
? AddLiveNode(Q,Ew + w[i],bestw,i,n);
? // 右孩子总是可行的
? AddLiveNode(Q,Ew,bestw,i,n); // x[i] = 0
? Q.Delete(Ew); // 取下一个 E-节点
? if (Ew == -1) { // 到达层的尾部
? if (Q.IsEmpty()) return bestw;
? Q.Add(-1); //添加尾部标记
? Q.Delete(Ew); // 取下一个 E-节点
? i++;} // Ew的层
? }
? }
算法设计与分析 332
货箱装船 改进
? template<class T>
? T MaxLoading(T w[],T c,int n)
? {// 返回最优装载值
? // 使用 F I F O分枝定界算法
? // 为层 1初始化
? LinkedQueue<T> Q; // 活节点队列
? Q, A d d ( - 1 ) ; / /标记本层的尾部
? int i = 1; // E-节点的层
? T Ew = 0,// E-节点的重量
? bestw = 0; // 目前的最优值
算法设计与分析 333
? r = 0; // E-节点中余下的重量
? for (int j = 2; j <= n; j++)
? r += w[i];
? // 搜索子集空间树
? while (true) {
? // 检查 E-节点的左孩子
? T wt = Ew + w[i]; // 左孩子的权值
? if (wt <= c) { // 可行的左孩子
? if (wt > bestw) bestw = wt;
? // 若不是叶子，则添加到队列中
? if (i < n) Q.Add(wt);}
算法设计与分析 334
? // 检查右孩子
? if (Ew + r > bestw && i < n)
? Q.Add(Ew); // 可以有一个更好的叶子
? Q.Delete(Ew); // 取下一个 E-节点
? if (Ew == -1) { // 到达层的尾部
? if (Q.IsEmpty()) return bestw;
? Q.Add(-1); //添加尾部标记
? Q.Delete(Ew); // 取下一个 E-节点
? i++; // E-节点的层
? r -= w[i];} // E-节点中余下的重量
? }
? }
算法设计与分析 335
货箱装船 寻找最优子集
?类 Q N o d e
? template<class T>
? class QNode {
? p r i v a t e,
? QNode *parent; // 父节点指针
? bool LChild; // 当且仅当是父节点的左孩
子时，取值为 t r u e
? T weight; // 由到达本节点的路径所定义
的部分解的值
? } ;
算法设计与分析 336
计算最优子集的分枝定界算法
? template<class T>
? Void
AddLiveNode(LinkedQueue<QNode<T>*>
&Q,T wt,int i,int n,T bestw,QNode<T> *E,
? QNode<T> *&bestE,int bestx[],bool ch)
? {// 如果不是叶节点，则向队列 Q中添加一个 i
//层、重量为 w t的活节点
? // 新节点是 E的一个孩子。当且仅当新节点是
//左孩子时,c h为 t r u e。
? // 若是叶子，则 c h取值为 b e s t x [ n ]
? if (i == n) {// 叶子
? if (wt == bestw) {
算法设计与分析 337
? // 目前的最优解
? bestE = E;
? bestx[n] = ch;}
? r e t u r n ; }
? // 不是叶子,添加到队列中
? QNode<T> *b;
? b = new QNode<T>;
? b->weight = wt;
? b->parent = E;
? b->LChild = ch;
? Q, A d d ( b ) ;
? }
算法设计与分析 338
? template<class T>
? T MaxLoading(T w[],T c,int n,int bestx[])
? {// 返回最优装载值，并在 b e s t x中返回最优
//装载
? // 使用 F I F O分枝定界算法
? // 初始化层 1
? LinkedQueue<QNode<T>*> Q; // 活节点队列
? Q, A d d ( 0 ) ; // 0 代表本层的尾部
? int i = 1; // E-节点的层
? T Ew = 0,// E-节点的重量
? bestw = 0; // 迄今得到的最优值
? r = 0; // E-节点中余下的重量
? for (int j = 2; j <= n; j++)
算法设计与分析 339
? r += w[i];
? QNode<T> *E = 0,// 当前的 E-节点
? * b e s t E ; // 目前最优的 E-节点
? // 搜索子集空间树
? while (true) {
? // 检查 E-节点的左孩子
? T wt = Ew + w[i];
? if (wt <= c) {// 可行的左孩子
? if (wt > bestw) bestw = wt;
? AddLiveNode(Q,wt,i,n,bestw,E,
bestE,bestx,true);}
算法设计与分析 340
? // 检查右孩子
? if (Ew + r > bestw) AddLiveNode(Q,Ew,i,n,
bestw,E,bestE,bestx,false);
? Q, D e l e t e ( E ) ; // 下一个 E-节点
? if (!E) { // 层的尾部
? if (Q.IsEmpty()) break;
? Q, A d d ( 0 ) ; // 层尾指针
? Q, D e l e t e ( E ) ; // 下一个 E-节点
? i + + ; // E-节点的层次
? r -= w[i];} // E-节点中余下的重量
? Ew = E-> w e i g h t ; // 新的 E-节点的重量
? }
算法设计与分析 341
? // 沿着从 b e s t E到根的路径构造 x[ ],
x [ n ]由 A d d L i v e N o d e来设臵
? for (j = n - 1; j > 0; j--) {
? bestx[j] = bestE->LChild; // 从 b o o l转
换为 i n t
? bestE = bestE-> p a r e n t ;
? }
? return bestw;
? }
算法设计与分析 342
最大收益分枝定界
? bbnode 类
? class bbnode {
? p r i v a t e,
? bbnode *parent; // 父节点指针
? bool LChild; // 当且仅当是父节点的左孩
子时，取值为 t r u e
? } ;
算法设计与分析 343
最大收益分枝定界
? HeapNode 类
? template<class T>
? class HeapNode {
? p u b l i c,
? operator T () const {return uweight;}
? p r i v a t e,
? bbnode *ptr; // 活节点指针
? T uweight; // 活节点的重量上限
? int level; // 活节点所在层
? } ;
算法设计与分析 344
? template<class T>
? void AddLiveNode(MaxHeap<HeapNode<T>
> &H,bbnode *E,T wt,bool ch,int lev)
? {// 向最大堆 H中增添一个层为 l e v上限重量为
w t的活节点
? // 新节点是 E的一个孩子
? // 当且仅当新节点是左孩子 ch 为 t r u e
? bbnode *b = new bbnode;
? b->parent = E;
? b->LChild = ch;
? HeapNode<T> N;
? N.uweight = wt;
? N.level = lev;
算法设计与分析 345
? N.ptr = b;
? H, I n s e r t ( N ) ;
? }
? template<class T>
? T MaxLoading(T w[],T c,int n,int bestx[])
? {// 返回最优装载值，最优装载方案保存于 b e
s t x
? // 使用最大收益分枝定界算法
? // 定义一个最多有 1 0 0 0个活节点的最大堆
? MaxHeap<HeapNode<T> > H(1000);
? // 第一剩余重量的数组
? // r[j] 为 w [ j + 1, n ]的重量之和
? T *r = new T [n+1];
算法设计与分析 346
? r[n] = 0;
? for (int j = n-1; j > 0; j--)
? r[j] = r[j+1] + w[j+1];
? // 初始化层 1
? int i = 1; // E-节点的层
? bbnode *E = 0; // 当前 E-节点
? T Ew = 0; // E-节点的重量
? // 搜索子集空间树
? while (i != n+1) {// 不在叶子上
? // 检查 E-节点的孩子
? if (Ew + w[i] <= c) {// 可行的左孩子
? AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}
? // 右孩子
算法设计与分析 347
? AddLiveNode(H,E,Ew+r[i],false,i+1);
? // 取下一个 E-节点
? HeapNode<T> N;
? H.DeleteMax(N); // 不能为空
? i = N.level;
? E = N.ptr;
? Ew = N.uweight - r[i-1];
? }// 沿着从 E-节点 E到根的路径构造 b e s t x [ ]
? for (int j = n; j > 0; j--) {
? bestx[j] = E->LChild; // 从 b o o l转换为 i n t
? E = E-> p a r e n t ;
? }return Ew;
? }
算法设计与分析 348
说明
? 1) 使用最大堆来表示活节点的最大优先队列
时，需要预测这个队列的最大长度（程序 8 - 6
中是 1 0 0 0）。为了避免这种预测，可以使用
一个基于指针的最大优先队列来取代基于数
组的队列。
? 2) bestw表示当前所有可行节点的重量的最大
值，而优先队列中可能有许多其 uweight不超
过 bestw的活节点，因此这些节点不可能帮助
我们找到最优的叶节点，这些节点浪费了珍
贵的队列空间，并且它们的插入 /删除动作也
浪费了时间，所以可以将这些节点删除。
算法设计与分析 349
?有一种策略可以减少这种浪费，即在插
入某个节点之前检查是否有
uweight<bestw。然而，由于 bestw在算
法执行过程中是不断增大的，所以目前
插入的节点在以后并不能保证
uweight<bestw。另一种更好的方法是在
每次 bestw增大时，删除队列中所有
uweight<besew的节点。这种策略要求删
除具有最小 uweight的节点。因此，队列
必须支持如下的操作：插入、删除最大
节点、删除最小节点。这种优先队列也
被称作双端优先队列
（ double-ended priority queue）。
算法设计与分析 350
0/1背包问题
? 0 / 1背包问题的最大收益分枝定界算法
可以由 程序 4 - 6发展而来。可以使用程
序 4- 6的 B o u n d函数来计算活节点 N的
收益上限 u p,使得以 N为根的子树中的
任一节点的收益值都不可能超过 uprofit。
?使用了类 Knap,
?它类似于回溯法中的类 K n a p
?（ 见程序 4 - 5）。
算法设计与分析 351
0/1背包问题的最大收益分枝
定界算法
? template<class Tw,class Tp>
? Tp Knap<Tw,Tp>::MaxProfitKnapsack()
? {// 返回背包最优装载的收益
? // bestx[i] = 1 当且仅当物品 i 属于最优装载
? // 使用最大收益分枝定界算法
? // 定义一个最多可容纳 1 0 0 0个活节点的最大
堆
? H = new MaxHeap<HeapNode<Tp,Tw> >
(1000);
算法设计与分析 352
? // 为 b e s t x分配空间
? bestx = new int [n+1];
? // 初始化层 1
? int i = 1;
? E = 0;
? cw = cp = 0;
? Tp bestp = 0; // 目前的最优收益
? Tp up = Bound(1); // 在根为 E的子树中最大可
能的收益
? // 搜索子集空间树
? while (i != n+1) { // 不是叶子
算法设计与分析 353
? // 检查左孩子
? Tw wt = cw + w[i];
? if (wt <= c) {// 可行的左孩子
? if (cp+p[i] > bestp) bestp = cp+p[i];
? AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}
? up = Bound(i+1);
? // 检查右孩子
? if (up >= bestp) // 右孩子有希望
? AddLiveNode(up,cp,cw,false,i+1);
? // 取下一个 E-节点
? HeapNode<Tp,Tw> N;
? H->DeleteMax(N); // 不能为空
算法设计与分析 354
? E = N.ptr;
? cw = N.weight;
? cp = N.profit;
? up = N.uprofit;
? i = N.level;
? }
? // 沿着从 E-节点 E到根的路径构造 bestx[]
? for (int j = n; j > 0; j--) {
? bestx[j] = E-> L C h i l d ;
? E = E-> p a r e n t ;
? }
? return cp;
? }
算法设计与分析 355
? 函数 MaxProfitKnapsack在子集树中执行最大
收益分枝定界搜索。函数假定所有的物品都
是按收益密度值的顺序排列，可以使用类似
于程序 4 - 9中回溯算法所使用的预处理代码来
完成这种排序。函数 MaxProfitKnapsack首先
初始化活节点的最大堆，并使用一个数组
bestx来记录最优解。由于需要不断地利用收
益密度来排序，物品的索引值会随之变化，
因此必须将 MaxProfitKnapsack所生成的结果
映射回初始时的物品索引。可以用 Q的 I D域
来实现上述映射 （见程序 4 - 9） 。
算法设计与分析 356
最大完备子图 分枝定界算法
? int AdjacencyGraph::BBMaxClique(int
bestx[])
? {// 寻找一个最大完备子图的最大收益分枝定
界程序
? // 定义一个最多可容纳 1 0 0 0个活节点的最大
堆
? MaxHeap<CliqueNode> H(1000);
? // 初始化层 1
? bbnode *E = 0; // 当前的 E-节点为根
? int i = 1,// E-节点的层
? cn = 0,// 完备子图的大小
算法设计与分析 357
? bestn = 0; // 目前最大完备子图的大小
? // 搜索子集空间树
? while (i != n+1) {// 不是叶子
? // 在当前完备子图中检查顶点 i 是否与其它顶
点相连
? bool OK = true;
? bbnode *B = E;
? for (int j = i - 1; j > 0; B = B->parent,j--)
? if (B->LChild && a[i][j] == NoEdge) {
? OK = false;
? b r e a k ; }
? if (OK) {// 左孩子可行
算法设计与分析 358
? if (cn + 1 > bestn) bestn = cn + 1;
? AddCliqueNode(H,cn+1,cn+n-i+1,i+1,E,
true);}
? if (cn + n - i >= bestn)
? // 右孩子有希望
? AddCliqueNode(H,cn,cn+n-i,i+1,E,false);
? // 取下一个 E-节点
? CliqueNode N;
? H.DeleteMax(N); // 不能为空
? E = N.ptr;
? cn = N.cn;
? i = N.level;
? }
算法设计与分析 359
? // 沿着从 E到根的路径构造 bestx[]
? for (int j = n; j > 0; j--) {
? bestx[j] = E-> L C h i l d ;
? E = E-> p a r e n t ;
? }
? return bestn;
? }
算法设计与分析 360
旅行商问题的最小耗费分枝
定界算法
? template<class T>
? T AdjacencyWDigraph<T>::BBTSP(int v[])
? {// 旅行商问题的最小耗费分枝定界算法
? // 定义一个最多可容纳 1000个活节点的最小
堆
? MinHeap<MinHeapNode<T> > H(1000);
? T *MinOut = new T [n+1];
? // 计算 MinOut[i] = 离开顶点 i的最小耗费边的
耗费
? T MinSum = 0; // 离开顶点 i的最小耗费边的数
目
算法设计与分析 361
? for (int i = 1; i <= n; i++) {
? T Min = NoEdge;
? for (int j = 1; j <= n; j++)
? if (a[i][j] != NoEdge &&(a[i][j] < Min || Min ==
NoEdge))
? Min = a[i][j];
? if (Min == NoEdge) return NoEdge; //此路不
通
? MinOut[i] = Min;
? MinSum += Min;
? }
? // 把 E-节点初始化为树根
算法设计与分析 362
? MinHeapNode<T> E;
? E.x = new int [n];
? for (i = 0; i < n; i++)
? E.x[i] = i + 1;
? E.s = 0; // 局部旅行路径为 x [ 1, 0 ]
? E.cc = 0; // 其耗费为 0
? E.rcost = MinSum;
? T bestc = NoEdge; // 目前没有找到旅行路径
? // 搜索排列树
? while (E.s < n - 1) {// 不是叶子
? if (E.s == n - 2) {// 叶子的父节点
? // 通过添加两条边来完成旅行
算法设计与分析 363
? // 检查新的旅行路径是不是更好
? if (a[E.x[n-2]][E.x[n-1]] != NoEdge &&
a[E.x[n-1]][1] != NoEdge && (E.cc +a[E.x[n-
2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc
== NoEdge)) {
? // 找到更优的旅行路径
? bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-
1]][1];
? E.cc = bestc;
? E.lcost = bestc;
? E, s + + ;
? H, I n s e r t ( E ) ; }
? else delete [] E.x;}
算法设计与分析 364
? else {// 产生孩子
? for (int i = E.s + 1; i < n; i++)
? if (a[E.x[E.s]][E.x[i]] != NoEdge) {
? // 可行的孩子,限定了路径的耗费
? T cc = E.cc + a[E.x[E.s]][E.x[i]];
? T rcost = E.rcost - MinOut[E.x[E.s]];
? T b = cc + rcost; //下限
? if (b < bestc || bestc == NoEdge) {
? // 子树可能有更好的叶子
? // 把根保存到最大堆中
? MinHeapNode<T> N;
? N.x = new int [n];
算法设计与分析 365
? for (int j = 0; j < n; j++)
? N.x[j] = E.x[j];
? N.x[E.s+1] = E.x[i];
? N.x[i] = E.x[E.s+1];
? N.cc = cc;
? N.s = E.s + 1;
? N.lcost = b;
? N.rcost = rcost;
? H, I n s e r t ( N ) ; }
? } // 结束可行的孩子
? delete [] E.x;} // 对本节点的处理结束
? try {H.DeleteMin(E);} // 取下一个 E-节点
算法设计与分析 366
? catch (OutOfBounds) {break;} // 没有未处理
的节点
? }
? if (bestc == NoEdge) return NoEdge; // 没有
旅行路径
? // 将最优路径复制到 v[1:n] 中
? for (i = 0; i < n; i++)
? v[i+1] = E.x[i];
? while (true) {// 释放最小堆中的所有节点
? delete [] E.x;
? try {H.DeleteMin(E);}
? catch (OutOfBounds) {break;}
? }return bestc;}
算法设计与分析 367
电路板排列问题的最小耗费
分枝定界算法
? int BBArrangeBoards(int **B,int n,int m,int*
&bestx)
? {// 最小耗费分枝定界算法,m个插槽,n块板
? MinHeap<BoardNode> H(1000); // 容纳活节
点
? // 初始化第一个 E节点,t o t a l和 b e s t d
? BoardNode E;
? E.x = new int [n+1];
? E.s = 0; // 局部排列为 E, x [ 1, s ]
? E.cd = 0; // E.x[1:s]的密度
算法设计与分析 368
? E.now = new int [m+1];
? int *total = new int [m+1];
? // now[i] = x[1:s]中含插槽 i的板的数目
? // total[i] = 含插槽 i的板的总数目
? for (int i = 1; i <= m; i++) {
? total[i] = 0;
? E.now[i] = 0;
? }
? for (i = 1; i <= n; i++) {
? E.x[i] = i; // 排列为 1 2 3 4 5,,, n
? for (int j = 1; j <= m; j++)
? total[j] += B[i][j]; // 含插槽 j的板
? }
算法设计与分析 369
? int bestd = m + 1; / /目前的最优密度
? bestx = 0; // 空指针
? do {// 扩展 E节点
? if (E.s == n - 1) {// 仅有一个孩子
? int ld = 0; // 最后一块板的局部密度
? for (int j = 1; j <= m; j++)
? ld += B[E.x[n]][j];
? if (ld < bestd) {// 更优的排列
? delete [] bestx;
? bestx = E.x;
? bestd = max(ld,E.cd);
? }
? else delete [] E.x;
算法设计与分析 370
? delete [] E.now;}
? else {// 生成 E-节点的孩子
? for (int i = E.s + 1; i <= n; i++) {
? BoardNode N;
? N.now = new int [m+1];
? for (int j = 1; j <= m; j++)
? // 在新板中对插槽计数
? N.now[j] = E.now[j] + B[E.x[i]][j];
? int ld = 0; // 新板的局部密度
? for (j = 1; j <= m; j++)
? if (N.now[j] > 0 && total[j] != N.now[j]) ld++;
? N.cd = max(ld,E.cd);
算法设计与分析 371
? if (N.cd < bestd) {// 可能会引向更好的叶子
? N.x = new int [n+1];
? N.s = E.s + 1;
? for (int j = 1; j <= n; j++)
? N.x[j] = E.x[j];
? N.x[N.s] = E.x[i];
? N.x[i] = E.x[N.s];
? H, I n s e r t ( N ) ; }
? else delete [] N.now;}
? delete [] E.x;} // 处理完当前 E-节点
? try {H.DeleteMin(E);} // 下一个 E-节点
? catch (OutOfBounds) {return bestd;} //没有 E-
节点
算法设计与分析 372
? } while (E.cd < bestd);
? // 释放最小堆中的所有节点
? do {delete [] E.x;
? delete [] E.now;
? try {H.DeleteMin(E);}
? catch (...) {break;}
? } while (true);
? return bestd;
? }
第九章 回溯
算法设计与分析 373
随机算法
?在接收输入的同时，还接收一串随机比
特流并且在运行过程中使用该比特流
? Las vegas
? Monte carlo
算法设计与分析 374
随机算法
?随机化快速排序
?随机化选择排序
?测试串的相等性
?模式匹配
?随机取样
?素数性测试
算法设计与分析 375
近似算法
? 算法 VCOVERAPPOX
? 输入：无向图 G＝（ V,E）
? 输出,G的一个顶点覆盖 C
? C← { }
? While E≠{ }
? 设 e＝（ u,v)为 E中的任意边
? C ←C ∪{u,v}
? 删除 e和 E中所有与 u和 v相关联的边
? End while
算法设计与分析 376
近似算法
? 重新编排项，使得 v1/s1≥v2/s2…≥vn/sn
? j ←0;k ←0;v ←0;z ←{}
? While j<n and k<c
? j ←j ＋ 1
? If sj≤c-k then
? Z ←Z ∪{uj}
? k ←k+sj
? v ←v+vj
? End if
? End while
? Let Z’={us},us为最大得项
? If v≥vs then return Z
? Eles return Z’
算法设计与分析 377
网络流
s
d b
a c
t
算法设计与分析 378
s
d b
a c
t
算法设计与分析 379
s
b
a
t
算法设计与分析 380
Ford-fulkerson
? 初始化剩余图，设 R＝ G
? For 边（ u,v） ∈ E
? f（ u,v） ← 0
? end for
? While在 R中有一条增广路径 p＝ s,…, t
? 设 △为 p的瓶颈容量
? for p中的每条边（ u,v）
? f（ u,v） ← f（ u,v）＋ △
? end for
? 更新剩余图
? end while
算法设计与分析 381
s
d b
a c
t
算法设计与分析 382
第一层
s
d b
a c
t
算法设计与分析 383
第二层
s
d b
a c
t
算法设计与分析 384
第三层
s
d b
a
算法设计与分析 385
最后流
s
d b
a c
t
算法设计与分析 386
s
d b
a c
t
算法设计与分析 387
s
d b
a c
t
算法设计与分析 388
s
d b
a c
t
算法设计与分析 389
s
d b
a c
t
算法设计与分析 390
s
d b
a c
t
算法设计与分析 391
匹配
a
e
i j k
f g
l
h
d c b
算法设计与分析 392
a
e
i j k
f g
l
h
d c b
算法设计与分析 393
a
e
i j k
f g
l
h
d c b
算法设计与分析 394
a
e
i j
f
g h
d c
b
算法设计与分析 395
a
e
j f g
d c
b
算法设计与分析 396
a
e
i j
f
g h
d c
b
算法设计与分析 397
a
e
i f
d
c
b
算法设计与分析 398
a
e i
f g h
d
c b
算法设计与分析 399
a
e i
f g h
d
c b
算法设计与分析 400
a
e i
f g h
d
c b
算法设计与分析 401
a
e i
f g h
d
c b