【转载】《算法设计与分析》课程笔记

这是笔者在朋友那里弄来的学习笔记,先转发在此以造福同学们。对于缺少的图片、出错的公式、有问题的排版,我有时间再解决

《算法设计与分析》课程笔记

Darius - 2020.8

[TOC]

算法引论

计算机问题求解的基本步骤:

graph LR
	1[具体问题] --问题分析与建模--> 2[数学模型] --算法设计与实现--> 3[算法与计算结果] --算法分析--> 4[性能分析]

算法的概念与性质

算法是在有限步骤内求解问题所使用的一组定义明确的规则(步骤)。广义上讲,算法是指解决问题的方法或过程;狭义上讲,算法是满足下述性质的指令序列。

  • 输入:有零个或多个外部量作为算法的输入。输出:算法产生至少一个量作为输出。
  • 确定性:组成算法的每条指令是清晰的、无歧义的。
  • 有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。
  • 可行性:算法中的操作都可以通过已实现的基本运算执行有限次来实现。

一个完整的算法应具备三个基本要素:基本运算和操作、控制结构和数据结构。

算法常用的表示方法:自然语言、流程图、伪代码、程序设计语言等。

抽象数据类型(ADT)

为了将顶层算法与底层算法隔开,对二者的接口进行抽象,让底层只通过接口为顶层服务,顶层只通过接口调用底层运算;这个接口就是抽象数据类型。ADT 的优点有:

  • 算法顶层设计与底层实现分离;算法设计与数据结构设计隔开;
  • 便于空间和时间耗费的折衷;描述的算法具有很好的可维护性;
  • 算法自然呈现模块化;为自顶向下逐步求精和模块化提供有效途径和工具;
  • 算法结构清晰,层次分明,便于正确性的证明和复杂度的分析。

算法的效率分析

算法的复杂度依赖于问题的输入实例和输入规模。我们一般只关注最坏情况下算法复杂度,这样算法复杂度既不依赖于机器也不依赖输入实例,只依赖于输入规模 n ,表示为 T(n) 。如何度量不同算法性能?运行时间——时间复杂度、存储空间——空间复杂度。用基本操作的执行次数来度量算法的时间效率,算法运行估算时间公式: T_n\approx c_{op}C(n) c_{op} 为算法在特定计算机上一个基本操作的执行时间,是个常量; C(n) 为该算法需执行的基本操作次数。算法的空间复杂度是对算法运行过程中占用存储空间大小的度量,是问题规模 n 的函数,记为: S(n)=O(f(n)) ,其中, n 是问题的规模输入量, f(n) 为语句关于 n 所占存储空间的函数。

分析度量算法效率时,使用渐近效率的概念。渐近效率更高的算法,对大规模输入是更好的。

为了阐释度量算法复杂度随问题规模增长而增长的速度,引入:渐进上界 O 、下界 \Omega 、确界 \Theta

渐进上界

对于函数 g(n) ,定义 O(g(n))=\{ f(n)|\exists \ c, n_0>0 ,\ \text{s.t. }\forall\ n\geq n_0,\ 0\leq f(n)\leq cg(n) \} O(g(n)) 表示一个函数集合, g(n) 是所有 f(n) 的一个上界。记作 f(n)=O(g(n)) ,渐进上界符号的运算性质:

  • O(f)+O(g)=O(f+g)=O(\max(f,g))
  • O(f)*O(g)=O(f*g)
  • g(n)=O(f(n))\Rightarrow O(f)+O(g)=O(f)
  • C>0,\ O(Cf(N))=O(f(N))\Rightarrow f=O(f)

渐进下界

对于函数 g(n) ,定义 \Omega(g(n))=\{ f(n)| \exists\ c,n_0>0,\ \text{s.t. }\forall\ n\geq n_0,\ 0\leq cg(n)\leq f(n)\} \Omega(g(n)) 表示一个函数集合, g(n) 是所有 f(n) 的一个下界。记作 f(n)=\Omega(g(n))

渐进确界

对于函数 g(n) ,定义 \Theta(g(n))=\{ f(n)| \exists\ c_1,c_2,n_0>0,\ \text{s.t. }\forall\ n\geq n_0,\ 0\leq c_1 g(n)\leq f(n)\leq c_2 g(n) \} \Theta(g(n)) 表示一个函数集合, g(n) 是所有 f(n) 的一个确界。记作 f(n)=\Theta(g(n)) 。运算性质有:

  • f(n)=\Theta(g(n))\Leftrightarrow f(n)=\Omega(g(n)),\ f(n)=O(g(n))
  • f_1(n)=\Theta(g_1(n)),f_2(n)=\Theta(g_2(n))\Leftrightarrow f_1(n)+f_2(n)= \Theta(\max\{g_1(n),g_2(n)\})

另外还有 o 符号,如果对于任意给定的 \varepsilon >0 ,都存在正整数 n_0 ,使得当 n\geq n_0 时有 f(n)/g(n)\leq \varepsilon ,则称函数 f(n) n 充分大时的阶比 g(n) 小,记为 f(n)=o(g(n))

复杂度的估算

  • 频度求合法:当算法中语句的执行次数和某变量直接相关,且变量的起止范围明确,可以使用求和公式求出最大语句频度 f(n) ,取其阶数即可。
  • 假设法:先假设循环执行 m 次,再根据循环终止条件求出语句频度 f(n)
  • 迭代分析法:适用于算法包含递归函数。迭代地展开递归方程的右端,化成非递归和式,最后再求和即可。

第一章作业题

习题 1-4 函数的渐近表达式

求下列函数的渐进表达式。

  1. 3n^2+10n\color{gray}{\ =O(n^2)}
  2. n^2/10+2^n\color{gray}{=O(2^n)}
  3. 21+1/n\color{gray}{\ =O(1)}
  4. \log n^3\color{gray}{=3\log n=O(\log n)}
  5. 10\log 3^n\color{gray}{=(10\log 3)n}=O(n)

习题 1-6 按渐近阶排列表达式

按照渐近阶从低到高的顺序排列以下表达式: 4n^2,\ \log n,\ 3^n,\ 20n,\ 2,\ n^{2/3},\ n!

**解:**按渐近阶从低到高,方法排列顺序为: 2,\ \log n,\ n^{2/3},\ 20n,\ 4n^2,\ 3^n,\ n!

习题 1-7 算法效率

  1. 假设某算法在输入规模为 n 时的计算时间为 T(n)=3\times 2^n 。在某台计算机上实现并完成该算法的时间为 t 秒。现有另一台计算机,其运行速度为第一台计算机的 64 倍,那么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题?
  2. 若上述算法的计算时间改进为 T(n)=n^2 ,其余条件不变,则在新机器上用 t 秒时间能解输入规模为多大的问题?
  3. 若上述算法的计算时间进一步改进为 T(n)=8 ,其余条件不变,那么在新机器上用 t 秒时间能解输入规模为多大的问题?

解: 1. 设新机器用同一算法在 t 秒内能解输入规模为 n_1 的问题。因此有 t=3\times 2^n=3\times 2^{n_1}/64 ,解得 n_1=n+6 2. n_1^2=64n^2\Rightarrow n_1=8n 3. 由于 T(n) 是常数,因此算法可解任意规模问题。

习题 1-8 硬件效率

硬件厂商 XYZ 公司宣称最新研制的微处理器运行速度为其竞争对手 ABC 公司同类产品的 100 倍。对于计算复杂性分别为 n,\ n^2,\ n^3 n! 的各算法,若用 ABC 公司的计算机在 1 小时内能解输入规模为 n 的问题,那么用 XYZ 公司的计算机在 1 小时内分别能解输入规模为多大的问题?

解: n^{\prime}=100n,\ n^{\prime 2}=100n^2\Rightarrow n^{\prime}=10n,\ n^{\prime 3}=100n^3\Rightarrow n^{\prime}=\sqrt[3]{100}n=4.64n,

n^{\prime}!=100n!\Rightarrow n^{\prime}<n+\log 100=n+6.64

递归与分治

基本思想

递归的概念与思想

直接或间接调用自身的算法称为递归算法,用函数自身给出定义的函数称为递归函数。递归包括“递推”和“回归”两部分,

  • 递推:为了得到问题的解,将原问题推到比它简单的问题求解。递推应该有终止条件,简单问题表示离递推终止条件更接近的问题。
  • 回归:指将简单问题的解,回归到原问题的解上来。

换句话说,递归就是把一个问题划分成一个或多个规模更小的子问题,用同样的方法求解子问题。

例 2.3 Ackerman 函数

当一个函数及它的一个变量是由函数自身定义时,称函数为双递归函数

Ackerman 函数 A(n,m) 有两个独立的整数变量 n\geq 0,\ m\geq 0 ,其定义为:

\left\{\begin{array}{cl} A(1,0)=2\\ A(0,m)=1 & m\geq 0\\ A(n,0)=n+2 & n\geq 2\\ A(n,m)=A\left(A(n-1,m),m-1\right) & n,m\geq 1 \end{array}\right.
  • m=1 时, A(1,1)=A(A(0,1),1)=A(1,0)=2
A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2=A(n-2,1)+2+2=A(1,1)+2(n-1)=2n\ (n\geq1)
  • m=2 时, A(1,2)=A(A(0,2),1)=A(1,1)=2
A(n,2)=A(A(n-1,2),1)=2A(n-1,2)=2^2A(n-2,2)=2^{n-1}A(1,2)=2^n
  • m=3 时, A(1,3)=A(A(0,3),2)=A(1,2)=2
A(n,3)=A(A(n-1,3),2)=2^{A(n-1,2)}=2^{\displaystyle 2^{A(n-2,3)}}=\underbrace{2^{2^{\displaystyle\cdot^{\displaystyle\cdot^{\displaystyle\cdot^{2^{A(1,3)}}}}}}}_{n-1 {\Large{\text{个}}}2}=\underbrace{2^{2^{\displaystyle\cdot^{\displaystyle\cdot^{\displaystyle\cdot^{2}}}}}}_{n{\Large{\text{个}}}2}\quad.

分治算法总体思想

  • 将要求解的较大规模的问题分割成 k 个小规模的子问题,对这 k 个子问题分别求解。
  • 若子问题规模仍不够小,则再划分为 k 个子问题,如此递归下去。
  • 直到问题规模足够小,容易求解为止。再将求出的小规模的问题的解合并为一个更大规模问题的解,自底向上逐步求出原问题的解。一般模式为:

在使用分治法时,最好使子问题规模大致相等,即把原问题分成大小相等的 k 个子问题,这是一种平衡子问题的思想,通常总是比子问题规模不等的做法要更优。

分治法的复杂性分析

一个分治法将规模为 n 的问题分成 k 个规模为 n/m 的子问题求解。假设阀值 n_0=1 adhoc 解规模为 1 的问题耗费 1 个单位时间,将原问题分解为 k 个子问题以及用 merge k 个子问题解合并为原问题解需要 f(n) 个单位时间。 T(n) 表示该分治法解规模 |P|=n 的问题所需的计算时间,

T(n)=\left\{ \begin{array}{cl} O(1) & n=1\\ kT(n/m)+f(n) & n>1 \end{array} \right. \\ \begin{aligned} T(n)&=kT(n/m)+f(n)\\ &=k\left[kT(n/m^2)+f(n/m\right]+f(n)\\ &=k^2T(n/m^2)+kf(n/m)+f(n)\\ &=\cdots\\ &=k^{i}T(n/m^i)+k^{i-1}f(n/m^{i-1})+\cdots+kf(n/m)+f(n)\\ &\xlongequal{n=m^i}k^iT(1)+k^{i-1}f(n/m^{i-1})+\cdots+kf(n/m)+f(n)\\ &=n^{\log_m k}+\sum_{j=0}^{\log_m{n-1}}k^j f(n/m^j) \end{aligned}

递归方程及其解只给出 n m 的幂时 T(n) 的值,如果认为 T(n) 足够平滑,则由 n m 的幂的值可以估计 T(n) 的增长速度。假设 T(n) 单调上升,则 \forall\ m^i\leq n<m^{i+1},\ T(m^i)\leq T(n)<T(m^{i+1})

分治策略的使用条件

  • 该问题具有最优子结构性质
  • 该问题分解出的子问题的解可以合并为该问题的解;
  • 该问题分解出的各个子问题是相互独立的
  • 子问题与原问题类型一致而其规模却不断缩小,且缩小到一定规模容易解决;

递归算法应用

例 2.4 排列问题

R=\{r_1, r_2, \ldots,r_n\} 是要进行排列的 n 个元素, R_i=R-\{r_i\} 。集合 X 中元素的全排列记为 \text{perm}(X) (r_i)\text{perm}(X) 表示在全排列 \text{perm}(X) 的每一个排列前加上前缀 r_i 得到的排列,则有:

\text{perm}(R)=\left\{ \begin{array}{cl} \left\{ r_1\right\} & n=1\\ (r_1)\text{perm}(R_1),(r_2)\text{perm}(R_2),\ldots,(r_n)\text{perm}(R_n) & n>1 \end{array} \right.

总体思想是,将整组数中的所有的数分别与第一个数交换,这样总是在处理后面的数的全排列。

例如,当 n=3 ,并且 E=\{a,b,c\} ,则:

\text{perm}(E)=a.\text{perm}(\{b,c\})+b.\text{perm}(\{a,c\})+c.\text{perm}(\{a,b\})\\ a.\text{perm}(\{b,c\})=ab.\text{perm}(c)+ac.\text{perm}(b)=ab.c+ac.b=\{abc,acb\}\\ b.\text{perm}(\{a,c\})=ba.\text{perm}(c)+bc.\text{perm}(a)=ba.c+bc.a=\{bac,bca\}\\ c.\text{perm}(\{a,b\})=ca.\text{perm}(b)+cb.\text{perm}(a)=ca.b+cb.a=\{cab,cba\}\\ \text{perm}(E)=\{abc,acb,bac,bca,cab,cba\}

按照定义,递归产生全排列的算法如下:

public static void perm(Object[] list, int k, int m) {
    if(k == m) {	// 只剩一个元素
        for(int i = 0; i <= m; i ++) {
            System.out.print(list[i]);
        }
        System.out.println();
    } else {		// 还有多个元素,递归产生排列
        for(int i = k; i <= m; i ++) {
            swap(list, k, i);
            perm(list, k + 1, m);
            swap(list, k, i);
        }	// 与后面的元素交换
    }
}
// 数组元素按下标交换的函数
public static void swap(Object[] list, int i, int j) {
    Object temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

算法 \text{perm}(\text{list},k,m) 递归地产生所有前缀是 \text{list}[0:k-1] ,后缀是 \text{list}[k:m] 的全排列的所有排列。调用算法 \text{perm}(\text{list},0,n-1) 即可产生 \text{list}[0:n-1] 的全排列。在一般情况下, k<m ,算法将 \text{list}[k:m] 中每一个元素分别与 \text{list}[k] 交换,然后递归计算 \text{list}[k+1:m] 的全排列,并且结果作为 \text{list}[0:k] 的后缀。

例 2.5 整数划分问题

将正整数 n 表示为一系列正整数之和,

n=n_1+n_2+\cdots+n_k,\ n_1\geqslant n_2\geqslant \cdots \geqslant n_k\geqslant 1,\ k\geq 1\

正整数 n 的这种表示称为 n 的划分, n 的不同的划分个数称为 n 的划分数,记作 p(n)

n 的所有不同划分中,最大加数不大于 m 的划分个数为 q(n,m) ,显然 p(n)=q(n,n)

  • m=1 时,显然此时只有一种划分方式: n=\overbrace{1+1+\cdots +1}^{n\Large\text{ 个}} ,即 q(n,1)=1,\ n\geq 1
  • m>n 时,实际上最大加数不应该大于 n ,所以 q(n,m)=q(n,n),\ m>n
  • m=n 时, n 的划分可以由最大加数为 n 的划分和最大加数不大于 n-1 的划分组成,即:
q(n,n)=1+q(n,n-1),\ \quad n=m
  • 1<m<n 时, n 的划分由最大加数不大于于 m-1 的划分和等于 m 的划分组成,即:
q(n,m)=q(n,m-1)+q(n-m,m),\ \quad n>m>1

其中,最大加数等于 m 的划分相当于固定首个加数为 m ,后面是最大加数不大于 m ,对 n-m 的划分,另外,对于 n\leq 0 m\leq 0 的情况是非法的,即 q(n,m)=0\ 。递归算法如下:

public static int q(int n, int m) {
    if(n < 1 || m < 1) return 0;
    if(n == 1 || m == 1) return 1;
    if(n < m) return q(n, n);
    if(n == m) return q(n, m - 1) + 1;
    return q(n, m - 1) + q(n - m, m);
}

例 2.6 Hanoi 塔问题

a,b,c 3 个塔座。开始时,在塔座 a 上有一叠共 n 个圆盘,这些圆盘自下而上,由大到小地叠在一起,各圆盘从小到大编号为 1,2,\ldots,n ,要求将 a 上的这一叠圆盘移到 b 上,并且扔按相同顺序叠置。在移动圆盘时应该遵循以下规则:

  1. 每次只能移动 1 个圆盘;
  2. 较大的圆盘永远在较小的圆盘下面;
  3. 在满足规则 1. 和规则 2. 的前提下,可将圆盘移至 a,b,c 中任一塔座上。

问题是将 n 个圆盘通过 c a 移动到 b ,显然可以转化为先将 n-1 个圆盘通过 b a 移动到 c ,再将第 n 个圆盘从 a 移动到 b ,然后将那 n-1 个圆盘通过 a c 移动到 b\ 。递归算法如下:

public static void hanoi(int n, int a, int b, int c) {
    if(n > 0) {
        hanoi(n-1, a, c, b);
        move(a, b);
        hanoi(n-1, c, b, a);
    }
}

\text{hanoi}(n,a,b,c) 表示将 a 上的 n 个圆盘按规则利用 c 移到 b \text{move}(a,b) 表示将 a 上的圆盘移到 b\

递归算法小结

  • 优点:结构清晰,可读性强,容易用数学归纳法证明算法正确性,设计算法方便。
  • 缺点:运行效率较低,耗费的计算时间和占用的存储空间比非递归算法要多。
    • 解决方法:消除递归算法中的递归调用,转化为非递归。
      • 采用用户定义的栈模拟系统的递归调用工作栈。该方法通用性强,本质还是递归,但优化效果不明显。
      • 用递推来实现递归函数。
      • 通过 Cooper 变换、反演变换能将一些递归转化成尾递归,迭代出结果。后两种方法在时空复杂度上有较大改善,但适用范围有限。

分治法的应用

二分搜索

给定已按升序排好的 n 个元素 a[0:n-1] ,在这 n 个元素中找一特定元素 x 。二分搜索采用分治策略,最坏情况下用 O(\log n) 时间完成搜索任务。二分搜索的基本思想是将 n 个元素分成个数大致相同的两半,取中间数与 x 进行比较:如果找到,则终止,

  • 如果 x 大于中间数,由于数组是升序的,则只需在右半部分继续搜索;
  • 同理,如果 x 小于中间数,在左半部分搜索。

重复操作,直到找到 x 或无法继续搜索为止。算法实现如下:

public static int binarySearch(int[] a, int x, int n) {
    // 在 a[0]<=a[1]<=...<=a[n-1] 中搜索 x, 
    // 找到 x 时返回其在数组中的位置,否则返回 -1
    int left = 0, right = n - 1;
    while(left <= right) {
        int middle = (left + right) / 2;
        if(x == a[middle]) return middle;
        if(x > a[middle]) left = middle + 1;
        else right = middle - 1;
    }
    return -1;  // 未找到 x
}

显然,每执行一次 while 循环,问题的规模就减小一半,所以最坏情况下 while 执行了 O(\log n) 次,每一次循环需要 O(1) 时间,所以最坏情况下时间复杂度 O(\log n)

大整数乘法

X Y 都是 n 位的二进制整数,要计算他们的乘积 XY 。将 n 位二进制整数 X Y 先都分为两段,每段长为 n/2 ,这里假设 n 2 的幂,

X=\overbrace{\boxed{\quad\ A\quad\ {\color{white}{|}}}}^{n/2\Large\text{ 位}}\overbrace{\boxed{{\color{white}{|}}\quad \ B\quad \ }}^{n/2\Large\text{ 位}}\quad\quad\quad\quad Y=\overbrace{\boxed{\quad\ C\quad\ {\color{white}{|}}}}^{n/2\Large\text{ 位}}\overbrace{\boxed{{\color{white}{|}}\quad \ D\quad \ }}^{n/2\Large\text{ 位}}\\ X=A2^{n/2}+B,\ Y=C2^{n/2}+D,\ XY=(A2^{n/2}+B)(C2^{n/2}+D)=AC2^n+(AD+BC)2^{n/2}+BD

如果按照上式计算,则需要进行 4 n/2 位整数乘法;另外还有 3 次不超过 2n 位的整数加法和两次移位,这些操作总体是 O(n) 次的,设 T(n) 是两个 n 位整数相乘的运算次数,

T(n)=\left\{ \begin{array}{cl} O(1) & n=1\\ 4T(n/2)+O(n) & n>1 \end{array}\right.

显然 T(n)=O(n^{\log 4})=O(n^2) ,要改进复杂度,需减少乘法次数,把 XY 写成另一种形式,

XY=AC2^n+((A-B)(D-C)+AC+BD)2^{n/2}+BD

此时就只需做 3 n/2 位整数乘法, 6 次加减法和两次移位, T(n)=\left\{ \begin{array}{cl} O(1) & n=1\\ 3T(n/2)+O(n) & n>1 \end{array}\right.

T(n)=O(n^{\log 3})\approx O(n^{1.59}) ,值得注意的是,

(A-B)(D-C)+AC+BD=(A+B)(D+C)-AC-BD

虽然后者的复杂度也是 O(n^{1.59}) ,但考虑到 A+B,\ C+D 可能会得到 n+1 位,增大问题规模,故一般不选择后者。如果将大整数分成更多段,用更复杂的方法进行组合,得到的算法是否会更优?这个思想最终导致了**快速傅利叶变换(Fast Fourier Transform)**的产生,它可以在 O(n\log n) 时间内解决大整数乘法。

Strassen 矩阵乘法

A B 是两个 n\times n 矩阵,他们的乘积 C=AB 也是一个 n\times n 矩阵,定义为,

C[i][j]=\sum_{k=1}^n A[i][k]\cdot B[k][j]

显然计算 C 的一个元素需要 O(n) 的时间,因此,按定义计算矩阵 C 的时间复杂度为 O(n^3) 。采用类似大整数乘法的分治策略,将矩阵 A,B,C 都分块成 4 个大小相等的子矩阵,即,

\left[\begin{array}{cc} C_{11} & C_{12}\\ C_{21} & C_{22} \end{array}\right] =\left[\begin{array}{cc} A_{11} & A_{12}\\ A_{21} & A_{22} \end{array}\right] \left[\begin{array}{cc} B_{11} & B_{12}\\ B_{21} & B_{22} \end{array}\right]\\ \left[\begin{array}{cc} C_{11} & C_{12}\\ C_{21} & C_{22} \end{array}\right]=\left[\begin{array}{cc} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22}\\ A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22} \end{array}\right]

利用上式计算,要做 8 n/2 阶方阵的乘法和 4 n/2 方阵的加法,方阵的加法显然需要 O(n^2) 的时间,因此,分治法的计算时间 T(n)=\left\{ \begin{array}{cl} O(1) & n=2\\ 8T(n/2)+O(n^2) & n>2 \end{array}\right. ,解是 T(n)=O(n^{\log 8})=O(n^3) ,并没有得到改进,仍需要减少矩阵乘法的次数,

\begin{aligned} & M_1=A_{11}(B_{12}-B_{22})\\ & M_2=(A_{11}+A_{12})B_{22}\\ & M_3=(A_{21}+A_{22})B_{11}\\ & M_4=A_{22}(B_{21}-B_{11})\\ & M_5=(A_{11}+A_{22})(B_{11}+B_{22})\\ & M_6=(A_{12}-A_{22})(B_{21}+B_{22})\\ & M_7=(A_{11}-A_{21})(B_{11}+B_{12}) \end{aligned}

做了这 7 次矩阵乘法后,再做若干次加减法就可以得到矩阵 C

\left[\begin{array}{cc} C_{11} & C_{12}\\ C_{21} & C_{22} \end{array}\right]= \left[\begin{array}{cc} M_5+M_4-M_2+M_6 & M_1+M_2\\ M_3+M_4 & M_5+M_1-M_3-M_7 \end{array}\right]

Strassen 矩阵乘法中,做了 7 n/2 阶矩阵乘法和 18 n/2 阶矩阵的加减法,则,

T(n)=\left\{ \begin{array}{cl} O(1) & n=2\\ 7T(n/2)+O(n^2) & n>2 \end{array}\right.\ \Rightarrow\ T(n)=O(n^{\log 7})\approx O(n^{2.81})

目前矩阵乘法最好的时间上界是 O(n^{2.376})

棋盘覆盖

在一个 2^k\times 2^k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格,且称该棋盘为特殊棋盘。

在棋盘覆盖问题中,要用图示的 4 种不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何两个 L 型骨牌不得重叠覆盖。

显然,在任何一个 2^k\times 2^k 棋盘覆盖中,用的 L 型骨牌个数恰好为 (4^k-1)/3\

k>0 时,将 2^k\times 2^k 棋盘分割为 4 2^{k-1}\times 2^{k-1} 子棋盘,特殊方格必位于四个子棋盘之一,其余 3 子棋盘中无特殊方格,为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,可以用一个 L 型骨牌覆盖这 3 个子棋盘的会合处,这 3 个子棋盘上被 L 型骨牌覆盖的方格就成为该棋盘上的特殊棋盘,

从而将原问题转化为 4 个较小规模的棋盘覆盖问题,递归地使用这种分割,直到棋盘简化为 1\times 1 的棋盘。实现的 chessBoard 分治算法如下,

public static int tile = 1; // 骨牌号
public static int[][] board = new int[16][16]; // 棋盘
public static void chessBoard(int tr, int tc, int dr, int dc, int size) {
    if(size == 1) return;
    int t = tile++, // L 型骨牌号
        s = size/2; // 分割棋盘
    // 覆盖左上角子棋盘
    if(dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中
        chessBoard(tr, tc, dr, dc, s);
    else {  // 此棋盘无特殊方格
        // 用 t 号 L 型 骨牌覆盖右下角
        board[tr + s - 1][tc + s - 1] = t;
        // 覆盖其余方格
        chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    // 覆盖右上角子棋盘
    if(dr < tr + s && dc >= tc + s)
        chessBoard(tr, tc + s, dr, dc, s);
    else {  // 用 t 号 L 型 骨牌覆盖左下角
        board[tr + s - 1][tc + s] = t;
        chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    // 覆盖左下角子棋盘
    if(dr >= tr + s && dc < tc + s)
        chessBoard(tr + s, tc, dr, dc, s);
    else {  // 用 t 号 L 型 骨牌覆盖右上角
        board[tr + s][tc + s - 1] = t;
        chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 覆盖右下角子棋盘
    if(dr >= tr + s && dc >= tc + s)
        chessBoard(tr + s, tc + s, dr, dc, s);
    else {  // 用 t 号 L 型 骨牌覆盖左上角
        board[tr + s][tc + s] = t;
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

上述算法中, \text{board}[0][0] 是整个棋盘的左上角方格, \text{tr} 表示棋盘左上角方格的行号, \text{tc} 表示棋盘左上角方格的列号, \text{dr} 是特殊方格所在的行号, \text{dc} 是特殊方格所在的列号, \text{size}=2^k

T(k) 是算法 chessBoard 覆盖一个 2^k\times 2^k 棋盘所需的时间,则,

T(k)=\left\{ \begin{array}{cl} O(1) & k=0\\ 4T(k-1) + O(1) & k>0 \end{array} \right.\quad\Rightarrow\quad T(k)=O(4^k)

覆盖 2^k\times 2^k 棋盘所需的 L 型骨牌个数为 (4^k-1)/3 ,此算法在渐进意义下是最优的。

合并排序

合并排序是种稳定的排序,其思想为:将待排序元素分成大小大致相同的两个子集,对每个子集进行合并排序,再将排好序的子集合并为所要求的排好序的集合,例如对 [49,\ 38,\ 65,\ 97,\ 76,\ 13,\ 27] 排序,

\underbrace{\underbrace{\underbrace{[49]\quad\ [38]}_{\displaystyle[38\ \ \ 49]}\quad\ \underbrace{[65]\quad\ [97]}_{{\displaystyle[65\ \ \ 97]}}}_{\displaystyle[38\ \ \ 49\ \ \ 65\ \ \ 97]}\quad\ \underbrace{\underbrace{[76]\quad\ [13]}_{\displaystyle[13\ \ \ 76]}\quad\ \underbrace{[27]}_{{\displaystyle[27]}}}_{\displaystyle[13\ \ \ 27\ \ \ 76]}}_{\displaystyle[13\ \ \ 27\ \ \ 38\ \ \ 49\ \ \ 65\ \ \ 76\ \ \ 97]}

其递归算法如下:

public static void mergeSort(Comparable a[], int left, int right) {
    Comparable[] b = new Comparable[a.length];
    if(left < right) {              // 至少有 2 个元素
        int i = (left + right)/2;   // 取中点
        mergeSort(a, left, i);
        mergeSort(a, i + 1, right);
        merge(a, b, left, i, right);    // 合并到数组 b
        copy(a, b, left, right);        // 复制回数组 a
    }
}
public static void merge(Comparable[] c, Comparable[] d, int l, int m, int r) {
    // 合并 c[l:m] 和 c[m+1:r] 到 d[l:r]
    int i = l, j = m + 1, k = l;
    while(i <= m && j <= r)
        if(c[i].compareTo(c[j]) <= 0)
            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];
}
public static void copy(Comparable[] a, Comparable[] b, int left, int right) {
    for(int i = left; i <= right; i++)
        a[i] = b[i];
}

其中,算法 merge 合并两个排好序的数组段到新的数组 b 中,然后由算法 copy 将合并后的数组段复制回数组 a 中,显然 merge 和 copy 可以在 O(n) 时间内完成,用合并排序对 n 个元素进行排序,最坏情况下所需的计算时间 T(n) 满足, T(n)=\left\{ \begin{array}{cl} O(1) & n\leq 1\\ 2T(n/2)+O(n) & n>1 \end{array} \right.

\begin{aligned} T(n)&=2T(n/2)+cn=2(2T(n/4)+cn/2)+cn=4T(n/4)+2cn=\cdots\\ &=2^k T(n/2^k)+kcn\xlongequal{n=2^k,\ k=\log n}n+cn\log n=O(n\log n) \end{aligned}

由于排序问题的计算时间下界为 \Omega(n\log n) ,所以是渐近最优的。关于 mergeSort 的优化,可以从分治策略的机制入手,可以消除算法的递归。算法 mergeSort 的递归过程是将待排序集合一分为二,直至排序集合剩下 1 个元素为止,然后不断合并两个排好序的集合。

按此机制,可以先将数组 a 中相邻元素两两配对,用合并算法将他们有序,构成 n/2 组长度为 2 的排好序的子数组段,然后再将他们排序成长度为 4 的子数组段,直至整个数组有序。非递归算法如下,

public static void mergeSort(Comparable a[]) {
    Comparable[] b = new Comparable[a.length];
    int s = 1;
    while(s < a.length) {
        mergePass(a, b, s);     // 合并到数组 b
        s += s;
        mergePass(b, a, s);     // 合并到数组 a
        s += s;
    }
}
public static void mergePass(Comparable[] x, Comparable[] y, int s) {
    // 合并大小为 s 的相邻子数组
    int i = 0;
    while(i <= x.length - 2*s) {    // 合并大小为 s 的相邻 2 段子数组
        merge(x, y, i, i + s - 1, i + 2*s -1);
        i = i + 2*s;
    }
    if(i + s < x.length)	// 剩下的元素个数少于 2s
        merge(x, y, i, i + s - 1, x.length - 1);
    else    // 复制到 y
        for(int j = i; j < x.length; j++)
            y[j] = x[j];
}

自然合并排序的基本思想:给定的数组本身存在多个已经自然排序的子数组,对于这些子数组,不需要分解,用 1 次对原始数组的线性扫描就可以确定出所有已自然排序的子数组,然后将相邻的排好序的子数组两两合并,构成更大的排好序的子数组段,直到整个数组有序。

快速排序

快速排序是一种不稳定的排序,基本思想为:对要排序的数组 a[p:r] ,执行以下步骤:

  1. 分解(divide):以 a[p] 为基准将 a[p:r] 分为 3 a[p:q-1],\ a[q],\ a[q+1:r] ,使得,
    • a[p:q-1] 中任何元素小于等于 a[q]
    • a[q+1:r] 中任何元素大于等于 a[q]
  2. 递归求解(conquer):递归调用快速排序算法,对 a[p:q-1] a[q+1:r] 进行排序;
  3. 合并(merge):由于对 a[p:q-1] a[q+1:r] 的排序是通过数组中交换元素位置实现的,所以当两个子数组排序完成后,整个数组就已经有序,不需要显式的合并。

基于这个思想,快速排序算法如下,

public static void qSort(Comparable[] a, int p, int r) {
    if(p < r) {
        int q = partition(a, p, r);
        qSort(a, p, q - 1);     // 对左半端排序
        qSort(a, q + 1, r);     // 对右半段排序
    }
}

对含有 n 个元素的数组 a[0:n-1] 快速排序只需调用 \text{qSort}[a,0,n-1] 即可,上述算法中的 partition 函数,以确定的基准元素 a[p] 对数组 a[p:r] 进行划分;划分时,以元素 x=a[p] 为基准,分别从左、右两端开始,扩展两个区域 a[p:i] a[j:r] ,使得 a[p:i] 中元素小于或等于 x a[j:r] 中元素大于或等于 x ,初始时, i=p,\ j=r+1

在 while 循环中,下标 j 逐渐减小, i 逐渐增大,直到 a[i]\geq x\geq a[j] ,若此时 i<j ,就应该交换 a[i] a[j] 的位置,然后继续扩展左右两个区域,具体算法如下,

public static int partition(Comparable[] a, int p, int r) {
    int i = p, j = r + 1;
    Comparable x = a[p];
    // 将 <= x 的元素交换到左侧, >= x 的元素交换到右侧
    while(true) {
        while(a[++i].compareTo(x) < 0 && i < r);
        while(a[--j].compareTo(x) > 0);
        if(i >= j) break;
        swap(a, i, j);
    }
    swap(a, p, j);
    return j;
}

均衡划分:子问题的规模比不变;例如,设规模比 X:Y-X ,时间复杂度递归方程为,

T(n)=\left\{ \begin{array}{cl} O(1) & n\leq 1\\ T(Xn/Y)+T((Y-X)n/Y)+O(n) & n>1 \end{array} \right.

根据递归树可知,该问题时间复杂度为 T(n)=O(n\log n)

快速排序的时间复杂度与划分是否对称有关,最坏的情况是划分过程产生的两个区域分别有 n-1 1 个元素,算法 partition 的计算时间是 n-1 ,所以如果每一步 partition 都是这种最坏情况的划分,那么此时的时间复杂度 T(n) 为,

T(n)=\left\{ \begin{array}{cl} 0 & n\leq 1\\ T(n-1)+T(1)+n-1 & n>1 \end{array} \right. \quad \Rightarrow \ T(n)=\frac{n(n-1)}{2}=O(n^2)

在最好的情况下,每次划分都产生两个大小相同的区域,此时计算时间为,

T(n)=\left\{ \begin{array}{cl} 0 & n\leq 1\\ 2T(n/2)+n-1 & n>1 \end{array} \right. \quad \Rightarrow \ T(n)=O(n\log n)

由于首元素划分后在每个位置的概率都相等,快速排序的平均时间复杂度为,

T(n)=\left\{ \begin{array}{cl} 0& n\leq 1\\ \displaystyle\frac{1}{n}\sum_{k=1}^{n-1}(T(k)+T(n-k))+ n-1 & n>1 \end{array} \right.\\ \begin{aligned} T(n)&=\frac{1}{n}\sum_{k=1}^{n-1}(T(k)+T(n-k))+n-1\\ &=\frac{2}{n}\sum_{k=1}^{n-1}T(k)+n-1=\Theta(n\log n) \end{aligned}

通过修改 partition 算法,在快速排序算法的每一步中当数组还没有被划分时,在 a[p:r] 中随机选一个元素作为划分基准,从而可以期望划分是较对称的。

public static int randomizedPartition(Comparable[] a, int p, int r) {
    int i = (int)(Math.random()*(r - p + 1)) + p; // [p,r] 的随机数
    swap(a, i, p);
    return partition(a, p, r);
}

线性时间选择

给定线性序集中 n 个元素和一个整数 k,\ 1\leq k \leq n ,找出 n 个元素中第 k 小的元素, k=(n+1)/2 称为中位数。特殊情况下的线性时间算法:找最大最小元素,线性扫描显然是 O(n) 的;如果 k\leq n/\log n 或者是 k\leq n-n/\log n ,使用堆排序算法, O(n+k\log n)=O(n) 。对于一般情况下的选择问题,用快速排序的思想,对数组进行递归划分,不同的是只对划分出的子数组之一进行递归。算法 randomizedSelect 调用了随机快速排序中的 randomizedPartition,划分是随机产生的,要找到数组 a[0:n-1] 中第 k 小元素只要调用 randomizedSelect (a,0,n-1,k) 即可,具体算法如下,

public static Comparable randomizedSelect(Comparable[] a, int p, int r, int k) {
    if(p == r) return a[p];
    int i = randomizedPartition(a, p, r),
        j = i - p + 1;  // i 左边的元素个数
    if(k <= j) return randomizedSelect(a, p, i, k);
    else return randomizedSelect(a, i + 1, r, k - j);
}

在最坏情况下 randomizedSelect 算法需要 O(n^2) 的计算时间,但可以证明,算法 randomizedSelect 可以在 O(n) 的平均时间内找到 n 个元素的第 k 小元素。如果能在线性时间内找到一个划分基准,使得按这个基准所划分出的两个子数组的长度都至少为原数组长度的 \varepsilon (0<\varepsilon< 1) ,那么就可以在最坏情况下用 O(n) 时间完成任务, T(n)\leq T(\varepsilon n)+O(n)\Rightarrow T(n)=O(n)

按以下步骤可以找到满足要求的划分标准:

  1. n 个元素划分为 \lceil n/5\rceil 个组,每组 5 个元素,只可能有一个组不是 5 个元素,将每组元素排序,并取出每组的中位数,共 \lceil n/5\rceil 个。
  2. 递归调用 select 算法来找出这 \lceil n/5\rceil 个元素的中位数,如果 \lceil n/5\rceil 是偶数,就找他的中位数中较大的一个,以这个元素作为划分基准。

如下图所示, n 个元素用小圆点表示,空心小圆点为每组元素的中位数。中位数的中位数 x 在图中标出,图中箭头是由较大元素指向较小元素。

假设所有元素互不相同,在这种情况下,找出的基准 x 至少比 3\lfloor (n-5)/10\rfloor 个元素大,因为在每一组中有两个元素小于本组的中位数,而 \lfloor n/5\rfloor 个中位数中又有 \lfloor (n-5)/10\rfloor 个小于基准 x ,同理,基准 x 也至少比 3\lfloor (n-5)/10\rfloor 个元素小。当 n\geq 75 时, 3\lfloor (n-5)/10\rfloor\geq n/4 ,所以按此基准划分所得的两个子数组的长度都至少缩短 1/4\ 。不考虑不足 5 个元素的组的情况下,

  • \lfloor n/5\rfloor 为奇数时,至少有 (\lfloor n/5\rfloor-1)/2 个组中的部分元素比 x 小;
  • \lfloor n/5\rfloor 为偶数时,至少有 \lfloor n/5\rfloor/2 个组中的部分元素比 x 小。

所以,至少有 (\lfloor n/5\rfloor-1)/2 个组中的部分元素比 x 小,每个组有 3 个元素比 x 小,所以 x 至少比 3((\lfloor n/5\rfloor-1)/2)=3(\lfloor (n-5)/5\rfloor/2)= 3\lfloor (n-5)/10\rfloor 个元素大,同理,比 x 大的元素至少存在有 3\lfloor (n-5)/10\rfloor 个。

综上所述,可以得到 select 算法如下,

public static Comparable select(Comparable[] a, int p, int r, int k) {
    if(r - p < 75) {
        bubbleSort(a, p, r);
        return a[p + k - 1];
    }
    // 将 a[p+5*i] 至 a[p+5*i+4] 的第3小元素与 a[p+i] 交换位置
    // 找中位数的中位数,r - p - 4 即 n - 5
    for(int i = 0; i <= (r - p - 4)/5; i++) {
        int s = p + 5 * i, t = s + 4;
        for(int j = 0; j < 3; j++) bubble(a, s, t - j);
        swap(a, p + i, s + 2);  // 交换每组中位数到前面
    }
    Comparable x = select(a, p, p + (r - p - 4)/5, (r - p + 6)/10);
    // (n + 1)/2 = ((r - p + 1)/5 + 1)/2 = (r - p + 6)/10
    int i = partition(a, p, r, x), j = i - p + 1;
    if(k <= j) return select(a, p, i, k);
    else return select(a, i + 1, r, k - j);
}
public static int partition(Comparable[] a, int p, int r, Comparable val) {
    int pos = p;
    for(int q = p; q <= r; q++)
        if(a[q] == val) {
            pos = q;
            break;
        }
    swap(a, p, pos);
    int i = p, j = r + 1;
    Comparable x = a[p];
    // 将 <= x 的元素交换到左侧, >= x 的元素交换到右侧
    while(true) {
        while(a[++i].compareTo(x) < 0 && i < r);
        while(a[--j].compareTo(x) > 0);
        if(i >= j) break;
        swap(a, i, j);
    }
    swap(a, p, j);
    return j;
}
public static void bubbleSort(Comparable[] a, int p, int r) {
    for(int i = 0; i < r - p; i++) bubble(a, p, r - i);
}
public static void bubble(Comparable[] a, int p, int r) {
    for(int i = p; i < r; i++)
        if(a[i].compareTo(a[i + 1]) > 0) swap(a, i, i + 1);
}

n 为数组长度,算法的递归调用只有在 n\geq 75 时才执行,当 n<75 时算法所用的计算时间不超过一个常数 C_1 ,找到中位数 x 后,以 x 为划分基准调用 partition 对数组进行划分需要 O(n) 的时间,算法的 for 循环体共执行 n/5 次,每次需要 O(1) 时间,因此执行 for 循环需要 O(n) 时间。

设对 n 个元素的数组调用 select 算法需要 T(n) 时间,那么找中位数的中位数 x 至多用了 T(n/5) 的时间,按照算法所选的基准 x 进行划分所得到的两个子数组分别至多有 3n/4 个元素,则有,

T(n)\leq\left\{ \begin{array}{cl} C_1 & n<75\\ C_2n+T(n/5)+T(3n/4)& n\geq 75 \end{array} \right.\quad \Rightarrow\ T(n)=O(n)

由于算法将每一组的大小定为 5 ,并选取 75 作为是否作递归调用的分界点,保证了 T(n) 递归式中两个自变量之和 n/5+3n/4=19n/20=\alpha n,\ 0<\alpha<1 ,这是使 T(n)=O(n) 的关键,当然也可以选择其他常数。select 算法中假定所有元素都不相等,当元素可能相等时,应在划分之后加一个语句,将所有与基准元素相等的集中在一起,设这种元素有 m\ (m\geq 1) 个,若 j\leq k\leq j+m-1 ,则不必递归调用,直接返回 a[i] ,否则,最后一行改为调用 select (i+m-1,r,k-j-m)

第二章作业题

习题 2-3 改写二分搜索算法

a[0:n-1] 是已经升序排好的数组,改写二分搜索算法,当搜索元素 x 不在数组中时,返回小于 x 的最大元素位置 i 和大于 x 的最小元素位置 j ,当搜索元素 x 在数组中时, i j 相同,均为 x 在数组中的位置。

public static boolean binarySearch(int[] a, int x, int left, int right, int[] ind) {
    int middle;
    while(left <= right) {
        middle = (left + right) / 2;
        if(x == a[middle]) {
            ind[0] = ind[1] = middle;
            return true;
        } else if(x > a[middle]) left = middle + 1;
        else right = middle - 1;
    }
    ind[0] = right;     // ind[0] 是小于 x 的最大元素位置
    ind[1] = left;      // ind[1] 是大于 x 的最小元素位置
    return false;
}

习题 2-8 不动点问题的 O(log n) 时间算法

n 个不同的整数升序排好后存于 T[0:n-1] 中。若存在下标 i,\ 0\leq i< n ,使得 T[i]=i ,设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为 O(\log n)

**解:**由于 n 个整数是不同的,因此对任意 0\leq i< n-1 ,有 T[i]\leq T[i+1]-1

  1. 对于 0\leq i< n ,当 T[i]>i 时,对任意的 i\leq j<n ,有,
T[j]\geq T[i]+j-i>i+j-i=j\quad \Rightarrow\ T[j]>j
  1. 对于 0\leq i< n ,当 T[i]<i 时,对任意的 0\leq j \leq i ,有,
T[j]\leq T[i]-i+j <i-i+j=j \quad \Rightarrow\ T[j]< j

由 1. 2. 可知,用二分搜索算法可以在 O(\log n) 时间内找到所需要的下标。

习题 2-9 主元素问题的线性时间算法

T[0:n-1] n 个元素的数组。对任一元素 x ,设 S(x)=\{i\ |\ T[i]=x\} 。当 |S(x)|>n/2 时,称 x T 的主元素。设计一个线性时间算法,确定 T[0:n-1] 是否有一个主元素。

**解:**如果 T 有一个主元素 x ,则 x T 的中位数。反之,如果 T 的中位数不是 T 的主元素,则 T 没有主元素,因此,用一个线性时间找到中位数,然后再线性扫描一遍数组判断是不是主元素。

习题 2-15 最大值和最小值问题的最优算法

给定数组 a[0:n-1] ,试设计一个算法,在最坏情况下用 \left\lceil 3n/2-2 \right\rceil 次比较找出 a[0:n-1] 中元素的最大值和最小值。

**解:**设所给的 n 个实数为 x[i],\ i=1,2,\ldots,n\ 。首先,显然有,

\left\lceil 3n/2-2 \right\rceil=n+\left\lceil n/2 \right\rceil-2=2n-(n-\left\lceil n/2 \right\rceil)-2=2n-\lfloor n/2 \rfloor-2
  1. n 为偶数时,设 n=2k ,首先,作 k 次比较 x[i]:x[k+i],\ 1\leq i\leq k\ 。当 x[k+i]>x[i] 时,交换它们的位置。这样,经 k 次比较后有 x[i]\leq x[k+i],\ 1\leq i\leq k\

    然后,用 k-1 次比较找出 x[1:k] 中最大者,再用 k-1 次比较找出 x[k+1:n] 中最小者。这两个数即为所要求的最大值与最小值。比较次数为,

k+2k-2=3k-2=2n-\lfloor n/2\rfloor-2
  1. n 为奇数时,设 n=2k+1 ,首先,用对 n 为偶数时的方法找出 x[1:n-1] 中的最大值与最小值。然后,再将 x[n] 与找出的最大值与最小值做两次比较,即可确定所要的最大值与最小值。在这种情况下,比较次数为,
3k-2+2=3k=4k+2-k-2=2n-\lfloor n/2\rfloor-2

由 1. 2. 可知,上述算法需要比较的次数为 2n-\lfloor n/2\rfloor-2=\left\lceil 3n/2-2 \right\rceil

习题 2-27 最接近中位数的 k 个数

给定由 n 个互不相同的数组成的集合 S 以及正整数 k\leq n ,试设计一个 O(n) 时间算法,找出 S 中最接近 S 的中位数的 k 个数。

**解:**1. 找出 S 的中位数 \text{median }

  1. 计算 T=\{|x-\text{median}|\ |\ x\in S\}
  2. 找出 T 的第 k 小元素 y
  3. 线性扫描一遍,根据 y 找出所要的解 \{x\in S\ |\ |x-\text{median}|\leq y\}

在最坏情况下,线性时间选择的计算时间为 O(n) ,因此 1. 3. 需要 O(n) 时间。2. 4. 都是线性扫描,显然也只需要 O(n) 时间,所以在最坏情况下算法的计算时间为 O(n)

动态规划

基本思想

与分治法类似,动态规划的基本思想也是将待求解问题分解成若干子问题,用最优原则来建立递归关系式。但是经分解得到的子问题往往不是互相独立的(重叠子问题),不同子问题的数目只有多项式量级,在用分治法求解时,有些子问题被重复计算,导致算法需要指数级时间复杂度。

如果能保存已解决子问题的答案,对每一个问题只计算一次,而后将其解存在一个表格(备忘录)中,当再次要解此问题时,用常数时间调用已有的结果,就可以避免重复,得到多项式时间的算法。

动态规划的基本步骤

  1. 找出最优解的性质,并刻画其结构特征。
  2. 递归地定义最优值。
  3. 以自底向上的方式计算出最优值。
  4. 根据计算最优值过程中得到的信息,构造最优解。

步骤 1. ~ 3. 是动态规划的基本步骤,在只需最优值的情形,步骤 4. 可以省去。

动态规划的设计要素

  • 建模时,优化的目标函数是什么,约束条件是什么;
  • 如何划分子问题(边界);
  • 问题的优化函数值与子问题的优化函数值存在什么依赖关系(递推方程);
  • 是否满足优化原则或最优子结构;
  • 最小子问题怎样界定,初值等于什么。

矩阵连乘问题

给定 n 个矩阵 \{A_{1},A_2,\ldots,A_n\} A_i p_{i-1}\times p_i 大小的矩阵, i=1,2,\ldots,n ,其中 A_i A_{i+1} 是可乘的, i=1,2,\ldots,n-1 ,试确定矩阵的乘法顺序,使得元素相乘的总次数最少。

矩阵 A 和矩阵 B 可乘的条件是矩阵 A 的列数等于矩阵 B 的行数,若 A 是一个 p\times q 矩阵, B 是一个 q\times r 矩阵,则其乘积 C=AB 是一个 p\times r 矩阵,根据矩阵乘法的标准算法,总共需要 pqr 次数乘。

完全加括号的矩阵连乘积可递归地定义为:

  • 递归出口:单个矩阵是完全加括号的;
  • 递归方式:矩阵连乘积 A 是完全加括号的,则 A 可表示为 2 个完全加括号的矩阵连乘积 B C 的乘积并加括号,即 A=(BC)

首先容易想到穷举法,列举出所有可能的计算次序,并计算每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。对于 n 个矩阵的连乘积,设不同的计算次序有 P(n) 种,每种加括号方式都可以分解为两个矩阵子序列的加括号: ((A_1,\ldots,A_k)(A_{k+1},\ldots,A_n)) P(n) 递推式为:

P(n)=\left\{ \begin{array}{cl} 1 & n = 1\\ \displaystyle\sum_{k=1}^{n-1}P(k)P(n-k) & n>1 \end{array} \right.

解此递归方程, P(n) 实际是 Catalan 数,即 P(n)=C(n-1) ,其中,

C(n)=\frac{1}{n+1}\left(\begin{array}{c} 2n\\n \end{array}\right)=\Omega(4^n/n^{3/2})

显然 P(n) 是随 n 的增长呈指数增长的,在 n 较大时不可行。

分析最优解的结构

将矩阵连乘积 A_i A_{i+1}\cdots A_j 记为 A[i:j],\, i\leq j ,考查计算 A[i:j] 的最优计算次序,设这个计算次序在矩阵 A_k A_{k+1} 之间将矩阵链断开 (i\leq k<j) ,则加括号方式为 ((A_i,\ldots,A_k)(A_{k+1},\ldots,A_j)) ,按此计算次序,总计算量为 A[i:k] 的计算量加上 A[k+1:j] 的计算量,再加上二者相乘的计算量。

问题特征:计算 A[i:j] 的最优次序所包含的计算矩阵子链 A[i:k] A[k+1:j] 也是最优的。

证明:反证法,如果有一个计算 A[i:k] 的次序需要的计算量更少,则用此次序替换原来计算 A[i:k] 的次序,得到的计算 A[i:j] 的计算量将比按最优次序计算所需计算量更少,这是矛盾的。同理可知,计算 A[i:j] 的最优次序所包含的计算矩阵子链 A[k+1:j] 的次序也是最优的。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解,这种性质称为最优子结构性质

建立递归关系

设计算 A[i:j]\,\, (1\leq i\leq j\leq n) 所需的最少数乘次数为 m[i,j] ,则原问题最优值就是 m[1,n]

  • i=j 时, A[i:j]=A_i ,单一矩阵无需计算, m[i,i]=0,\,\, (i=1,2,\ldots,n)
  • i<j 时,若计算 A[i:j] 的最优次序在 A_k A_{k+1} 之间断开 (i\leq k<j) ,则,
m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}p_k p_j

因此,可以递归地定义 m[i,j] 为:

m[i,j]=\left\{ \begin{array}{cl} 0 & i=j \\ \displaystyle\min_{i\leq k<j}\{m[i,k]+m[k+1,j]+p_{i-1}p_k p_j\} & i<j \end{array} \right.

m[i,j] 给出了最优值的同时还确定了计算 A[i:j] 的最优次序中的断开位置 k ,若将断开位置 k 记为 s[i,j] ,在计算出最优值 m[i,j] 后,可递归地由 s[i,j] 构造出相应的最优解。递归算法如下,

// p 数组存放矩阵链的行列信息,p[i-1] 和 p[i] 分别为第 i 个矩阵的行和列
int recurMatrixChain(int i, int j) {
    if(i == j) return 0;	// 只有一个矩阵,返回 0
    int u = recurMatrixChain(i+1, j) + p[i-1]*p[i]*p[j]; // 计算 A[i:j]=A_i*A[i+1:j]
    s[i][j] = i;	// 记录断点 i
    for(int k = i+1; k < j; k++) {
        int t = recurMatrixChain(i, k) + recurMatrixChain(k+1, j) + p[i-1]*p[k]*p[j];
        // 对 i<k<j,逐个计算 A[i:j]=A[i:k]A[k+1:j]
        if(t < u) {
            u = t;
            s[i][j] = k;	// 记录最小的 m[i,j] 及对应的断点 k
        }
    }
    return u;
}

直接递归的算法会有许多子问题被重复计算,可以证明该算法计算时间 T(n) 有指数下界,

T(n)\geq \left\{ \begin{array}{cl} O(1) & n =1\\ 1+\displaystyle\sum_{k=1}^{n-1}(T(k)+T(n-k)+1) & n>1 \end{array} \right.\\ \begin{aligned} n>1,\,\,T(n)\geq 1+(n-1)+\sum_{k=1}^{n-1}(T(k)+T(n-k)) = n +\sum_{k=1}^{n-1}T(k)+\sum_{k=1}^{n-1}T(n-k)=n+2\sum_{k=1}^{n-1}T(k) \end{aligned}

可用数学归纳法证明 T(n)\geq 2^{n-1}=\Omega(2^n)

动态规划计算最优值

对于 1\leq i\leq j\leq n ,不同的有序对 (i,j) 对应于不同的子问题,因此不同子问题个数最多有,

\left(\begin{array}{c}n\\2\end{array}\right)+n=\Theta(n^2)

用动态规划解此问题,可以按递归式以自底向上的方式进行计算,为了去掉重复计算,在计算过程中,保存已解决的子问题答案,每个子问题只计算一次,最终得到多项式时间的算法,

public static void matrixChain(int[] p, int [][]m, int [][]s) {
    // p 存放矩阵的行列数,m 存放最优值,s 存放断开位置
    int n = p.length - 1;
    for(int i = 1; i <= n; i++) m[i][i] = 0;    // 单个矩阵计算量为 0
    for(int r = 2; r <= n; r++) {       // 按矩阵链长度递增计算
        for(int i = 1; i <= n - r + 1; i++) {   // i 可能的起点
            int j = i + r - 1;      // 对应 i,包含 r 个矩阵的终点
            m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]; // 计算 A[i:j]=A_iA[i+1,j]
            s[i][j] = i;    // 记录断点 i
            for(int k = i + 1; k < j; k++) {
                int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                // 对 i<k<j,逐个计算 A[i:j]=A[i:k]A[k+1:j]
                if(t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = k;    // 记录最小的 m[i,j] 及对应的断点 k
                }
            }
        }
    }
}

算法 matrixChain 首先计算出 m[i][i]=0,\,i=1,2,\ldots,n ,然后按矩阵链递增的方式依次计算出,矩阵链长度为 2 的: m[i][i+1],\,i=1,2,\ldots,n-1 ,长度为 3 的: m[i][i+2],\,i=1,2,\ldots,n-2 ,……。在计算 m[i][j] 过程中只用到已经计算过的 m[i][k] m[k+1][j]

算法 matrixChain 的主要计算量取决于算法中对 r,i,k 的三重循环,循环体内计算量为 O(1) ,三重循环的总次数为 O(n^3) ,因此算法的时间上界为 O(n^3) ,所占空间显然是 O(n^2)

构造最优解

s[i][j] 中的 k 表示矩阵链 A[i:j] 的最优方式是在 A_k A_{k+1} 之间断开,因此由 s[1][n] 可知 A[1:n] 的最优加括号方式为 (A[1:s[1][n]])(A[s[1][n]+1:n]) ,递归构造即可,时间复杂度 O(n)

public static void traceback(int [][] s, int i, int j) {
    if(i == j) {
        System.out.print("A" + i);
        return;
    }
    System.out.print("(");
    traceback(s, i, s[i][j]);
    traceback(s, s[i][j] + 1, j);
    System.out.print(")");
    //System.out.println("Multiply A[" + i + ":" + s[i][j] +
    //        "] and A[" + (s[i][j] + 1) + ":" + j + "]");
}

备忘录方法

备忘录方法是动态规划方法的变形,但是采用的递归方式是自顶向下。备忘录方法在递归求解过程中,对每个待解的子问题,先检查是否已求解,若未求解,则递归计算,若已求解,则取出相应的结果。备忘录方法同样避免了子问题的重复计算,和动态规划有同样的效率。

public static int memorizedMatrixChain(int n) {
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            m[i][j] = 0;
    return lookupChain(1, n);
}
public static int lookupChain(int i, int j) {
    if(m[i][j] > 0) return m[i][j];
    if(i == j) return 0;
    int u = lookupChain(i+1, j) + p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for(int k = i + 1; k < j; k++) {
        int t = lookupChain(i, k) + lookupChain(k+1, j) + p[i-1]*p[k]*p[j];
        if(t < u) {
            u = t;
            s[i][j] = k;
        }
    }
    m[i][j] = u;
    return u;
}

一般来讲,当一个问题的所有子问题都至少要解一次时,动态规划方法优于备忘录方法,此时动态规划方法没有任何多余的计算;当子问题空间中部分子问题可不必求解时,备忘录方法更有利,从其算法结构可以看出,该方法只会求解那些需要求解的子问题。

最长公共子序列

给定序列 X=\{x_1,x_2,\ldots,x_m\} ,则序列 Z=\{z_1,z_2,\dots,z_k\} X 的子序列,指的是存在一个严格递增的下标序列 \{i_1,i_2,\ldots,i_k\} 使得对于所有 j=1,2,\dots,k ,有 z_j=x_{i_j}

给定两个序列 X Y ,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z X Y 的公共子序列。给定两个序列 X=\{x_1,x_2,\ldots,x_m\},\,Y=\{y_1,y_2,\ldots,y_n\} ,找出 X Y 的最长公共子序列。

最优子结构性质

设序列 X=\{x_1,x_2,\ldots,x_m\},\,Y=\{y_1,y_2,\ldots,y_n\} 的最长公共子序列为 Z=\{z_1,z_2,\ldots,z_k\} ,则,

  1. x_m=y_n ,则 z_k=x_m=y_n ,且 Z_{k-1} X_{m-1} Y_{n-1} 的最长公共子序列。
  2. x_m\ne y_n z_k\ne x_m ,则 Z X_{m-1} Y 的最长公共子序列。
  3. x_m\ne y_n z_k\ne y_n ,则 Z X Y_{n-1} 的最长公共子序列。

其中, X_{m-1}=\{x_1,x_2,\ldots,x_{m-1}\},\,Y_{n-1}=\{y_1,y_2,\ldots,y_{n-1}\},\,Z_{k-1}=\{z_1,z_2,\ldots,z_{k-1}\}

证明:1. 用反证法,若 z_k\ne x_m ,则 \{z_1,z_2,\ldots,z_k,x_m\} X Y 的长度为 k+1 的公共子序列,这与 Z X Y 的最长公共子序列矛盾,因此必有 z_k=x_m=y_n Z_{k-1} X_{m-1} Y_{n-1} 的长度为 k-1 的公共子序列,若 X_{m-1} Y_{n-1} 有长度大于 k-1 的公共子序列 w ,则将 x_m 加在其尾部产生 X Y 的长度大于 k 的公共子序列,这是矛盾的,所以 Z_{k-1} X_{m-1} Y_{n-1} 的最长公共子序列。

  1. 由于 z_k\ne x_m Z X_{m-1} Y 的公共子序列。若 X_{m-1} Y 有长度大于 k 的公共子序列 W ,则 W 也是 X Y 的长度大于 k 的公共子序列,这与 Z X Y 的最长公共子序列矛盾。因此 Z X_{m-1} Y 的最长公共子序列。3. 的证明与 2. 同理。

由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此,最长公共子序列问题具有最优子结构性质。

递归关系

由最优子结构性质可知,可按以下方法递归计算:当 x_m=y_n 时,找出 X_{m-1} Y_{n-1} 的最长公共子序列,然后在其尾部加上 x_m 即是 X Y 的最长公共子序列;当 x_m\ne y_n 时,找出 X_{m-1} Y 的最长公共子序列和 X Y_{n-1} 的最长公共子序列,较长者就是 X Y 的最长公共子序列。

c[i][j] 记录 X_i Y_j 的最长公共子序列的长度,其中 X_{i}=\{x_1,x_2,\ldots,x_{i}\},\,Y_{j}=\{y_1,y_2,\ldots,y_{j}\} ,当 i=0 j=0 时,空序列是 X_i Y_j 的最长公共子序列, c[i][j]=0 。构建递归关系,

c[i][j]=\left\{ \begin{array}{cl} 0& i=0\, \or\, j=0\\ c[i-1][j-1]+1 & i,j>0,\,x_i=x_j\\ \max\{c[i][j-1],c[i-1][j]\} &i,j>0,\,x_i\ne x_j \end{array} \right.

显然该问题具备子问题重叠的性质。

计算最长公共子序列

考虑子问题空间中,总共有 \Theta(mn) 个不同的子问题,因此,用动态规划方法自底向上地计算最优值,在计算 c[i][j] 之前, c[i-1][j-1],\,c[i-1][j],\,c[i][j-1] 均已计算出来。

算法 lcsLength 以序列 X_{m}=\{x_1,x_2,\ldots,x_{m}\},\,Y_{n}=\{y_1,y_2,\ldots,y_{n}\} 作为输入,输出两个数组 c b ,其中, c[i][j] 存储 X_i Y_j 的最长公共子序列的长度, b[i][j] 记录 c[i][j] 的值是由哪一个子问题的解得到的,这在构造最长公共子序列时要用到,问题的最优值记录于 c[m][n]

public static int lcsLength(char []x, char []y, int[][] c, int[][] b) {
    int m = x.length - 1;
    int n = y.length - 1;
    for(int i = 1; i <= m; i++) c[i][0] = 0;
    for(int i = 1; i <= n; i++) c[0][i] = 0;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(x[i] == y[j]) {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            } else if(c[i-1][j] >= c[i][j-1]) {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            } else {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
    }
    return c[m][n];
}

由于每个数组单元的计算耗费 O(1) 时间,算法 lcsLength 耗时 O(mn) 。然后根据 b 数组的内容打印出最长公共子序列,由于每次递归都会使 i j 减小 1 ,所以时间复杂度为 O(m+n)

public static void lcs(int i, int j, char []x, int [][]b) {
    if(i == 0 || j == 0) return;
    if(b[i][j] == 1) {
        lcs(i-1, j-1, x, b);	// X_i 和 Y_j 的 lcs 由 X_{i-1} 和 Y_{j-1} 的 lcs,
        System.out.print(x[i]);	// 再加上 x_i 得到
    } else if(b[i][j] == 2) {
        lcs(i-1, j, x, b);	// X_i 和 Y_j 的 lcs 与 X_{i-1} 和 Y_j 的 lcs 相同
    } else lcs(i, j-1, x, b);	// X_i 和 Y_j 的 lcs 与 X_i 和 Y_{j-1} 的 lcs 相同
}

算法改进

数组元素 c[i][j] 的值仅由 c[i-1][j-1],\, c[i-1][j],\, c[i][j-1] 确定,所以可以不借助数组 b 仅借助 c 本身,在 O(1) 时间内确定 c[i][j] 的值是由 c[i-1][j-1],\, c[i-1][j],\, c[i][j-1] 的哪一个值确定,在 O(mn) 时间内构造最长公共子序列。从而可以省 \Theta(mn) 的空间,对常数因子做改进。实例:

\begin{array}{|cc|c|c|c|c|c|c|c|} \hline &j&0&1&2&3&4&5&6\\ i&&y_j&\color{red}{\text{B}}&\text{D}&\color{red}{\text{C}}&\text{A}&\color{red}{\text{B}}&\color{red}{\text{A}}\\ \hline 0&x_i&0&0&0&0&0&0&0\\ \hline 1&\text{A}&\color{blue}{0}&\uparrow0&\uparrow0&\uparrow0&\nwarrow1&\leftarrow1&\nwarrow 1\\ \hline 2&\color{red}{\text{B}}&0&\color{red}{\nwarrow 1}&\color{red}{\leftarrow 1}&\leftarrow 1& \uparrow1 &\nwarrow2&\leftarrow2 \\ \hline 3&\color{red}{\text{C}}&0&\uparrow1 &\uparrow1 &\color{red}{\nwarrow 2}&\color{red}{\leftarrow 2}&\uparrow2&\uparrow2 \\ \hline 4&\color{red}{\text{B}}&0&\nwarrow1&\uparrow1&\uparrow2&\uparrow2&\color{red}{\nwarrow 3}&\leftarrow 3 \\ \hline 5&\text{D}&0&\uparrow1&\nwarrow2&\uparrow2&\uparrow2&\color{red}{\uparrow 3}&\uparrow 3 \\ \hline 6&\color{red}{\text{A}}&0&\uparrow 1&\uparrow 2&\uparrow 2&\nwarrow 3&\uparrow 3&\color{red}{\nwarrow 4} \\ \hline 7&\text{B}&0&\nwarrow 1&\uparrow 2&\uparrow 2&\uparrow 3&\nwarrow 4&\color{red}{\uparrow 4} \\ \hline \end{array}

另外,如果只需要计算最长公共子序列的长度,则可以对空间复杂度做出改进。事实上,在计算 c[i][j] 时,只用到数组 c 的第 i 行和第 i-1 行,因此,可以使用滚动数组,用两行的空间就可以计算出最长公共子序列的长度,空间复杂度减少至 O(\min\{m,n\})

凸多边形最优三角剖分

用多边形顶点的逆时针序列表示凸多边形,即 P=\{v_0,v_1,\ldots,v_{n-1}\} 表示具有 n 条边 v_0v_1 , \,v_1v_2 , \,\ldots\, , \,v_{n-1}v_n 的凸多边形,其中,规定 v_0=v_n 。若 v_i v_j 是多边形上不相邻的两个顶点,则线段 v_iv_j 称多边形的一条弦,弦将多边形分割成两个多边形: \{v_i,v_{i+1},\ldots,v_j\} \{v_j,v_{j+1},\dots,v_i\} 。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合 T n 个顶点的凸多边形的三角剖分有 n-3 条弦和 n-2 个三角形。例如下图就是一个凸七边形的两个不同的三角剖分。

给定凸多边形 P=\{v_0,v_1,\ldots,v_{n-1}\} ,以及定义在由多边形的边和弦组成的三角形上的权函数 w ,要求确定该凸多边形的三角剖分,使得该三角剖分中所有三角形上权之和为最小。

定义在三角形上的权函数 w 可以是任意的,例如 w(v_iv_jv_k)=|v_iv_j|+|v_jv_k|+|v_kv_i| ,其中 |v_iv_j| 是点 v_i v_j 的欧氏距离,此权函数的最优三角剖分即为最小弦长三角剖分。

一个表达式的完全加括号方式相应于一棵完全二叉树,称为表达式的语法树,例如,完全加括号的矩阵连乘积 ((A_1(A_2A_3))(A_4(A_5A_6))) 相应的语法树如下图(左)所示。

语法树的每个叶子表示表达式中一个原子,若某结点左子树表示表达式 E_l ,右子树表示表达式 E_r ,则以该结点为根的子树表示表达式 E_lE_r 。凸多边形三角剖分也可以用语法树表示,如上述第一种三角剖分可用上图(右)中所示的语法树表示,该语法树的根节点为边 v_0v_6 ,三角剖分中的弦组成其余内结点,多边形中的其他边都是语法树的一个叶结点。显然,凸 n 边形的三角剖分与有 n-1 个叶结点的语法树之间存在一一对应关系;由于 n 个矩阵的完全加括号乘积与 n 个叶结点的语法树之间存在一一对应关系,因此 n 个矩阵的完全加括号乘积与凸 (n+1) 边形中的三角剖分之间存在一一对应关系,如上图表示出这种对应关系。 n 个矩阵连乘积中的每个矩阵 A_i 对应于凸 (n+1) 边形中的一条边 v_{i-1}v_i ;三角剖分中的一条弦 v_iv_j\,(i<j) ,对应于矩阵连乘积 A[i+1:j]

上图为另一种三角剖分的语法树,对应完全加括号的矩阵连乘 (A_1(((A_2A_3)A_4)(A_5A_6)))

最优子结构性质

若凸 (n+1) 边形 P=\{v_0,v_1,\ldots,v_n\} 的最优三角剖分 T 包含三角形 v_0v_kv_n\,(1\leq k< n) ,则 T 的权为三个部分权的和:三角形 v_0v_kv_n 的权,子多边形 \{v_0,v_1,\ldots,v_k\} \{v_k,v_{k+1},\ldots,v_n\} 的权之和。可以断言,由 T 所确定的这两个子多边形的三角剖分也是最优的。因为若有比两个子多边形的权更小的三角剖分将导致 T 不是最优三角剖分的矛盾。

递归关系

定义 t[i][j]\,(1\leq i<j\leq n) 为凸子多边形 \{v_{i-1},v_i,\ldots,v_j\} 的最优三角剖分所对应的权函数值,即最优值。设退化的多边形 \{v_{i-1},v_i\} 具有权值 0 ,因此,凸 (n+1) 边形 P 的最优权值为 t[1][n]

j-i\leq 1 时,凸子多边形至少有 3 个顶点。由最优子结构性质, t[i][j] 的值应为 t[i][k] 的值加上 t[k+1][j] 的值,再加上三角形 v_{i-1}v_kv_j 的权值, (i\leq k< j) ,递归定义为,

t[i][j]=\left\{ \begin{array}{cl} 0 & i=j \\ \displaystyle\min_{i\leq k<j}\{t[i][k]+t[k+1][j]+w(v_{i-1}v_k v_j)\} & i<j \end{array} \right.
计算最优值与构造最优解

与矩阵连乘积问题算法基本相同,只是修改其中权函数的计算部分,空间复杂度 O(n^2) ,时间复杂度 O(n^3) 。构造最优解的过程是相同的,在计算每一个凸子多边形 \{v_{i-1},v_i,\ldots,v_j\} 的最优值时,用数组 s 记录了最优三角剖分中的所有三角形信息,其中 s[i][j] 记录了与 v_{i-1},\,v_j 一起构成三角形的第 3 个顶点的位置,据此,可以用 O(n) 时间构造出最优三角剖分中的所有三角形。

电路布线

在电路板的上下两端分别有 n 个接线柱,根据电路设计,要求用导线 (i,\pi(i)) 将上端接线柱 i 与下端接线柱 \pi(i) 相连,其中 \pi(i),\, 1\leq i\leq n ,是 \{1,2,\ldots,n\} 的一个排列,导线 (i,\pi(i)) 称为该电路板上的第 i 条连线。对任意 1\leq i<j\leq n ,第 i 条连线和第 j 条连线相交的充要条件是 \pi(i)>\pi(j)

电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线,即该问题要求确定导线集 \text{Nets}=\{(i,\pi(i)),\,1\leq i\leq n\} 的最大不相交子集。

最优子结构性质

N(i,j)=\{t|(t,\pi(t))\in\text{Nets},\, t\leq i,\, \pi(t)\leq j\}

N(i,j) 的最大不相交子集为 \text{MNS}(i,j) \text{Size}(i,j)=|\text{MNS}(i,j)|

  • i=1 时, \text{MNS}(i,j)=N(1,j)=\left\{\begin{array}{cl}\varnothing & j<\pi(1)\\\{(1,\pi(1))\} & j\geq \pi(1)\end{array}\right.
  • i>1 时, j<\pi(i),\,(i,\pi(i))\notin N(i,j),\,N(i,j)=N(i-1,j),\, \text{Size}(i,j)=\text{Size}(i-1,j)

j\geq \pi(i) ,此时,若 (i,\pi(i))\in \text{MNS}(i,j) ,则对任意 (t,\pi(t))\in \text{MNS}(i,j),\, t<i \pi(t)<\pi(i) ,否则, (t,\pi(t)) (i,\pi(i)) 相交,在这种情况下 \text{MNS}(i,j)-\{(i,\pi(i))\} N(i-1,\pi(i)-1) 的最大不相交子集,即 \text{Size}(i,j)=\text{Size}(i-1,\pi(i)-1)+1 。否则,子集

\text{MNS}(i-1,\pi(i)-1)\cup \{(i,\pi(i))\}\subseteq N(i,j)

是比 \text{MNS}(i,j) 更大的 N(i,j) 的不相交子集,这与定义矛盾。

(i,\pi(i))\notin \text{MNS}(i,j) ,则对任意 (t,\pi(t))\in \text{MNS}(i,j) t<i ,从而 \text{MNS}(i,j)\subseteq N(i-1,j) ,因此, \text{Size}(i,j)\leq \text{Size}(i-1,j) ;另一方面, \text{MNS}(i-1,j)\subseteq N(i,j) ,故 \text{Size}(i,j)\geq \text{Size}(i-1,j) ,从而有 \text{Size}(i,j)=\text{Size}(i-1,j)

由上述分析可知,电路布线问题具有最优子结构性质。

递归计算最优值

电路布线问题的最优值为 \text{Size}(n,n) ,由最优子结构性质可知:

  • i=1 时, \text{Size}(1,j)=\left\{\begin{array}{cl}0 & j<\pi(1)\\1& j\geq \pi(1)\end{array}\right.
  • i>1 时, \text{Size}(i,j)=\left\{\begin{array}{cl}\text{Size}(i-1,j) & j<\pi(i)\\ \max\{\text{Size}(i-1,j),\text{Size}(i-1,\pi(i)-1)+1\} & j\geq \pi(i)\end{array}\right.

根据递归结构可以得到电路布线的动态规划算法:

public static void mnset(int []c, int [][]size) {
    int n = c.length - 1;
    for(int j = 0; j < c[1]; j++) size[1][j] = 0;
    for(int j = c[1]; j <= n; j++) size[1][j] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < c[i]; j++) size[i][j] = size[i-1][j];
        for(int j = c[i]; j <= n; j++)
            size[i][j] = Math.max(size[i-1][j], size[i-1][c[i]-1] + 1);
    }
    size[n][n] = Math.max(size[n-1][n], size[n-1][c[n]-1] + 1);
}

构造最优解

根据算法 mnset 计算出的 \text{size}[i][j] 的值,容易由算法 traceback 构造最优解 \text{MNS}(n,n)

public static void traceback(int []c, int [][]size, int []net) {
    int n = c.length - 1;
    int j = n, m = 0;
    for(int i = n; i > 1; i--)
        if(size[i][j] != size[i-1][j]) {
            net[m++] = i;
            j = c[i] - 1;
        }
    if(j >= c[1]) net[m++] = 1;
    return m;
}

其中,用数组 \text{net}[0:m-1] 存储 \text{MNS}(n,n) 中的 m 条连线。算法 mnset 显然需要 O(n^2) 的计算时间和 O(n^2) 的空间;算法 traceback 需要 O(n) 的计算时间。

流水作业调度

n 个作业 \{1,2,\ldots, n\} 要在由两台机器 M_1 M_2 组成的流水线上完成加工,每个作业的加工顺序都是先在 M_1 上加工,然后在 M_2 上加工, M_1 M_2 加工作业 i 所需的时间分别为 a_i b_i

流水作业调度问题要求确定 n 个作业的最优加工顺序,使得从第一个作业在机器 M_1 上开始加工,到最后一个作业在机器 M_2 上加工完成所需的时间最少。

一个**最优调度应使机器 M_1 没有空闲时间,且机器 M_2 的空闲时间最少。一般情况下,机器 M_2 上会有机器空闲和作业积压两种情况。**设全部作业的集合为 N=\{1,2,\ldots,n\} S\subseteq N N 的作业子集,在一般情况下,**机器 M_1 开始加工 S 中作业时,机器 M_2 还在加工其他作业,要等时间 t 后才可利用。将这种情况下完成 S 中作业所需的最短时间记为 T(S,t) 。**流水作业调度问题的最优值为 T(N,0)

最优子结构性质

\pi n 个流水作业的一个最优调度,所需的加工时间为 a_{\pi(1)}+T^{\prime} ,其中 T^{\prime} 是在机器 M_2 的等待时间为 b_{\pi(1)} 时,安排作业 \pi(2),\ldots,\pi(n) 所需的时间。记 S=N-\{\pi(1)\} ,则有 T^{\prime}=T(S,b_{\pi(1)})

T 的最优性可知, T^{\prime}\geq T(S,b_{\pi(1)}) ,若 T^{\prime}> T(S,b_{\pi(1)}) ,设 \pi^{\prime} 是作业集 S 在机器 M_2 的等待时间为 b_{\pi(1)} 情况下的一个最优调度。则 \pi(1),\pi^{\prime}(2),\ldots,\pi^{\prime}(n) N 的一个调度,这个调度所需的时间为 a_{\pi(1)}+T(S,b_{\pi(1)})<a_{\pi(1)}+T^{\prime} ,这与 \pi N 的最优调度矛盾,因此, T^{\prime}\leq T(S,b_{\pi(1)}) ,从而有 T^{\prime}=T(S,b_{\pi(1)}) 。即流水作业调度问题具有最优子结构性质。

递归结构

由流水作业调度问题的最优子结构性质可知:

\begin{aligned} &T(N,0)=\min_{1\leq i\leq n}\{a_i+T(N-\{i\},b_i)\}\\ &T(S,t)=\min_{i\in S}\{a_i+T(S-\{i\},b_i+\max\{t-a_i,0\})\} \end{aligned}

当选定作业 i S 中第一个加工作业之后,在机器 M_2 上,作业 i 必须在 \max\{t,a_i\} 时间之后才能开始。即机器 M_2 上开始对 S-\{i\} 中的作业进行加工之前,所需要的等待时间为:

b_i+\max\{t,a_i\}-a_i=b_i+\max\{t-a_i,0\}

t>a_i ,则作业 i M_1 上加工完成(用时 a_i )之后,还需要等 t-a_i 个时间单位才能开始在 M_2 上加工;若 t\leq a_i ,则作业 i M_1 上加工完成之后,立即可以在 M_2 上加工,不需要等待。

作业调度的 Johnson 法则

\pi 是作业集 S 在机器 M_2 的等待时间为 t 时的任一最优调度。设 \pi(1)=i,\,\pi(2)=j ,则,

\begin{aligned} T(S,t)&= a_i+T(\overbrace{S-\{i\}}^{\color{blue}{S^{\prime}}},\overbrace{b_i+\max\{t-a_i,0\}}^{\color{blue}{t^{\prime}}})\\ &=a_i+T(S^{\prime},t^{\prime})\\ &=a_i+a_j+T({\color{blue}{S^{\prime}}}-\{j\},b_j+\max\{{\color{blue}{t^{\prime}}}-a_j,0\})\\ &=a_i+a_j+T(S-\{i,j\},\overbrace{b_j+\max\{b_i+\max\{t-a_i,0\}-a_j,0\}}^{\color{red}{t_{ij}}})\\ &=a_i+a_j+T(S-\{i,j\},{\color{red}{t_{ij}}}) \end{aligned}\\ \begin{aligned} t_{ij}&=b_j+\max\{b_i+\max\{t-a_i,0\}-a_j,0\}\\ &=b_j+\max\{(b_i-a_j)+\max\{t-a_i,0\},0\}\\ &=b_j+b_i-a_j+\max\{\max\{t-a_i,0\},a_j-b_i\}\\ &=b_j+b_i-a_j+\max\{t-a_i,a_j-b_i,0\}\\ &=b_j+b_i-a_j-a_i+\max\{t,a_i+a_j-b_i,a_i\} \end{aligned}

交换作业 i 和作业 j 的加工顺序,得到作业集 S 的另一调度 \pi^{\prime} ,所需的加工时间为,

T^{\prime}(S,t)=a_i+a_j+T(S-\{i,j\},t_{ji})\\ t_{ji}=b_j+b_i-a_j-a_i+\max\{t,a_i+a_j-b_j,a_j\}

i j 满足 Johnson 不等式 \min\{b_i,a_j\}\geq\min\{b_j,a_i\} 时, \max\{-b_i,-a_j\}\leq\max\{-b_j,-a_i\}

\begin{aligned} a_i+a_j+\max\{-b_i,-a_j\}&\leq a_i+a_j+\max\{-b_j,-a_i\}\\ \max\{a_i+a_j-b_i,a_i\}&\leq\max\{a_i+a_j-b_j,a_j\}\\ \forall\, t,\quad\max\{t,a_i+a_j-b_i,a_i\}&\leq\max\{t,a_i+a_j-b_j,a_j\}\\ t_{ij}&\leq t_{ji}\,\Leftrightarrow\, T(S,t)\leq T^{\prime}(S,t) \end{aligned}

当作业 i 和作业 j 不满足 Johnson 不等式时,交换它们的加工顺序后,作业 i j 满足 Johnson 不等式,且不增加加工时间。因此,对于流水作业调度问题,必存在最优调度 \pi ,使得作业 \pi(i) \pi(i+1) 满足 Johnson 不等式 \min\{b_{\pi(i)},a_{\pi(i+1)}\}\geq\min\{b_{\pi(i+1)},a_{\pi(i)}\},\,1\leq i\leq n-1 \pi 称为满足 Johnson 法则的调度;进一步可以证明,调度 \pi 满足 Johnson 法则当且仅当对任意 i<j 有,

\min\{b_{\pi(i)},a_{\pi(j)}\}\geq\min\{b_{\pi(j)},a_{\pi(i)}\}

由此可知,任意两个满足 Johnson 法则的调度具有相同的加工时间,即所有满足 Johnson 法则的调度均为最优调度。流水作业调度问题转化为求满足 Johnson 法则的调度问题。

算法描述

\min\{b_i,a_j\}\geq \min\{b_j,a_i\} ,即 \min\{a_i,a_j,b_i,b_j\} a_i b_j 时,Johnson 不等式成立,此时把 i 排在前, j 排在后的调度用时较少;反之,若 \min\{a_i,a_j,b_i,b_j\} a_j b_i 时,应 j 在前, i 在后。

\min\{a_1,a_2,\ldots,a_n,b_1,b_2,\dots,b_n\}=a_k 时,对于任何 i\ne k ,都有 \min\{b_k,a_i\}\geq \min\{b_i,a_k\} ,应将作业 k 安排在最前面,作为最优调度的第一个执行的作业。

\min\{a_1,a_2,\ldots,a_n,b_1,b_2,\dots,b_n\}=b_k 时,对于任何 i\ne k ,都有 \min\{b_i,a_k\}\geq \min\{b_k,a_i\} ,应将作业 k 安排在最后面,作为最优调度的最后一个执行的作业。

实例: n=4,\,(a_1,a_2,a_3,a_4)=(5,12,4,8),\,(b_1,b_2,b_3,b_4)=(6,2,14,7)

(a_1,a_2,a_3,a_4) (b_1,b_2,b_3,b_4) 合起来排序的结果为,

(2,4,5,6,7,8,12,14)=({\color{blue}{b_2}},{\color{red}{a_3}},{\color{red}{a_1}},b_1,{\color{blue}{b_4}},a_4,a_2,b_3)

最小数是 b_2 ,作业 2 应安排为最后一个作业, \pi(4)=2 ;次小数是 a_3 ,作业 3 应安排为第一个作业, \pi(1)=3 ;第 3 小数是 a_1 ,作业 1 应安排为第二个作业, \pi(2)=1 ;第 4 小数是 b_1 ,因为作业 1 已安排过,跳过;第 5 个数是 b_4 ,作业 4 应安排为倒数第二个作业, \pi(3)=4\,

流水作业调度问题的 Johnson 算法:

  1. N_1=\{i\,|\,a_i<b_i\},\,N_2=\{i\,|\,a_i\geq b_i\}
  2. N_1 中作业按 a_i 非递减排序,将 N_2 中作业按 b_i 的非递增排序;
  3. N_1 中作业接 N_2 中作业构成满足 Johnson 法则的最优调度。
\begin{aligned} n=4,\,(a_1,a_2,a_3,a_4)&=(5,12,4,8)\\(b_1,b_2,b_3,b_4)&=(6,2,14,7) \end{aligned}\\ \begin{aligned} N_1=\{1,3\}\quad\xrightarrow{\text{Sort by $ a_i $ non-decreasing}}\quad & N_1=\{3,1\}\\ N_2=\{2,4\}\quad\xrightarrow{\text{Sort by $ b_i $ non-increasing}}\quad & N_2=\{4,2\}\quad\, \Rightarrow\quad \pi=N_1+N_2=\{3,1,4,2\}. \end{aligned}
public static class Element implements Comparable {
    int key, index;
    boolean job;
    public Element(int k, int i, boolean j) {
        key = k; index = i; job = j;
    }
    public int compareTo(Object x) {
        int xkey = ((Element)x).key;
        if(key < xkey) return -1;
        if(key == xkey) return 0;
        return 1;
    }
}
public static int flowShop(int []a, int []b, int []c) {
    int n = a.length;
    Element []d = new Element[n];
    for(int i = 0; i < n; i++) {
        int key = (a[i] > b[i]) ? b[i] : a[i];
        boolean job = (a[i] <= b[i]);
        d[i] = new Element(key, i, job);
    }
    MergeSort.mergeSort(d);
    int j = 0, k = n - 1;
    for(int i = 0; i < n; i++) {
        if(d[i].job) c[j++] = d[i].index;
        else c[k--] = d[i].index;
    }
    j = a[c[0]]; k = j + b[c[0]];
    for(int i = 1; i < n; i++) {
        j += a[c[i]];
        k = (j < k) ? (k + b[c[i]]) : (j+b[c[i]]);
    }
    return k;
}

算法 flowShop 的主要计算时间是对作业集的排序,时间复杂度 O(n\log n) ,空间复杂度 O(n)

0 - 1 背包问题

给定 n 种物品和一背包,物品 i 的重量是 w_i ,价值为 v_i ,背包的容量为 C 。应如何选择装入背包的物品,使得装入背包中物品的总价值最大。形式化描述:给定 C>0,w_i>0,v_i>0,1\leq i\leq n ,要求找出 n 元 0 - 1 向量 (x_1,x_2,\ldots,x_n),\,x_i\in\{0,1\},1\leq i\leq n ,使得 \sum_{i=1}^{n}w_ix_i\leq C \sum_{i=1}^n v_ix_i 最大。

\left\{\begin{array}{l} \displaystyle\max \sum_{i=1}^{n}v_ix_i\\ \displaystyle\sum_{i=1}^{n}w_ix_i\leq C,\,x_i\in\{0,1\},1\leq i\leq n \end{array}\right.

最优子结构性质

(x_1,x_2,\ldots,x_n) 是所给 0 - 1 背包问题的一个最优解,则 (x_2,\ldots, x_n) 是下面问题的最优解,

\left\{ \begin{array}{l} \displaystyle\max \sum_{i=2}^{n}v_ix_i\\ \displaystyle\sum_{i=2}^{n} w_ix_i\leq C-w_1x_1,\, x_i\in\{0,1\},2\leq i\leq n \end{array} \right.

否则,设 (z_2,\ldots,z_n) 是最优解,则 (x_1,z_2,\ldots,z_n) 是原问题最优解且 (x_1,x_2,\ldots,x_n) 不是最优解,此为矛盾。所以 0 - 1 背包问题具有最优子结构性质。

递归关系

设所定的 0 - 1 背包问题的子问题

\left\{\begin{array}{l} \displaystyle\max \sum_{k=i}^{n}v_kx_k\\ \displaystyle\sum_{k=i}^{n}w_kx_k\leq j,\,x_k\in\{0,1\},i\leq k\leq n \end{array}\right.

的最优值为 m(i,j) ,表示背包容量为 j ,可选物品为 i, i+1, \ldots, n 时 0 - 1 背包问题的最优值。

m(n,j)=\left\{ \begin{array}{cl} v_n &j\geq w_n\\ 0& 0\leq j<w_n \end{array} \right.\\ m(i,j)=\left\{ \begin{array}{cl} \max\{m(i+1,j),m(i+1,j-w_i)+v_i\}& j\geq w_i\\ m(i+1,j)& 0\leq j<w_i \end{array} \right.

算法描述

w_i\,(1\leq i\leq n) 为整数时,用二维数组 m[][] 存储 m(i,j) 的相应值。

public static void knapsack(int []v, int []w, int c, int [][]m) {
    int n = v.length - 1;
    int jMax = Math.min(w[n] - 1, c);
    for(int j = 0; j <= jMax; j++) m[n][j] = 0;
    for(int j = w[n]; j <= c; j++) m[n][j] = v[n];
    for(int i = n - 1; i > 1; i--) {
        jMax = Math.min(w[i] - 1, c);
        for(int j = 0; j <= jMax; j++) m[i][j] = m[i+1][j];
        for(int j = w[i]; j <= c; j++)
            m[i][j] = Math.max(m[i+1][j], m[i+1][j - w[i]] + v[i]);
    }
    m[1][c] = m[2][c];
    if(c >= w[1]) m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]);
}
public static void traceback(int [][]m, int []w, int c, int []x) {
    int n = w.length - 1;
    for(int i = 1; i < n; i++)
        if(m[i][c] == m[i+1][c]) x[i] = 0;
        else x[i] = 1, c -= w[i];
    x[n] = (m[n][c] > 0) ? 1 : 0;
}

按算法 knapsack 计算后, m[1][c] 给出所要求的最优值, (x_1,x_2,\ldots,x_n) 是最优解。

**实例:**有编号 a,b,c,d,e 的五件物品,重量分别是 2,2,6,5,4 ,价值分别是 6,3,5,4,6 ,现在给你一个承重为 10 的背包,如何让背包里装入的物品具有最大的价值总和。

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline (\text{name},w,v)/j&1&2&3&4&5&{\color{green}{6}}&7&{\color{green}{8}}&9&{\color{green}{10}}\\ \hline \begin{array}{ccc}a&{\color{green}{2}}&6\end{array}&{\color{white}{0}}0&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}9&{\color{white}{0}}9&12&12&15&15&{\color{red}{15}}\\ \hline \begin{array}{ccc}b&{\color{green}{2}}&3\end{array}&{\color{white}{0}}0&{\color{white}{0}}3&{\color{white}{0}}3&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}9&{\color{white}{0}}9&{\color{white}{0}}{\color{red}{9}}&10&{\color{red}{11}}\\ \hline \begin{array}{ccc}c&6&5\end{array}&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}{\color{blue}{6}}&{\color{white}{0}}6&{\color{white}{0}}{\color{red}{6}}&10&11\\ \hline \begin{array}{ccc}d&5&4\end{array}&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}{\color{blue}{6}}&{\color{white}{0}}6&{\color{white}{0}}6&10&10\\ \hline \begin{array}{ccc}e&{\color{green}{4}}&6\end{array}&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}0&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}{\color{blue}{6}}&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}6&{\color{white}{0}}6\\ \hline \end{array}

knapsack 算法需要 O(nc) 计算时间,traceback 算法需要 O(n) 计算时间,算法假定物品重量 w_i 都是整数,表示背包容量的变量 j ,是以 1 为单位的,当背包容量较大时,算法需要的时间较多。

最优二叉搜索树

二叉搜索树:左子树上所有节点值均小于根节点值,右子树所有节点值均大于根节点值。

给定 n 个互异的关键字组成的序列 S=(x_1,x_2,\ldots,x_n) ,且关键字有序 (x_1<x_2<\cdots<x_n) ,现从这些关键字中构造一棵二叉搜索树。对于每个关键字 x_i ,一次搜索搜索到的概率为 b_i 。可能有一些搜索的值不在 S 内,因此还有 n+1 个虚拟键 d_0,d_1,\ldots,d_n ,他们代表不在 S 内的值。具体: d_0 代表所有小于 x_1 的值, d_n 代表所有大于 x_n 的值;对于 i=1,2,\ldots,n-1 d_i 代表所有位于 x_i x_{i+1} 之间的值。对于每个虚拟键,一次搜索对应于 d_i 的概率为 a_i 。查找成功与不成功的概率之和为 1

\sum_{i=0}^{n}a_i+\sum_{j=1}^{n}b_j=1,\,\,\, (a_i\geq 0,\,0\leq i\leq n,\,\,b_j\geq 0,\,1\leq j\leq n)

(a_0,b_1,a_1,\ldots,b_n,a_n) 为集合 S 的存取概率分布。二叉搜索树的期望代价为,

\begin{aligned} E(\text{search cost in $ T $ })&=\sum_{i=1}^n(\text{depth}_{T}(x_i)+1)b_i+\sum_{j=0}^{n}(\text{depth}_{T}(d_j)+1)a_j\\ &=1+\sum_{i=1}^{n}\text{depth}_{T}(x_i)b_i+\sum_{j=0}^{n}\text{depth}_{T}(d_j)a_j \end{aligned}

期望代价为在二叉搜索树 T 中搜索一次需要的平均比较次数,又称平均路长。最优二叉搜索树问题是对于有序集 S 及其概率分布 (a_0,b_1,a_1,\ldots,b_n,a_n) ,构造一棵具有最小平均路长的二叉搜索树。

最优子结构性质

二叉搜索树 T 的一棵含有结点 x_i,\ldots,x_j 和叶结点 (x_{i-1},x_i),\ldots,(x_j,x_{j+1}) 的子树可以看作是有序集 \{x_i,\ldots,x_j\} 关于全集合 (x_{i-1},\ldots,x_{j+1}) 的一棵二叉搜索树,其存取概率为条件概率,

\overline{b_k}=b_k/w_{ij}\, ,\,\,i\leq k\leq j\quad\quad\, \overline{a_h}= a_h/w_{ij}\, ,\,\,i-1\leq h\leq j

其中, w_{ij}=a_{i-1}+b_i+\cdots+b_j+a_j,\,\,1\leq i\leq j\leq n\,

T_{ij} 是有序集 \{x_i,\ldots,x_j\} 关于存取概率 \overline{a_{i-1}},\overline{b_i},\ldots,\overline{b_j},\overline{a_j} 的一棵最优二叉搜索树,其平均路长为 p_{ij} T_{ij} 的根结点存储元素 x_m ,其左右子树 T_l T_r 的平均路长分别为 p_l p_r ,由于 T_l T_r 中结点深度是他们在 T_{ij} 中的结点深度减 1 ,所以,

w_{i,j}p_{i,j}=w_{i,j}+w_{i,m-1}p_l+w_{m+1,j}p_r

由于 T_l 是关于集合 \{x_i,\ldots,x_{m-1}\} 的一棵二叉搜索树,故 p_l\leq p_{i,m-1} 。若 p_l>p_{i,m-1} ,则用 T_{i,m-1} 替换 T_l 可得到平均路长比 T_{ij} 更小的二叉搜素树,这与 T_{ij} 是最优二叉搜索树矛盾,故 T_l 是一棵最优二叉搜索树,同理, T_r 也是一棵最优二叉搜索树。因此,该问题具有最优子结构性质。

递归结构

最优二叉搜索树 T_{ij} 的平均路长为 p_{ij} ,则所求最优值为 p_{1,n}\, p_{ij} 递归式:

w_{i,j}p_{i,j}=w_{i,j}+\min_{i\leq k\leq j}\{w_{i,k-1}p_{i,k-1}+w_{k+1,j}p_{k+1,j}\}\quad\, i\leq j

初始时, p_{i,i-1}=0,\,1\leq i\leq n ;记 w_{i,j}p_{i,j} m(i,j) ,则 m(1,n)=w_{1,n}p_{1,n}=p_{1,n} 为最优值。

计算 m(i,j) 的递归式为:

m(i,j)=w_{i,j}+\min_{i\leq k\leq j}\{m(i,k-1)+m(k+1,j)\},\,\,\,\,\,\, 1\leq i\leq j\leq n\\ m(i,i-1)=a_{i-1},\,\, 1\leq i\leq n\quad\quad w_{i,j}=a_{i-1}+b_i+\cdots+b_j+a_j,\,\,1\leq i\leq j\leq n

**推导过程:**自顶向下的分析,对于最优二叉搜索树 T_{ij} ,设根结点为 x_k ,显然 \text{depth}_{T_{ij}}(x_k)=0

\begin{aligned} {\color{red}{\underbrace{m(i,j)}_{\Large\text{整树平均路长}}}}&={\color{red}{\min_{i\leq k\leq j}}} \left\{\begin{array}{c} \displaystyle{\color{blue}{\underbrace{b_k\times 1}_{\large\text{根}}}}+\underbrace{\sum_{l=i}^{k-1}(\text{depth}_{T_{ij}}(x_l){\color{blue}{+1}})b_l}_{\color{red}{\Large\text{左子树查找成功}}}+\underbrace{\sum_{l=i-1}^{k-1}(\text{depth}_{T_{ij}}(d_l){\color{blue}{+1}})a_l}_{\color{red}{\Large\text{左子树查找失败}}}\\ \displaystyle+\underbrace{\sum_{r=k+1}^{j}(\text{depth}_{T_{ij}}(x_r){\color{blue}{+1}})b_r}_{\color{red}{\Large\text{右子树查找成功}}}+\underbrace{\sum_{r=k}^{j}(\text{depth}_{T_{ij}}(d_r){\color{blue}{+1}})a_r}_{\color{red}{\Large\text{右子树查找失败}}} \end{array} \right\}\\ &={\color{red}{\min_{i\leq k\leq j}}} \left\{ \begin{array}{c} \displaystyle {\color{blue}{\underbrace{\sum_{g=i-1}^{j}a_g+\sum_{h=i}^j b_h}_{\Large\text{全部结点概率和}}}}+\underbrace{\sum_{l=i}^{k-1}\text{depth}_{T_{ij}}(x_l)b_l+\sum_{l=i-1}^{k-1}\text{depth}_{T_{ij}}(d_l)a_l}_{\color{red}{{\Large{\text{左子树平均 }}m(i,k-1)}}}\\ +\displaystyle\underbrace{\sum_{r=k+1}^{j}\text{depth}_{T_{ij}}(x_r)b_r+\sum_{r=k}^{j}\text{depth}_{T_{ij}}(d_r)a_r}_{\color{red}{{\Large{\text{右子树平均 }}m(k+1,j)}}} \end{array} \right\}\\ {\color{red}{m(i,j)}}&={\color{blue}{w_{i,j}}}+{\color{red}{\min_{i\leq k\leq j}}}\{m(i,k-1)+m(k+1,j)\},\,\,\,\,\,\, 1\leq i\leq j\leq n \end{aligned}

据此,可设计出解最优二叉搜索树问题的 OptimalBST 算法的 C++ 实现如下,

double b[6] = {0, 0.15, 0.1, 0.05, 0.1, 0.2};
double a[6] = {0.05, 0.1, 0.05, 0.05, 0.05, 0.1};
double m[10][10], w[10][10];
int s[10][10], n = 5, MAX = 1000000007;
void OptimalBST() {
    for (int i = 1; i <= n + 1; i++) {
        m[i][i - 1] = a[i - 1];
        w[i][i - 1] = a[i - 1];
    }
    for (int l = 1; l <= n; l++)
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = (double)MAX;
            w[i][j] = w[i][j - 1] + b[j] + a[j];
            for (int r = i; r <= j; r++) {
                double t = m[i][r - 1] + m[r + 1][j] + w[i][j];
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = r;
                }
            }
        }
}

算法 optimalBinarySearchTree 中用 s[i][j] 保存最优子树 T_{ij} 的根结点中元素。当 s[1][n]=k 时, x_k 为所求二叉搜索树的根结点元素,其左子树为 T_{1,k-1} ,因此 i=s[1][k-1] 表示 T_{1,k-1} 的根结点元素 x_i ,以此类推,可以在 O(n) 时间内构造出所求的最优二叉搜索树。

计算复杂性

算法的空间复杂度显然为 O(n^2) ,算法有三重循环,循环内复杂度 O(1) ,总时间复杂度为 O(n^3) ,主要计算量在于计算 \min_{i\leq k\leq j}\{m(i,k-1)+m(k+1,j)\} 。可由下式对算法做出改进。

\min_{i\leq k\leq j}\{m(i,k-1)+m(k+1,j)\}=\min_{s[i][j-1]\leq k\leq s[i+1][j]}\{m(i,k-1)+m(k+1,j)\}
void obst() {
    for (int i = 1; i <= n + 1; i++) {
        m[i][i - 1] = a[i - 1];
        w[i][i - 1] = a[i - 1];
    }
    for (int l = 1; l <= n; l++)
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            int i1 = s[i][j-1] > i ? s[i][j-1] : i;
            int j1 = s[i+1][j] > i ? s[i+1][j] : j;
            m[i][j] = (double)MAX;
            w[i][j] = w[i][j - 1] + b[j] + a[j];
            for (int r = i1; r <= j1; r++) {
                double t = m[i][r - 1] + m[r + 1][j] + w[i][j];
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = r;
                }
            }
        }
}

改进后的 obst 算法的计算时间为 O(n^2) ,所需空间为 O(n^2)

实例

5 个关键字的概率如下所示,构造最优二叉搜素树,计算最优期望搜索代价。

\begin{array}{|c|c|c|c|c|c|c|} \hline &&k_1&k_2&k_3&k_4&k_5\\ \hline i&0&1&2&3&4&5\\ \hline p_i&&0.15&0.10&0.05&0.10&0.20\\ \hline q_i&0.05&0.10&0.05&0.05&0.05&0.10\\ \hline \end{array}
  1. 初始值 m(i,i-1)=q_{i-1},\,w(i,i-1)=q_{i-1},\quad\,1\leq i\leq 6
m(1,0)=0.05,\,m(2,1)=0.10,\,m(3,2)=0.05,\,m(4,3)=0.05,\,m(5,4)=0.05,\,m(6,5)=0.10\\ w(1,0)=0.05,\,w(2,1)=0.10,\,w(3,2)=0.05,\,w(4,3)=0.05,\,w(5,4)=0.05,\,w(6,5)=0.10
  1. 构造只有 1 个内部结点的最优二叉搜索树。
\begin{aligned} w(1,1)&=w(1,0)+q_1+p_1=0.05+0.10+0.15=0.30\\ m(1,1)&=\min_{1\leq k\leq 1}\{m(1,0)+m(2,1)+w(1,1)\}=0.45,\,\,s(1,1)=1\\ w(2,2)&=w(2,1)+q_2+p_2=0.10+0.10+0.05=0.25\\ m(2,2)&=\min_{2\leq k\leq 2}\{m(2,1)+m(3,2)+w(2,2)\}=0.40,\,\,s(2,2)=2\quad\,\cdots \end{aligned}\\ w(3,3)=0.15,\,m(3,3)=0.25,\,s(3,3)=3;\\ w(4,4)=0.20,\,m(4,4)=0.30,\,s(4,4)=4;\\ w(5,5)=0.35,\,m(5,5)=0.50,\,s(5,5)=5.
  1. 构造有两个内部结点的最优二叉搜素树。
\begin{aligned} \end{aligned}\\ \begin{aligned} w(1,2)&=w(1,1)+q_2+p_2=0.30+0.05+0.10=0.45\\ m(1,2)&=\min_{1\leq k\leq 2}\left\{\begin{array}{c}m(1,0)+m(2,2)+w(1,2)\\m(1,1)+m(3,2)+w(1,2)\end{array}\right\}=\min_{1\leq k\leq 2}\left\{\begin{array}{c}0.90\\0.95\end{array}\right\}=0.90,\,\,s(1,2)=1\\ w(2,3)&=w(2,2)+q_3+p_3=0.25+0.05+0.05=0.35\\ m(2,3)&=\min_{2\leq k\leq 3}\left\{\begin{array}{c}m(2,1)+m(3,3)+w(2,3)\\m(2,2)+m(4,3)+w(2,3)\end{array}\right\}=\min_{2\leq k\leq 3}\left\{\begin{array}{c}0.70\\0.80\end{array}\right\}=0.70,\,\,s(2,3)=2\quad\, \cdots \end{aligned}\\ w(3,4)=0.30,\,m(3,4)=0.60,\,s(3,4)=4;\\ w(4,5)=0.50,\,m(4,5)=0.90,\,s(4,5)=5.
  1. 按此方法继续计算填表如下。
\begin{array}{|c|c|c|c|c|c|c|} \hline w(i,j)&0&1&2&3&4&5\\ \hline 1&0.05 &0.30& 0.45& 0.55& 0.70& 1.00\\ \hline 2&&0.10& 0.25& 0.35& 0.50 &0.80\\ \hline 3&&&0.05& 0.15& 0.30 &0.60\\ \hline 4&&&&0.05& 0.20& 0.50\\ \hline 5&&&&&0.05 &0.35\\ \hline 6&&&&&&0.10\\ \hline \end{array} \begin{array}{|c|c|c|c|c|c|c|} \hline m(i,j)&0&1&2&3&4&{\color{blue}{5}}\\ \hline {\color{blue}{1}}&0.05& 0.45 &0.90 &1.25& 1.75 &{\color{blue}{2.75}}\\ \hline 2&&0.10 &0.40 &0.70 &1.20& 2.00\\ \hline 3&&&0.05& 0.25& 0.60 &1.30\\ \hline 4&&&& 0.05& 0.30& 0.90\\ \hline 5&&&&&0.05& 0.50\\ \hline 6&&&&&&0.10\\ \hline \end{array}\\ \begin{array}{|c|c|c|c|c|c|} \hline s(i,j)&1&2&3&\color{red}{4}&\color{red}{5}\\ \hline \color{red}{1}&1& 1 &2&2& \color{red}{2} \\ \hline 2&&2 &2 &2 &4\\ \hline \color{red}{3}&&&3& \color{red}{4}& \color{red}{5} \\ \hline 4&&&& 4& 5\\ \hline 5&&&&&5\\ \hline \end{array}

最优期望搜索代价为 m(1,5)=2.75 ,由 s 数组构造出的最优二叉搜索树如下图。

另外,如果题目中只考察查找成功的情况的最优二叉搜索数,只需要考虑 p_i 即可,即只需要考虑关键字的概率分布,虚拟键的概率均假设为 0 即可。

第三章作业题

模拟矩阵连乘问题的动态规划算法

现有 5 个矩阵 A_1,A_2,\ldots,A_5 ,行列数序列为 (20,25,35,15,30,10) ,请给出矩阵连乘动态规划算法的最优值数组 m 和最优断开位置数组 s ,并写出最优计算次序。

  1. 首先, m(i,i)=0,\,\,1\leq i\leq 5\,
  2. 计算矩阵链长度为 1 的连乘积。
m(i,i+1)=\min_{i\leq k<i+1}\left\{m(i,i)+m(i+1,i+1)+p_{i-1}p_ip_{i+1}\right\}=p_{i-1}p_ip_{i+1},\,\,\,1\leq i\leq 4
  1. 计算矩阵链长度为 2 的连乘积。
\begin{aligned} m(i,i+2)&=\min_{i\leq k<i+2}\left\{\begin{array}{c}m(i,i)+m(i+1,i+2)+p_{i-1}p_ip_{i+2}\\ m(i,i+1)+m(i+2,i+2)+p_{i-1}p_{i+1}p_{i+2} \end{array}\right\}\\&=\min\left\{\begin{array}{c}m(i+1,i+2)+p_{i-1}p_ip_{i+2}\\ m(i,i+1)+p_{i-1}p_{i+1}p_{i+2} \end{array}\right\},\quad\, 1\leq i\leq 3 \end{aligned}
  1. 按此方法继续计算填表如下。
\begin{array}{|c|c|c|c|c|c|} \hline m(i,j)&1&2&3&4&{\color{blue}{5}}\\ \hline {\color{blue}{1}}&{\color{white}{00}}0{\color{white}{00}} &17500 &20625 &29625 &{\color{blue}{23500}}\\ \hline 2&&0&13125 &24375 &18500 \\ \hline 3&&&0 &15750 &9750\\ \hline 4&&&&0 &4500\\ \hline 5&&&&& 0\\ \hline \end{array}\quad \begin{array}{|c|c|c|c|c|c|} \hline s(i,j)&1&2&3&4&{\color{red}{5}}\\ \hline {\color{red}{1}}& & 1 &1& 3& {\color{red}{1}} \\ \hline {\color{red}{2}}&&&2 &3 &{\color{red}{2}} \\ \hline {\color{red}{3}}&&& &3 &{\color{red}{3}}\\ \hline 4&&&& &4\\ \hline 5&&&&&\\ \hline \end{array}

最小运算次数为 m(1,5)=23500 ,由 s 数组可以构造出最优计算次序为 (A_1(A_2(A_3(A_4A_5))))

习题 3-5 二维 0 - 1 背包问题

给定 n 种物品和一背包,物品 i 的重量是 w_i ,体积是 b_i ,价值为 v_i ,背包的容量为 C ,容积为 D 。问:应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品 i 只有两种选择,即装入背包或不装入背包。不能将物品 i 装入背包多次,也不能只装入部分的物品 i ,试设计一个解此问题的动态规划算法,并分析复杂性。

**解:**问题形式化描述为,给定 C>0,D>0,w_i>0,b_i>0,v_i>0,\,1\leq i\leq n ,要求找出 n 元 0 - 1 向量 (x_1,x_2,\ldots,x_n),\,x_i\in\{0,1\},\,\,1\leq i\leq n ,使得,

\max\sum_{i=1}^n v_ix_i\quad\text{s.t. }\left\{ \begin{array}{l} \displaystyle\sum_{i=1}^{n}w_ix_i\leq C\\ \displaystyle\sum_{i=1}^{n}b_ix_i\leq D\\ x_i\in\{0,1\},\,\,1\leq i\leq n \end{array} \right.

显然该问题具有最优子结构性质。设所给二维 0 - 1 背包问题的子问题

\max\sum_{t=i}^n v_tx_t\quad\text{s.t. }\left\{ \begin{array}{l} \displaystyle\sum_{t=i}^{n}w_tx_t\leq j\\ \displaystyle\sum_{t=i}^{n}b_tx_t\leq k\\ x_t\in\{0,1\},\,\,i\leq t\leq n \end{array} \right.

的最优值为 m(i,j,k) ,即表示背包容量为 j ,容积为 k ,可选择物品为 i,i+1,\ldots,n 时二维 0 - 1 背包问题的最优值。由二维 0 - 1 背包问题的最优子结构性质,建立递归式如下:

\begin{aligned} m(i,j,k)&=\left\{ \begin{array}{cl} \max\{m(i+1,j,k),m(i+1,j-w_i,k-b_i)+v_i\}& j\geq w_i\,\and\,k\geq b_i\\ m(i+1,j,k) & 0\leq j<w_i\,\or\,0\leq k<b_i \end{array} \right.\\ m(n,j,k)&=\left\{ \begin{array}{cl} v_n&j\geq w_n\,\and \,k\geq b_n\\ 0&0\leq j<w_n \,\or\, 0\leq k<b_n \end{array} \right. \end{aligned}

按此递归式计算出 m(1,C,D) 即为最优值。算法所需的计算时间为 O(nCD)

贪心算法

贪心算法的特性

贪心算法总是作出在当前看来最好的选择,即贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。利用了问题本身的一些特性,希望贪心算法得到的最终结果也是整体最优的。在某些情况,贪心算法不能得到整体最优,但其最终结果是最优解的近似。

贪心算法的基本要素

所求问题的整体最优解可以通过一系列局部最优的选择来到达。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心算法通常自顶向下进行,对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

  • 首先考察问题的一个整体最优解,并证明可修改此最优解,使其以贪心选择开始。
  • 证明在做了贪心选择之后,原问题简化为规模较小的类似子问题,可继续使用贪心选择。这一步的关键是利用其最优子结构性质。
  • 用数学归纳法可证明,经过一系列贪心选择可以得到整体最优解。

满足贪心选择性质必满足最优子结构性质;但满足最优子结构性质不一定满足贪心选择性质。

例如 0 - 1 背包问题和背包问题,说明了贪心算法和动态规划算法的区别。背包问题,与 0 - 1 背包问题类似,所不同的是在选择物品 i 装入背包时,可以选择物品 i 的一部分装入, 1\leq i\leq n\, 。形式化的描述上,与 0 - 1 背包唯一不同的地方就在于 x_i 的范围是 0\leq x_i\leq 1,\,1\leq i\leq n\, 。这两类问题都具有最优子结构性质,但背包问题可以用贪心算法求解,0 - 1 背包不能。策略为,

  • 首先计算每种物品单位重量的价值 v_i/w_i ,然后按贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
  • 若将这种物品全部装入背包后,背包内的物品总重量未超过 C ,则选择单位重量价值次高的物品并尽可能多地装入背包。以此类推,直到背包装满。具体算法如下:
public static class Element implements Comparable {
    float w, v;
    int i;
    public Element(int ww, int vv, int ii) {
        w = ww; v = vv; i = ii;
    }
    public int compareTo(Object x) {
        float xval = ((Element)x).v / ((Element)x).w;
        if(v / w < xval) return 1;
        if(v / w == xval) return 0;
        return -1;
    }
}
public static float knapsack(float c, float []w, float []v, float []x) {
    int n = v.length;
    Element[] d = new Element[n];
    for(int i = 0; i < n; i++) d[i] = new Element(w[i], v[i], i);
    MergeSort.mergeSort(d);
    float opt = 0;
    int i;
    for(i = 0; i < n; ++i) x[i] = 0;
    for(i = 0; i < n; ++i) {
        if(d[i].w > c) break;
        x[d[i].i] = 1;
        opt += d[i].v;
        c -= d[i].w;
    }
    if(i < n) {
        x[d[i].i] = c / d[i].w;
        opt += x[d[i].i] * d[i].v;
    }
    return opt;
}

算法 knapsack 的主要计算时间在于排序,因此算法的计算时间上界为 O(n\log n)

活动安排问题

n 个活动的集合 E=\{1,2,\ldots,n\} ,其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 s_i 和结束时间 f_i ,且 s_i<f_i 。如果选择了活动 i ,则它在半开时间区间 [s_i,f_i) 内占用资源。若区间 [s_i,f_i) [s_j,f_j) 不相交,称活动 i 和活动 j 相容,即 s_i\geq f_j s_j\geq f_i 时,活动 i 和活动 j 相容。求 n 个活动的最大相容集合。

各活动的起始时间和结束时间存储于数组 s f 中且按结束时间非递减排列。如果所给出的活动未按此序排列,可以先用 O(n\log n) 的时间重排。贪心算法 greedySelector 算法如下。

public static int greedySelector(int []s, int []f, boolean []a) {
    int n = s.length - 1;
    a[1] = true;
    int j = 1, cnt = 1;
    for(int i = 2; i <= n; i++)
        if(s[i] >= f[j]) {
            a[i] = true;
            j = i;
            cnt++;
        } else a[i] = false;
    return cnt;
}

输入的活动以其完成时间非递减排序,所以算法 greedySelector 每次总是选择具有最早完成时间的相容活动加入集合中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。算法计算时间 O(n)

可以用数学归纳法证明活动安排问题的贪心选择性质和最优子结构性质。

E=\{1,2,\ldots, n\} 是所给的活动集合,且按活动结束时间的非递减排列,因此活动 1 具有最早完成时间。证明此问题有一个最优解以贪心选择开始,即最优解中包含活动 1 ,设 A\subseteq E 是此问题的一个最优解,且 A 中的活动也按结束时间的非递减排列, A 中的第一个活动为活动 k\,

  • k=1 ,则 A 即为以贪心选择开始的最优解。
  • k>1 ,则设 B=\{A-\{k\}\}\cup\{1\} ,由于 f_1\leq f_k ,且 A 中的活动是相容的,因此 B 中的活动也是相容的,由于 B 中的活动个数与 A 中活动个数相同,且 A 是最优的,则 B 也最优。

综上,总是存在以贪心选择开始的最优解,即问题的贪心选择性质。选择了活动 1 后,问题简化为对 E 中所有与活动 1 相容的活动进行安排的子问题(最优子结构性质)。

A 是原问题的最优解,则 A^{\prime}=A-\{1\} E^{\prime}=\{i\in E\,|\,s_i\geq f_1\} 的最优解。否则,如果存在 E^{\prime} 的一个解 B^{\prime} ,包含比 A^{\prime} 更多的活动,则将活动 1 加入 B^{\prime} 中产生一个解 B ,包含比 A 更多的活动,矛盾。因此,该问题具有最优子结构性质。greedySelector 算法最终产生原问题整体最优解。

最优装载个数问题

n 个集装箱要装上一艘载重量为 c 的轮船,其中集装箱 i 的重量为 w_i ,要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。形式化描述为:

\max\sum_{i=1}^{n}x_i\quad\, \text{s.t. }\,\sum_{i=1}^{n}w_ix_i\leq c\,,\,\,x_i\in\{0,1\},\,1\leq i\leq n

其中, x_i=0 表示不装入集装箱 i x_i=1 表示装入集装箱 i\,

算法描述

最优装载问题是 0 - 1 背包问题的特例,其中 v_i=1 。可以使用贪心算法求解,采用重量最轻者先装的贪心选择策略,可产生最优装载个数的最优解。具体算法如下:

public static class Element implements Comparable {
    float w;
    int i;
    public Element(float ww, int ii) {
        w = ww; i = ii;
    }
    public int compareTo(Object x) {
        float xw = ((Element)x).w;
        if(w < xw) return -1;
        if(w == xw) return 0;
        return 1;
    }
}
public static float loading(float c, float []w, float []x) {
    int n = w.length;
    Element[] d = new Element[n];
    for(int i = 0; i < n; i++) d[i] = new Element(w[i], i);
    MergeSort.mergeSort(d);
    float opt = 0;
    for(int i = 0; i < n; i++) x[i] = 0;
    for(int i = 0; i < n && d[i].w <= c; i++) {
        x[d[i].i] = 1;
        opt += d[i].w;
        c -= d[i].w
    }
    return opt;
}

算法 loading 的计算量在于将集装箱按重量从小到大排序,计算时间为 O(n\log n)

贪心选择性质

设集装箱按重量从小到大排序, (x_1,x_2,\ldots,x_n) 是最优装载个数问题的一个最优解。

k=\min\{i\,|\,x_i=1,\,1\leq i\leq n\} ,如果问题有解,则 1\leq k\leq n\,

  • k=1 (x_1,x_2,\ldots,x_n) 是满足贪心选择性质的最优解。
  • k>1 ,取 y_1=1,y_k=0,\ldots,y_i=x_i,\,1<i\leq n,\,i\neq k ,则有,
\sum_{i=1}^n w_iy_i=w_1-w_k+\sum_{i=1}^n w_ix_i\leq \sum_{i=1}^{n} w_ix_i\leq c

所以 (y_1,y_2,\ldots,y_n) 是所给最优装载个数问题的可行解。又由 \sum_{i=1}^n y_i=\sum_{i=1}^n x_i 可知, y 也是一组最优解,所以最优装载个数问题满足贪心选择性质。

最优子结构性质

(x_1,x_2,\ldots,x_n) 是最优装载个数问题满足贪心选择性质的最优解,则 x_1=1 ,且 (x_2,\ldots,x_n) 是轮船载重量为 c-w_1 ,待装船集装箱为 \{2,3,\ldots,n\} 是相应的最优装载个数问题的最优解。

哈夫曼编码

哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0, 1 串表示各字符的最优表示方式。

前缀码

对每一个字符规定一个 0, 1 串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀。用二叉树作为前缀码的数据结构,树叶代表给定的字符,每个字符的前缀码表示从树根到代表该字符的树叶的一条路径。表示最优前缀码的二叉树中任一结点都有两个子结点。若 C 表示编码字符集,则表示其最优前缀码的二叉树恰有 |C| 个叶子,有 |C|-1 个内部结点。

给定编码字符集 C 及其概率分布 f ,即 C 中任一字符 c 以频率 f(c) 在数据文件中出现。 C 的一个前缀码编码方案对应于一棵二叉树 T 。字符 c 在树 T 中的深度记为 d_{T}(c) ,即 c 的前缀码长。这种编码方案的平均码长定义为: B(T)=\sum_{c\in C}f(c)d_{T}(c) ,平均码长最小的编码方案称为 C 的最优前缀码。

构造哈夫曼编码

哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T 。算法从 |C| 个叶结点开始,执行 |C|-1 次“合并”运算后产生最终所要求的树 T 。算法 huffmanTree 中,编码字符集中每一字符 c 的频率是 f(c) 。以 f 为键值的优先队列 Q 用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树,两棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的两棵树的频率之和,并将新树插入优先队列 Q 。经过 n-1 次的合并后,优先队列中只剩下一棵树,即所要求的树 T

public static class Huffman implements Comparable {
    Bintree tree;
    float weight;
    public Huffman(Bintree tt, float ww) {
        tree = tt;
        weight = ww;
    }
    public int compareTo(Object x) {
        float xw = ((Huffman)x).weight;
        if(weight < xw) return -1;
        if(weight == xw) return 0;
        return 1;
    }
}
public static Bintree huffmanTree(float []f) {
    int n = f.length;		// 生成单结点树
    Huffman[] w = new Huffman[n+1];
    Bintree zero = new Bintree();
    for(int i = 0; i < n; i++) {
        Bintree x = new Bintree();
        x.maketree(new MyInteger(i), zero, zero);
        w[i+1] = new Huffman(x, f[i]);
    }
    MinHeap H = new MinHeap();	// 建优先队列
    H.initialize(w, n);
    for(int i = 1; i <= n; i++) {	// 反复合并最小频率树
        Huffman x = (Huffman) H.removeMin();
        Huffman y = (Huffman) H.removeMin();
        Bintree z = new Bintree();
        z.maketree(null, x.tree, y.tree);
        Huffman t = new Huffman(z, x.weight + y.weight);
        H.put(t);
    }
    return ((Huffman)H.removeMin()).tree;
}

算法 huffmanTree 用最小堆实现优先队列 Q ,初始化优先队列需要 O(n) 的计算时间,由于最小堆的 removeMin 和 put 运算均需 O(\log n) 时间, n-1 次的合并总共需要 O(n\log n) 计算时间。

**实例:**构造编码字符集 \left\{\boxed{\text{a}:45},\boxed{\text{b}:13},\boxed{\text{c}:12},\boxed{\text{d}:16},\boxed{\text{e}:9},\boxed{\text{f}:5}\right\} 的哈夫曼树。

由根结点到叶子结点的路径编码得到字符的哈夫曼编码:

\begin{array}{|c|c|c|c|c|c|} \hline \text{character}&\text{a}&\text{b}&\text{c}&\text{d}&\text{e}&\text{f}\\ \hline f(c)&45&13&12&16&9&5\\ \hline \text{Huffman Code}&0&101&100&111&1101&1100\\ \hline \end{array}

另外,对于定长编码,总码长 = 编码位数 * 字符长度,其中定长编码的编码位数可以通过编码种数构造一棵满二叉树,满二叉树的层数就是编码的位数。哈夫曼编码的总码长相当于平均码长:

\sum_{c\in C}f(c)d_{T}(c)=\sum_{c\in C}f(c)\text{HuffmanCodeLength}(c)

文件的压缩率 = (定长编码的总码长 - 哈夫曼编码的总码长) / 定长编码的总码长。

贪心选择性质

C 是编码字符集,字符 c 的频率为 f(c) x y C 中具有最小频率的两个字符,则存在 C 的最优前缀码使 x,y 具有相同码长且仅最后一位编码不同。

**证明:**设二叉树 T C 的任意一个最优前缀码,只需要证明对 T 作适当修改后得到新的二叉树 T^{\prime\prime} ,使得新树中 x,y 是最深叶子且为兄弟,同时 T^{\prime\prime} 表示的前缀码也是 C 的一个最优前缀码。

b,c T 中最深叶子且为兄弟,设 f(b)\leq f(c),\,f(x)\leq f(y) ,则由于 x y C 中具有最小频率的两个字符, f(x)\leq f(b),\,f(y)\leq f(c) 。在 T 中交换 b,x 的位置得到 T^{\prime} ,继续在 T^{\prime} 交换 c,y 的位置得到 T^{\prime\prime} 。则树 T T^{\prime} 的前缀码的平均码长之差为:

\begin{aligned} B(T)-B(T^{\prime})&=\sum_{c\in C}f(d)d_{T}(c)-\sum_{c\in C}f(d)d_{T^{\prime}}(c)\\ &=f(x)d_T(x)+f(b)d_T(b)-f(x)d_{T^{\prime}}(x)-f(b)d_{T^{\prime}}(b)\\ &=f(x)d_T(x)+f(b)d_T(b)-f(x)d_{T}(b)-f(b)d_{T}(x)\\ &=(f(b)-f(x))(d_T(b)-d_T(x))\geq 0 \end{aligned}

同样,可以证明 B(T^{\prime})-B(T^{\prime\prime})\geq 0 ,因此有 B(T^{\prime\prime})\leq B(T^{\prime})\leq B(T) ,又由于 T 所表示的前缀码是最优的,即 B(T)\leq B(T^{\prime\prime}) ,所以 B(T)=B(T^{\prime\prime}) ,即 T^{\prime\prime} 表示的前缀码也是最优的,且 x y 具有相同码长且仅最后一位编码不同。

最优子结构性质

T 是表示 C 的一个最优前缀码的完全二叉树, C 中字符 c 的频率为 f(c) 。设 x,y T 中两个叶结点且为兄弟, z 是二者父结点。若将 z 看成具有概率 f(x)+f(y) 的字符,则树 T^{\prime}=T-\{x,y\} 表示字符集 C^{\prime}=\{C-\{x,y\}\}\cup \{z\} 的一个最优前缀码。

**证明:**首先 T 的平均码长 B(T) 可用 T^{\prime} 的平均码长 B(T^{\prime}) 表示。事实上,

对任意 c\in C-\{x,y\} d_T(c)=d_{T^{\prime}}(c) ,故 f(c)d_T(c)=f(c)d_{T^{\prime}}(c)

另一方面, d_T(x)=d_T(y)=d_{T^{\prime}}(z)+1 ,故

\begin{aligned} f(x)d_T(x)+f(y)d_T(y)&=(f(x)+f(y))(d_{T^{\prime}}(z)+1)\\ &=f(x)+f(y)+f(z)d_{T^{\prime}}(z) \end{aligned}\\ \begin{aligned} B(T)&=\sum_{c\notin \{x,y\}}f(c)d_T(c)+f(x)d_T(x)+f(y)d_T(y)\\ &={\color{red}{\sum_{c\notin \{x,y\}}f(c)d_T(c)}}+f(x)+f(y)+{\color{red}{f(z)d_{T^{\prime}}(z)}}\\ &={\color{red}{B(T^{\prime})}}+f(x)+f(y) \end{aligned}

T^{\prime} 表示的 C^{\prime} 的前缀码不是最优的,则存在 T^{\prime\prime} 表示的 C^{\prime} 的最优前缀码使得 B(T^{\prime\prime})<B(T^{\prime}) z 被看作 C^{\prime} 中的一个字符,故 z 作为 T^{\prime\prime} 中的一个叶子,若将 x,y 加入 T^{\prime\prime} 中,作为 z 的子结点,得到表示 C 的前缀码的二叉树 T^{\prime\prime\prime} ,则有,

B(T^{\prime\prime\prime})=B(T^{\prime\prime})+f(x)+f(y)<B(T^{\prime})+f(x)+f(y)=B(T)

T 的最优性矛盾, T^{\prime} 表示的 C^{\prime} 的前缀码是最优的。

单源最短路径

给定带权有向图 G=(V,E) ,每条边的权是非负实数。给定 V 中的一个顶点,称为源。要求计算从源到所有其他各顶点的最短路长度。这里路的长度指路上各边权之和。单源最短路问题的贪心选择策略:选择从源 v 出发目前最短的路径所到达的顶点,这就是目前的局部最优解。

算法基本思想

Dijkstra 算法是解单源最短路问题的贪心算法。基本思想是:设置顶点集合 S 并不断作贪心选择扩充这个集合。一个顶点属于 S 当且仅当从源到该顶点的最短路径长度已知。

初始时, S 中仅含有源。设 u G 的某一个顶点,把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径,并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S 中取出具有最短特殊路长度的顶点 u ,将 u 添加到 S 中,同时对数组 dist 作必要的修改。当 S 包含了 V 中所有顶点时,dist 数组就记录了从源到所有其他顶点之间的最短路径长度。

Dijkstra 算法可描述为,输入的带权有向图是 G=(V,E),\,V=\{1,2,\ldots,n\} ,顶点 v 是源, a 是一个二维数组, a[i][j] 表示边 (i,j) 的权。当 (i,j)\notin E 时, a[i][j] 是一个大数。 \text{dist}[i] 表示当前从源到顶点 i 的最短特殊路径长度。具体算法实现如下:

public static void dijkstra(int v, float [][]a, float []dist, int []prev) {
    int n = dist.length - 1;
    if(v < 1 || v > n) return;
    boolean[] s = new boolean[n+1];
    for(int i = 1; i <= n; i++) {
        dist[i] = a[v][i];
        s[i] = false;
        if(dist[i] == Float.MAX_VALUE) prev[i] = 0;
        else prev[i] = v;
    }
    dist[v] = 0; s[v] = true;
    for(int i = 1; i < n; i++) {
        float temp = Float.MAX_VALUE;
        int u = v;
        for(int j = 1; j <= n; j++)
            if((!s[j]) && (dist[j] < temp)) {
                u = i;
                temp = dist[j];
            }
        s[u] = true;
        for(int j = 1; j <= n; j++)
            if((!s[j]) && (a[u][j] < Float.MAX_VALUE)) {
                float newdist = dist[u] + a[u][j];
                if(newdist < dist[j]) {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
    }
}

对于上图所示的有向图,应用 Dijkstra 算法计算从源顶点 1 到其他顶点间最短路径的过程:

\begin{array}{|c|c|c|c|c|c|c|} \hline i&S&u&\text{dist}[2]/\text{prev}[2]&\text{dist}[3]/\text{prev}[3]&\text{dist}[4]/\text{prev}[4]&\text{dist}[5]/\text{prev}[5]\\ \hline -&\{1\}&-&10/1&\infty/0&30/1&100/1\\ \hline 1&\{1,2\}&2&&60/2&&\\ \hline 2&\{1,2,4\}&4&&50/4&&90/4\\ \hline 3&\{1,2,4,3\}&3&&&&60/3\\ \hline 4&\{1,2,4,3,5\}&5&\color{red}{10/1}&\color{red}{50/4}&\color{red}{30/1}&\color{red}{60/3}\\ \hline \end{array}

数组 prev 记录了最短路径信息。 \text{prev}[i] 记录了从源 v 到顶点 i 的最短路径上的前一个顶点,初始时, \text{prev}[i]=v ,更新最短路长度时,只要 \text{dist}[u]+a[u][j]<\text{dist}[j] 时, \text{prev}[j]=u\,

public static void ShortestPath(int v, itn dest, int []prev) {
    int i = dest;
    while(i != v) {
        System.out.println(i);
        i = prev[i];
    }
    System.out.println(v);
}

上述方法打印了从源 v 到顶点 dest 的最短路径(由后向前)。

贪心选择性质

Dijkstra 算法中所做的贪心选择是:若 u V-S 中具有最短特殊路径的顶点,就将 u 选入 S ,并确定了从源到 u 的最短路径长度 \text{dist}[u] ,即下一条最短路径是中间只经过 S 中顶点而最后到达 u 的路径。从源到 u 没有更短的其他路径。若有,则这条路径一定经过 V-S 中的其他顶点,设这条路初次走出 S 之外到达的顶点为为 x\in V-S ,然后徘徊于 S 内外若干次,最后离开 S 到达 u

在这条路径上,记 d(i,j) 为顶点 i 到顶点 j 的路长,那么,

\begin{aligned} \text{dist}[x]&\leq d(v,x)\\ d(v,x)+d(x,u)&=d(v,u)<\text{dist}[u] \end{aligned}

利用边权的非负性,可知 d(x,u)\geq 0 ,从而 \text{dist}[x]<\text{dist}[u] ,与 u 的选取矛盾。

最优子结构性质与计算复杂度

算法中确定的 \text{dist}[u] 确实是当前从源到顶点 u 的最短特殊路径。因此探讨添加 u S 中后, \text{dist}[u] 值的变化。将添加 u 之前的 S 称为旧的 S ,添加了 u 之后,可能出现一条到顶点 i 的新的特殊路。如果这条新特殊路是先经过旧的 S 到达顶点 u ,然后从 u 经一条边直接到达顶点 i ,则这种路的最短的长度是 \text{dist}[u]+a[u][i] ,这时,如果 \text{dist}[u]+a[u][i]<\text{dist}[i] ,则算法中用 \text{dist}[u]+a[u][i] 作为 \text{dist}[i] 的新值。如果这条新特殊路经过旧 S 到达 u 后,回到旧 S 中某个顶点 x ,最后到达顶点 i

那么由于 x 在旧的 S 中,因此 x u 先加入 S ,故图中从源到 x 的路的长度比从源到 u ,再从 u x 的路的长度小。于是当前 \text{dist}[i] 的值小于从源经 x i 的路的长度,也小于图中从源经 u x ,最后到达 i 的路的长度。因此,在算法中不必考虑这种路。因此,不论算法中 \text{dist}[u] 的值是否有变化,它总是关于当前顶点集 S 的到顶点 u 的最短特殊路径长度,该问题具有最优子结构性质。对于具有 n 个顶点和 e 条边的带权有向图,如果用带权邻接矩阵表示图,则计算时间为 O(n^2)

最小生成树

G=(V,E) 是无向连通带权图, E 中每条边 (v,w) 的权为 c[v][w] 。如果 G 的子图 G^{\prime} 是一棵包含 G 的所有顶点的树,则称 G^{\prime} G 的生成树。生成树上各边权的总和称为该生成树的耗费。在 G 的所有生成树中,耗费最小的生成树称为 G 的最小生成树。最小生成树在实际中具有广泛的应用。例如,在设计通信网络时,用图的顶点表示城市,用边 (v,w) 的权 c[v][w] 表示建立城市 v 和城市 w 之间的通信线路所需的费用,则最小生成树就给出了建立通信网络的最经济的方案。

最小生成树性质

G=(V,E) 是连通带权图, U V 的真子集。如果 (u,v)\in E ,且 u\in U,\,v\in V-U ,在所有这样的边中, (u,v) 的权 c[u][v] 最小,则一定存在 G 的一棵最小生成树,以 (u,v) 为其中一条边。

**证明:**假设 G 中的任何一棵最小生成树都不包含边 (u,v)

  • 将边 (u,v) 添加到 G 的一棵最小生成树 T 上,将产生含有边 (u,v) 的圈,并且在这个圈上有一条不同于 (u,v) 的边 (u^{\prime},v^{\prime}) ,使得 u^{\prime}\in U,\,v^{\prime}\in V-U

  • 将边 (u^{\prime},v^{\prime}) 删去,得到 G 的另一棵生成树 T^{\prime} 。由于 c[u][v]\leq c[u^{\prime}][v^{\prime}] ,所以 T^{\prime} 的耗费 \leq T 的耗费,于是 T^{\prime} 是一棵含有边 (u,v) 的最小生成树,这与假设矛盾。

Prim 算法

基本思想:在保证连通的前提下,依次选出权重较小的 n-1 条边。

  • G=(V,W) 为无向连通带权图,令 V=\{1,2,\ldots,n\}
  • 设置点集合 S 和边集合 T ,初始化 S=\{1\},\,T=\varnothing
  • 贪心策略:如果 V-S 中的顶点 j S 中的某个点 i 连接,且 (i,j) E 中的权重最小的边,于是就选择 j ,并将 j 加入 S (i,j) 加入 T 中。
  • 重复执行贪心策略,直至 V-S 为空为止。

在上述 Prim 算法中,还应当考虑如何有效地找出满足条件 i\in S,\, j\in V-S ,且权 c[i][j] 最小的边 (i,j) ,实现这个目的的较简单的办法是设置两个数组 closest 和 lowcost。对于每一个 V-S 中的 j \text{closest}[j] j S 中的邻接顶点,它与 j S 中的其他邻接顶点 k 相比较有:

c[j][\text{closest}[j]]\leq c[j][k],\quad\,\text{lowcost}[j]=c[j][\text{closest}[j]]

算法执行过程中,先找出 V-S 中使 lowcost 值最小的顶点 j ,然后选取边 (j,\text{closest}[j]) ,最后将 j 添加到 S 中,并对 closest 和 lowcost 作必要的修改。

public static void prim(int n, float [][]c) {
    float[] lowcost = new float[n+1];
    int[] closest = new int[n+1];
    boolean[] s = new boolean[n+1];
    s[1] = true;
    for(int i = 2; i <= n; i++) {
        lowcost[i] = c[1][i];
        closest[i] = 1;
        s[i] = false;
    }
    for(int i = 1; i < n; i++) {
        float min = Float.MAX_VALUE;
        int j = 1;
        for(int k = 2; k <= n; k++)
            if((lowcost[k] < min) && (!s[k])) {
                min = lowcost[k];
                j = k;
            }
        System.out.println(j + ", " + closest[j]);
        s[j] = true;
        for(int k = 2; k <= n; k++)
            if((c[j][k] < lowcost[k]) && (!s[k])) {
                lowcost[k] = c[j][k];
                closest[k] = j;
            }
    }
}

显然,prim 算法所需的计算时间为 O(n^2) 。实例如下图。

Kruskal 算法

基本思想:在保证无回路的前提下依次选择权重较小的 n-1 条边。

  • G=(V,W) 为无向连通带权图, V=\{1,2,\ldots,n\} ,将 n 个点看成 n 个孤立连通分支。

  • 将所有边权按权从小到大排序。

  • 然后从第一条边开始,依边权递增的顺序查看每一条边;当查看到第 k 条边 (v,w) 时,如果端点 v w 分别是当前两个不同连通分支 T_1 T_2 中的顶点时,就用边 (v,w) T_1 T_2 连接成一个连通分支,然后继续查看第 k+1 条边;如果端点 v w 在当前的同一个连通分支中,就直接再查看下一条边,一直进行到只剩下一个连通分支时为止。

关于集合的一些基本运算可用于实现 Kruskal 算法。Kruskal 算法中按权的递增顺序查看等价于对优先队列执行 removeMin 运算,可以用堆实现优先队列。另外,Kruskal 算法中,还要对一个由连通分支组成的集合不断进行修改,将这个集合记为 U ,则需要以下集合的基本运算。

  • \text{union}(a,b) :将 U 中两个连通分支 a b 连接起来,得到的结果称 A B\,
  • \text{find}(v) :返回 U 中包含顶点 v 的连通分支,用于确定某条边两个端点所属的连通分支。

这些基本运算是抽象数据类型并查集 UnionFind 所支持的基本运算。具体算法如下。

public static class EdgeNode implements Comparable {
    float weight;
    int u, v;
    EdgeNode(int uu, int vv, float ww) {
        u = uu; v = vv; weight = ww;
    }
    public int compareTo(Object x) {
        float xw = ((EdgeNode)x).weight;
        if(weight < xw) return -1;
        if(weight == xw) return 0;
        return 1;
    }
}
public static boolean kruskal(int n, int e, EdgeNode []E, EdgeNode []t) {
    MinHeap H = new MinHeap(1);
    H.initialize(E, e);
    FastUnionFind U = new FastUnionFind(n);
    int k = 0;
    while(e > 0 && k < n - 1) {
        EdgeNode x = (EdgeNode)H.removeMin();
        e--;
        int a = U.find(x.u);
        int b = U.find(x.v);
        if(a != b) {
            t[k++] = x;
            U.union(a, b);
        }
    }
    return (k == n - 1);
}

设输入的连通带权图有 e 条边,则将这些边依其权组成优先队列需要 O(e) 时间。一次 removeMin 运算需要 O(\log e) 时间,总共进行 e 次。因此 Kruskal 算法所需计算时间 O(e\log e) 。当 e=\Omega(n^2) 时,效率比 Prim 算法差,当 e=O(n^2) 时,比 Prim 算法好很多。实例如下。

第四章作业题

习题 4-2 背包问题的贪心选择性质

证明背包问题具有贪心选择性质。

背包问题可描述为:给定 W>0,\,w_i>0,\,v_i>0,\,1\leq i\leq n

要求找出一个 n 元向量 (x_1,x_2,\ldots,x_n),\,1\leq x_i\leq 1,\,1\leq i\leq n ,使得,

\max\sum_{i=1}^{n}v_ix_i\quad\, \, \text{s.t. }\,\sum_{i=1}^n w_ix_i\leq W

其贪心选择性质可描述为:若 w_i/x_i\leq v_{i+1}/w_{i+1},\,1\leq i< n ,则存在背包问题的一个最优解,

(x_1,x_2,\ldots,x_n)\quad\, \, \text{s.t. }\, x_1=\min\{W/w_1,1\}

可以分以下三种情形证明背包问题的贪心选择性质。

  • \sum_{i=1}^n w_i\leq W 。此时唯一的最优解为 (1,1,\ldots, 1)
  • \sum_{i=1}^n w_i>W ,且 v_1/w_1=v_i/w_i,\,2\leq i\leq n\,
  • \sum_{i=1}^n w_i>W

习题 4-3 特殊的 0-1 背包问题

若在 0-1 背包问题中,各物品依重量递增排列时,其价值恰好依递减序排列。对这个特殊的 0-1 背包问题,设计一个有效算法找出最优解,并说明算法的正确性。

W>0,\,w_i>0,\,v_i>0,\,1\leq i\leq n ,不妨设 0<w_1\leq w_2\leq\cdots\leq w_n ,由题意可知,

v_1\geq v_2\geq \cdots\geq v_n>0,\quad\,\, v_i/w_i\geq v_{i+1}/w_{i+1},\,1\leq i< n
  • w_1> W 时,唯一可行解 (0,0,\ldots,0)
  • w_1\leq W 时,存在一个最优解 S\subseteq\{1,2,\ldots,n\} 使得 1\in S

S\subseteq\{1,2,\ldots, n\} 是一个最优解,且 1\notin S 。对任意 i\in S ,取 S_i=S\cup\{1\}-\{i\} 也是最优解。

习题 4-6 Fibonacci 序列的 Huffman 编码

字符 a~h 出现的频率恰好是前 8 个 Fibonacci 数,它们的哈夫曼编码是什么?将结果推广到 n 个字符的频率恰好是前 n 个 Fibonacci 数的情形。

一般情况下, n 个字符的频率恰好是前 n 个 Fibonacci 数,则相应的哈夫曼编码树深度为 n-1 ,第一个字符的编码长度为 n-1 ,自底向上第 i 个内结点中的数为 \sum_{k=0}^i f_k 。用数学归纳法容易证明,

\sum_{k=0}^if_k<f_{i+2}

该性质保证了恰好是前 n 个 Fibonacci 数的哈夫曼树具有所述形状和性质。

习题 4-11 整数边权最小生成树算法

假设具有 n 个顶点的连通带权图中所有边的权值均为从 1 n 之间的整数,能对 Kruskal 算法做何改进?时间复杂度能改进到何程度?若对某常量 N ,所有边的权值均为从 1 N 之间的整数,在这种情况下又如何?在上述两种情况下,对 Prim 算法能做何改进?

对于 Kruskal 算法,可以从对边权的排序上优化,因为边权都是整数,假设最大的整数边权为 M ,那我们就可以开一个大小为 M 的数组 cnt,存放所有的边权, \text{cnt}[\text{num}] 表示边权为 num 的边的个数。然后可以顺序的从 1 遍历到 M ,可以将排序部分的复杂度优化到 O(M)

Prim 算法的主要运算在于寻找顶点分别在 V-U U 中边权最小的边,找出边后再对 U ,lowcost 和 closest 进行调整。

如果用一个优先队列完成这些工作,则要求优先队列支持 DeleteMin 和 Decrease - Key 运算。如果采用 Fibonacci 堆来实现优先队列,可以在 O(|V|\log|V|) 时间内完成对优先队列的所有操作。因此 Prim 算法可以在 O(|E|+|V|\log|V|) 时间内完成。

如果边权是 1\sim N (常数) 的整数,可以用一个数组 Q[0:N+1] 表示优先队列。其中 N+1 单元存储一个大数,其他单元存储顶点的双链表,权值等于数组下标,则 DeleteMin 和 Decrease - Key 都只需要 O(1) 的时间,从而可以在 O(|E|+N^2)=O(|E|) ( N 是常数) 的时间完成 Prim 算法。

如果边权是 1\sim n 的整数,此时 Decrease - Key 仍可在 O(1) 时间完成,DeleteMin 需要 O(n) 时间,完成 Prim 算法需要 O(|E|+n^2) 时间。用 van Emde Boas 优先队列,可在 O(n\log\log n) 时间内完成所有优先队列操作,故可在 O(|E|+n\log\log n) 时间内完成 Prim 算法。

最小生成树

对下面的无向连通图采用 Prim 和 Kruskal 算法构造最小生成树。

使用 Prim 算法构造最小生成树:

使用 Kruskal 算法构造最小生成树:

用两种方法都可以求得最小生成树的总耗费为 $ 39 $ 。

搜索技术

假定问题的解能表示成一个 n 元组形式,如 (x_1,\ldots,x_n) ,其中 x_i 取自某个有穷集 S_i 。所有这些 n 元组构成问题的解空间。假设集合 S_i 的大小是 m_i ,则可能的组数 m=m_1m_2\cdots m_n 。考虑问题,

  • 存在性问题:求满足某些条件的一个或全部元组,如果不存在这样的元组,返回 false;这些条件称为约束条件。满足约束条件的元组称为问题的可行解。
  • 优化问题:给定一组约束条件,在可行解中求使目标函数达到最优的元组,即最优解。

解决这类问题的一般方法是搜索技术,主要包括回溯法分支限界法

状态空间树

解空间的树结构称为状态空间树,它是尝试选择元组的各个分量时产生的树结构。树中的每个结点代表问题求解过程中的一个状态,根结点到它的路径代表对一些分量已作出的选择。根到一个结点的路径可以表示为: (x(1),\ldots,x(k)) ,也用这个元组标识该结点。状态空间树的所有结点构成问题求解的状态空间。如果由根到结点 s 的那条路径确定了解空间的一个元组,称 s 对应的状态为一个解状态(solution state)。如果一个解状态代表的元组满足约束条件称其为答案状态(answer state)。

搜索算法

搜索算法通过展开状态空间树来找所求的解。

  • 活结点:已展开一个以上子结点,但所有子结点尚未全部产生的结点。
  • 死结点:被限界或已展开了所有子结点的结点。
  • 扩展结点(E - 结点):当前正在展开子结点的结点。
  • 深度优先展开方法:一个 E - 结点 C 展开自己的一个子结点 R 后,就让结点 R 成为 E - 结点,当完成 R 的所有子树的搜索后,让 C 重新成为 E - 结点,继续展开 C 的子结点(如果存在),这种方法相对于对解空间树做深度优先搜索,称为深度优先展开方法。
  • 广度优先展开方法:在当前 E - 结点处,先展开自己的所有子结点,然后再从当前的活结点表中选择下一个 E - 结点。
  • 剪枝:使用启发式的剪枝技术能使搜索算法只展开一部分状态空间树,降低开销。
    • 剪枝函数从分析约束条件或某种启发式得到,且必须计算简单。剪枝函数 B_i 是一谓词, B_i(x_1,\ldots,x_i)=\text{true} 当且仅当从当前状态不可能展开到一个答案结点。
      • 约束函数:扩展结点处减去不满足约束的子树;
      • 限界函数:扩展结点处减去得不到最优解的子树。
    • 剪枝,指停止展开结点 (x_1,x_2,\ldots,x_n)

搜索方式

  • 广度优先搜索:从初始状态开始,逐层地进行搜索。

  • 深度优先搜索:从初始状态开始,逐个分支的进行搜索。

  • 启发式的搜索:从初始状态开始,每次选择最有可能达到终止状态的结点进行搜索。

    • 回溯法:加剪枝的深度优先展开方法称为回溯法。
    • 分支限界法:以广度优先或最小耗费优先的方式搜索解空间树。
  • 广度优先搜索和深度优先搜索的优点是一定能找到解;缺点是时间复杂性大。

  • 启发式搜索的是最好优先的搜索,优点是一般来说能较快地找到解,时间复杂性更小;缺点是需要设计一个评价函数,并且评价函数的优劣决定了启发式搜索的优劣。

回溯

回溯法的算法框架

回溯法是能避免不必要搜索的穷举式搜索法。适用于解一些组合数相当大的问题。回溯法是一个既带有系统性又带有跳跃性的搜索算法。回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。为了避免生成那些不可能产生最优解的问题状态,要不断利用剪枝函数来剪掉那些实际上不可能产生所需解的活结点,以减少问题的计算量。回溯法的基本步骤

  1. 针对所给问题,定义问题的解空间,找出进行穷举的搜索范围。

  2. 确定易于搜索的解空间结构,一般是形成状态空间树。

  3. 深度优先方式搜索解空间,搜索过程中用剪枝函数(约束函数、限界函数)避免无效搜索。

递归回溯

回溯法对解空间进行深度优先搜索,一般情况下用递归方式实现回溯法。

void backtrack(int t) {
    if(t > n) output(x);	// 已到叶子,输出解
    else		// 内结点所有子树选择
        for(int i = f(n, t); i <= g(n, t); i++) {
            x[t] = h(i);
            if(constraint(t) && bound(t)) backtrack(t + 1);
        }
}

其中,形参 t 表示递归深度,即当前扩展结点在解空间树中的深度。 n 用来控制递归深度。 f(n,t) 表示当前扩展结点处未搜索的子树的起始编号, g(n,t) 是终止编号, h(i) 表示在当前扩展结点处 x[t] 的第 i 个可选值。 \text{constraint}(t) 是约束函数, \text{bound(t)} 是限界函数。显然,这一搜索过程按深度优先方式进行,调用一次 \text{backtrack}(1) 即可完成整个回溯搜索过程。

迭代回溯

采用树的非递归深度优先遍历算法,可将回溯法表示为一个非递归迭代过程。

void iterativeBacktrack() {
    int t = 1;
    while(t > 0) {
        if(f(n, t) <= g(n, t))
            for(int i = f(n, t); i <= g(n, t); i++) {
                x[t] = h(i);
                if(constraint(t) && bound(t)) {
                    if(solution(t)) output(x);
                    else t++;
                }
            }
        else t--;
    }
}

其中, \text{solution}(t) 判断在当前扩展结点处是否已得到问题的可行解。

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。即在任何时刻,算法只保存从根结点到当前扩展结点的路径。

如果解空间树中从根结点到叶结点的最长路径的长度为 h(n) ,则回溯法所需的计算空间通常为 O(h(n)) 。而显式存储整个解空间则需要 O\left(2^{h(n)}\right) O(h(n)!) 内存空间。

子集树与排列树

所给的问题是从 n 个元素的集合 S 中找出满足某种性质的子集时,相应的解空间树称为子集树。例如,0 - 1 背包问题所相应的解空间就是子集树。子集树通常有 2^n 个叶子结点,总结点数 2^{n+1}-1 。遍历子集树的算法需要 \Omega(2^n) 的计算时间。所给的问题是确定 n 个元素满足某种性质的排列时,解空间树称为排列树。如旅行售货员问题。排列树通常有 n! 个叶子结点,遍历排列树需 \Omega(n!) 计算时间。

用回溯法搜索子集树的一般算法可描述为:

void backtrack(int t) {
    if(t > n) output(x);
    else
        for(int i = 0; i <= 1; i++) {
            x[t] = i;
            if(constraint(t) && bound(t)) backtrack(t + 1);
        }
}

用回溯法搜索排列树的算法框架可描述为:

void backtrack(int t) {
    if(t > n) output(x);
    else
        for(int i = t; i <= n; i++) {
            swap(x[t], x[i]);
            if(constraint(t) && bound(t)) backtrack(t + 1);
            swap(x[t], x[i]);
        }
}

在调用 \text{backtrack}(1) 执行回溯之前,先将变量数组 x 初始化为单位排列 (1,2,\ldots,n)

装载问题

有一批共 n 个集装箱要装上两艘载重量分别为 c_1 c_2 的轮船,集装箱 i 的重量为 w_i ,且

\sum_{i=1}^n w_i\leq c_1+c_2

要求确定是否有一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有,找出一种方案。

当集装箱的总重量为 c_1+c_2 时,等价于子集和问题;当 c_1=c_2 且集装箱重量为 2c_1 时,等价于分划(划分)问题。这两个等价问题都是 NP - hard 问题,因此该问题是 NP - hard 问题。

如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案:

  1. 首先将第一艘轮船尽可能装满;
  2. 将剩余的集装箱装上第二艘轮船。

**证明:**设可行解在第一艘船装入 W_1\leq c_1 的重量,第二艘装入 W_2\leq c_2 的重量。

设最大化第一艘船的装船量为 M_1 ,则 W_1\leq M_1 ,则有,

\sum_{i=1}^n w_i - M_1=W_1+W_2-M_1\leq W_1+W_2-W_1=W_2

则剩下的集装箱一定能装入第二艘轮船,证毕。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,该子集中集装箱重量之和最接近 c_1 ,由此可知,装载问题等价于以下特殊的 0 - 1 背包问题。

\max \sum_{i=1}^n w_ix_i\quad\,\ \text{s.t. }\,\sum_{i=1}^{n}w_ix_i\leq c_1,\,x_i\in\{0,1\},\,1\leq i\leq n

可以用动态规划求解,时间复杂度为 O(\min\{nc,2^n\}) ;可以用回溯法求解,时间复杂度 O(2^n) ,但是由于回溯法可以用剪枝函数减小耗费,所以在某些情况下优于动态规划算法。

装载问题用子集树表示解空间,左子结点表示 x[i]=1 ,右子结点表示 x[i]=0 。cw 记录当前结点相应的装载重量,bestw 记录当前已经获得的最大装载重量。约束函数:如果 \text{cw}+w[i]>c_1 ,则剪掉该左子结点。右子结点的 cw 值与扩展结点的 cw 值相等,因此,展开右子结点时,不检查约束函数。限界函数:设 r 为未装的货箱的总重量,如果 \text{cw}+r\leq\text{bestw} ,则停止展开该结点,剪去右子树。左子结点和父结点有相同的 \text{cw}+r 值,展开左子结点时,不检查限界函数。搜素过程如下。

x=\{x_1,\ldots,x_{k-1}\} 为当前 E - 结点;如果 \text{cw}+w[k]>c_1 ,则停止展开该左子结点, r 减去 w[k] ,并展开右子结点;否则, x[k]=1 ,cw 加上 w[k] r 减去 w[k] (x_1,\ldots,x_k) 为 E - 结点。

如果 \text{cw}+r\leq \text{bestw} ,则停止展开该右子结点,并回溯到最近的一个活结点;否则,令 x[k]=0 ,新的 E - 结点为 (x_1,\ldots,x_k) 。回溯:从 i=k-1 开始,找 x[i]=1 的第一个 i ,修改 cw 和 r 的值。

k>n 时,算法搜索至叶结点,相应的载重量 cw,如果 \text{cw}>\text{bestw} ,则更新最优解。

回溯法求解装载问题的最优值,在每个结点处算法花费 O(1) 的时间,子集树中结点个数为 O(2^n) ,故算法的计算时间为 O(2^n) 。算法另外需要 O(n) 的栈空间。

如果要构造最优解,可以用 x 数组和 \text{bestx} 数组, x 用于记录从根至当前结点的路径, \text{bestx} 用于记录当前最优解,算法到达叶结点处,如果更新最优值,就修改 \text{bestx}

public class Loading {
    static int n;			// 集装箱数
    static int []w;		   // 集装箱重量数组
    static int c;			// 第一艘轮船的载重量
    static int cw;			// 当前载重量
    static int bestw;     // 当前最优载重量
    static int r;			// 剩余集装箱重量
    static int []x;		   // 当前解
    static int []bestx;	  // 当前最优解
    public static int maxLoading(int []ww, int cc, int []xx) {
        n = ww.length - 1; w = ww; c = cc; cw = 0; bestw = 0;
        x = new int[n + 1]; bestx = xx;		// 初始化类数据成员
        // 初始化
        for(int i = 1; i <= n; i++) r += w[i];
        // 计算最优载重量
        backtrack(1);
        return bestw;
    }
    public static void backtrack(int i) {	// 回溯算法
        if(i > n) {		// 到达叶结点
            if(cw > bestw) {
                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];
            backtrack(i + 1);
            cw -= w[i];
        }
        if(cw + r > bestw) {	// 搜索右子树
            x[i] = 0;
            backtrack(i + 1);
        }
        r += w[i];
    }
}

由于 bestx 可能被更新 O(2^n) 次,构造最优解的装载问题回溯算法时间复杂度为 O(n2^n)

以下两种方法可以在 O(2^n) 时间内构造装载问题的最优解。

  • 先运行只计算最优值的算法,计算出最优装载量 W ,由于该算法不记录最优解,故所需计算时间为 O(2^n) ,然后运行构造最优解的算法,并一开始将 bestw 置为 W ,在首次到达叶结点处终止算法,由此返回的 bestx 即位最优解。
  • 另一种方法是在算法中动态地更新 bestw,在第 i 层的当前结点处,当前最优解由 x[j],1\leq j<i \text{bestx}[j],i\leq j<n 组成。每当算法回溯一层,将 x[i] 存入 \text{bestx}[i] ,这样在每个结点处更新 bestx 只需 O(1) 时间,从而整个算法中更新 bestx 所需时间为 O(2^n)

数组 x 记录了解空间树中从根到当前扩展结点的路径,这些信息已包含了回溯法在回溯时所需信息。因此利用数组 x 所含信息,可将回溯法表示成非递归形式,省去 O(n) 的递归栈空间。

public static int maxLoading(int []w, int c, int []bestx) {
    int i = 1;		// 当前层
    int n = w.length - 1;
    int[] x = new int[n + 1];	// x[1:i-1] 为当前路径
    int bestw = 0;		// 当前最优载重量
    int cw = 0;			// 当前载重量
    int r = 0;			// 剩余集装箱重量
    for(int j = 1; j <= n; j++) r += w[j];
    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++;
        }
        while(cw + r <= bestw) {	// 剪枝回溯,找到最近的一个活结点
            i--;
            while(i > 0 && x[i] == 0) {		// 从右子树返回
                r += w[i];
                i--;
            }
            if(i == 0) return bestw;
            x[i] = 0;		// 进入右子树
            cw -= w[i];
            i++;
        }
    }
}

批处理作业调度

给定 n 个作业的集合 \{J_1,J_2,\ldots,J_n\} 。每个作业必须先由机器 1 处理,然后由机器 2 处理。作业 J_i 需要机器 j 的处理时间为 t_{ji} 。对于一个确定的作业调度,设 F_{ji} 是作业 i 在机器 j 上完成处理的时间。所有作业在机器 2 上完成处理的时间和称为该作业的完成时间和 f=\sum_{i=1}^n F_{2i}

批处理作业调度问题要求对于给定的 n 个作业,制定最佳调度方案,使其完成时间和最小。

显然批处理作业调度问题的解空间是一棵排列树,设开始时 x=[1,2,\ldots,n] 是所给的 n 个作业,则相应的排列树由 x[1:n] 的所有排列构成。递归中,当 i>n 时,算法搜索至叶结点,得到一个新的作业调度方案,此时算法更新当前最优值和相应的当前最优作业调度。当 i<n 时,扩展结点位于排列树的第 i-1 层,算法选择下个要安排的作业,剪去不满足上界约束的子树,对相应子树进行搜索。

public class FlowShop {
    static int n,			// 作业数
           int f1,			// 机器 1 完成处理时间
           int f,      	  // 完成时间和
           int bestf;  	  // 当前最优值
    static int [][]m;     // 各作业所需的处理时间
    static int []x;       // 当前作业调度
    static int []bestx;   // 当前最优作业调度
    static int []f2;      // 机器 2 完成处理时间
    
    public static void backtrack(int i) {
        if(i > n) {
            for(int j = 1; j <= n; j++) bestx[j] = x[j];
            bestf = f;
        }
        else
            for(int j = i; j <= n; j++) {
                f1 += m[x[j]][1];
                f2[i] = ((f2[i-1] > f1) ? f2[i-1] : f1) + m[x[j]][2];
                f += f2[i];
                if(f < best) {
                    swap(x, i, j);
                    backtrack(i + 1);
                    swap(x, i, j);
                }
                f1 -= m[x[j]][1];
                f -= f2[i];
            }
    }
}

算法在每一个结点处耗费 O(1) 计算时间,在最坏情况下,算法时间复杂度 O(n!)

符号三角形问题

下面是由 14 个 “+” 和 14 个 “-” 组成的符号三角形,两个同号下面都是 “+”,两个异号下面是 “-”。

                                + + - + - + +
                                 + - - - - +
                                  - + + + -
                                   - + + -
                                    - + -
                                     - -
                                      +

一般情况下,符号三角形的第一行有 n 个符号,符号三角形问题要求对于给定的 n ,计算有多少个不同的符号三角形,使得其所含的 “+” 和 “-” 的个数相同。

对于符号三角形问题,用 n 元组 x[1:n] 表示符号三角形的第一行的 n 个符号。当 x[i]=1 时,表示第一行第 i 个符号为 “+”,当 x[i]=0 时,表示符号 “-”。

由于 x[i] 是二值的,所以可以用一棵完全二叉树来表示其解空间。在第一行的前 i 个符号 x[1:i] 确定后,即确定了一个由 i(i+1)/2 个符号组成的符号三角形。下一步确定了 x[i+1] 后,只要在上一步已确定的符号三角形右边加一条边,即可扩展为 x[1:i+1] 对应的符号三角形。

x[1:n] 确定的符号三角形包含的 “+” 与 “-” 个数均为 n(n+1)/4 ,因此,可行性约束函数为,当前符号三角形所包含的 “+” 与 “-” 个数均不超过 n(n+1)/4 。无解的判断: n(n+1)/2 是奇数。

public class Triangles {
    static int n,			// 第一行的符号个数
           int half,      // n*(n+1)/4
           int count;     // 当前 "+" 个数
    static int [][]p;     // 符号三角形矩阵
    static long sum;      // 已找到的符号三角形个数
    public static long compute(int nn) {
        n = nn; count = 0; sum = 0;
        half = n*(n+1)/2;
        if(half % 2 == 1) return 0;
        half = half / 2;
        p = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++) p[i][j] = 0;
        backtrack(1);
        return sum;
    }
    public static void backtrack(int t) {
        if((count > half) || (t*(t-1)/2 - count) > half) return;
        if(t > n) sum++;
        else
            for(int i = 0; i < 2; i++) {
                p[1][t] = i;
                count += i;
                for(int j = 2; j <= t; j++) {
                    p[j][t-j+1] = p[j-1][t-j+1] ^ p[j-1][t-j+2];
                    count += p[j][t-j+1];
                }
                backtrack(t + 1);
                for(int j = 2; j <= t; j++) count -= p[j][t-j+1];
                count -= i;
            }
    }
}

计算可行性约束需要 O(n) 时间,在最坏情况下有 O(2^n) 个结点需要计算可行性约束,故解符号三角形问题的回溯算法所需的计算时间为 O(n2^n)

n 皇后问题

按照国际象棋规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题要求在 n\times n 格的棋盘上放置 n 个皇后,任意两个皇后不放在同一行或同一列或同一斜线上。

n 元组 x[1:n] 表示 n 皇后问题的解。其中 x[i] 表示皇后 i 放在棋盘的第 i 行的第 x[i] 列。由于不允许两个皇后放在同一列,所以解向量中的 x[i] 互不相同。两个皇后不能放在同一斜线上是问题的隐约束。设两个皇后 (i,j),\,(k,l) 在同一斜线上,则有: i-j=k-l (斜率为 -1 )或 i+j=k+l (斜率为 1 ),即等价于 |i-k|=|j-l| ,因此,约束条件不同斜线为 |i-j|\ne |x[i]-x[j]| 。用回溯法解 n 皇后问题时,解空间用完全 n 叉树表示。可行性约束 place 剪去不满足行、列和斜线约束的子树。

求解 n 皇后问题的递归回溯算法描述如下:

public class NQueen {
    static int n;			// 皇后个数
    static int []x;       // 当前解
    static long sum;      // 当前已找到的可行方案数
    
    public static long nQueen(int nn) {
        n = nn; sum = 0; x = new int[n + 1];
        for(int i = 0; i <= n; i++) x[i] = 0;
        backtrack(1);
        return sum;
    }
    
    public static boolean place(int k) {	// 可行性约束判断
        for(int j = 1; j < k; j++)
            if((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))
                return false;
        return true;
    }
    
    public static void backtrack(int t) {
        if(t > n) sum++;
        else
            for(int i = 1; i <= n; i++) {	// 一行中的 n 个放置位置
                x[t] = i;
                if(place(t)) backtrack(t + 1);
            }
    }
}

数组 x 记录了解空间树中从根到当前扩展结点的路径,这些信息已包含了回溯法在回溯时所需要的信息。利用数组 x ,可以将回溯法表示成非递归形式,省去 O(n) 递归栈空间。

public static void backtrack() {
    x[1] = 0;
    int k = 1;			// k 搜索深度,行号
    while(k > 0) {
        x[k] += 1;		// 从当前列加 1 的位置开始搜索
        while((x[k] <= n) && (!place(k)))	// 当前列位置是否不满足条件
            x[k] += 1;		// 不满足条件,继续搜索下一位置
        if(x[k] <= n) {		// 存在满足条件的列
            if(k == n) sum++;	// 是最后一个皇后,完成搜索
            else {		// 不是,则处理下一行的皇后
                k++;
                x[k] = 0;
            }
        }
        else k--;	// x[k] > n, 已判断完 n 列,均没有满足条件,回溯到前一行
    }
}

运行时间取决于所访问结点个数 c ,每访问一个结点,就调用一次 place 函数,一次 place 的计算时间是 O(n) 的,因此总体计算时间 O(cn) ,即最坏情况下计算时间 O(n^n)

0 - 1 背包问题

0 - 1 背包问题是子集选取问题。0 - 1 背包问题的解空间可以用子集树表示。在搜索解空间树时,只要其左子结点是一个可行结点,搜索进入左子树。右子树中可能含最优解时,进入右子树搜索。

否则将右子树剪去。计算右子树中解的上界的方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包,由此可得右子树解的上界。

求解 0 - 1 背包问题的回溯算法描述如下:

public class Knapsack {
    public static class Element implements Comparable {
        int id;		// 物品编号
        double d;
        public Element(int idd, double dd) {
            id = idd; d = dd;
        }
        public int compareTo(Object x) {
            double xd = ((Element)x).d;
            if(d < xd) return -1;
            if(d == xd) return 0;
            return 1;
        }
        public boolean equals(Object x) {
            return d == ((Element)x).d;
        }
    }
    
    static double c;		 // 背包容量
    static int n;			  // 物品数
    static double []w;		 // 物品重量数组
    static double []p;		 // 物品价值数组
    static double cw;		 // 当前重量
    static double cp;		 // 当前价值
    static double bestp;	// 当前最优价值
    
    public static double knapsack(double []pp, double []ww, double cc) {
        c = cc; n = pp.length - 1; cw = 0.0; cp = 0.0; bestp = 0.0;
        Element []q = new Element[n];	// 单位质量价值数组
        for(int i = 1; i <= n; i++)		// 初始化 
            q[i - 1] = new Element(i, pp[i]/ww[i]);
        MergeSort.mergeSort(q);
        p = new double[n + 1];
        w = new double[n + 1];
        for(int i = 1; i <= n; i++) {
            p[i] = pp[q[n - i].id]; w[i] = ww[q[n - i].id];
        }
        backtrack(1);
        return bestp;
    }
    
    public static void backtrack(int i) {
        if(i > n) {		// 到达叶结点
            bestp = cp;
            return;
        }
        if(cw + w[i] <= c) {	// 进入左子树
            cw += w[i]; cp += p[i];
            backtrack(i + 1);
            cw -= w[i]; cp -= p[i];
        }
        if(bound(i + 1) > bestp) backtrack(i + 1);	// 进入右子树
    }
    public static double bound(int i) {
        double cleft = c - cw;		// 剩余容量
        double bound = cp;
        while(i <= n && w[i] <= cleft) {	// 以单位重量价值递减顺序装入物品
            cleft -= w[i];
            bound += p[i];
            i++;
        }
        if(i <= n) bound += p[i]*cleft/w[i];	// 装满背包
        return bound;
    }
}

计算上界需要 O(n) 时间,最坏情况下有 O(2^n) 个右子结点需要计算上界,故时间复杂度 O(n2^n)

图的 m 着色问题

给定无向连通图 G m 种不同的颜色。用这些颜色为图 G 的各顶点着色,每个顶点着一种颜色,是否有一种着色法使 G 中每条边的两个顶点着不同颜色。这个问题是图的 m 可着色判定问题。

若一个图最少需要 m 种颜色才能使图中每条边连接的两个顶点着不同颜色,则称这个数 m 为该图的色数。求一个图的色数 m 的问题称为图的 m 可着色优化问题。

给定图 G=(V,E) m 种颜色,判断图是否 m 可着色,若 m 可着色,找出所有不同着色方案。

用图的邻接矩阵 a 表示无向连通图,若 (i,j) 属于图的边集 E ,则 a[i][j]=1 ,否则等于 0 ,用整数 1 m 表示 m 种不同颜色。顶点 i 所着颜色用 x[i] 表示,数组 x[1:n] 为解向量。问题的解空间为一棵高度为 n+1 m 叉树。可行性约束函数:顶点 i 与已着色的相邻顶点颜色不重复。

public class Coloring {
    static int n;				// 图的顶点数
           int m;            // 可用颜色数
    static boolean [][]a;    // 图的邻接矩阵
    static int []x;          // 当前解
    static long sum;         // 当前已找到的可 m 着色方案数
    
    public static long mColoring(int mm) {
        m = mm; sum = 0;
        backtrack(1);
        return sum;
    }
    public static void backtrack(int t) {
        if(t > n) {
            sum++;
            for(in i = 1; i <= n; i++)
                System.out.print(x[i] + " ");
            System.out.println();
        }
        else
            for(int i = 1; i <= m; i++) {
                x[t] = i;
                if(ok(t)) backtrack(t + 1);
                x[t] = 0;
            }
    }
    public static boolean ok(int k) {	// 检查颜色可用性
        for(int j = 1; j <= n; j++)
            if(a[k][j] && (x[j] == x[k])) return false;
        return true;
    }
}

m 着色问题的解空间树中内结点个数为 \sum_{i=0}^{n-1}m^i ,对于每一个内结点,在最坏情况下,用 ok 检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时 O(mn) ,因此,算法总耗时为,

\sum_{i=0}^{n-1}m^i (mn)=nm(m^n-1)/(m-1)=O(nm^n)

旅行售货员问题

某售货员要到若干城市去推销商品,已知各城市之间的路程(费用),他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(总费用)最小。

用带权图 G=(V,E) 来表示,顶点代表城市,边表示城市之间的路,边权即是城市之间的费用。

旅行售货员问题的解空间是一棵排列树。开始时 x=[1,2,\ldots,n]

递归回溯算法中,当 i=n 时,当前扩展结点是排列树中叶结点的父结点。算法要检查图 G 是否存在一条从顶点 x[n-1] 到顶点 x[n] 的边和一条从顶点 x[n] 到顶点 1 的边,只有这两条边都存在时,才找到问题的一个可行解。此外,还要判断这条回路的费用是否优于当前已找到的最优回路的费用 bestc,以决定此可行解是否为最优解。如果是,更新当前最优值 bestc 和当前最优解 bestx 。

i<n 时,当前扩展结点位于排列树的第 i-1 层。图 G 中存在从顶点 x[i-1] 到顶点 x[i] 的边时, x[1:i] 构成图 G 的一条路径,且当前 x[1:i] 的费用小于当前最优值时,算法进入树的第 i 层,否则将剪去相应的子树。问题的递归回溯算法可描述如下:

public class Bttsp {
    static int n;				// 图 G 的顶点数
    static int []x;          // 当前解
    static int []bestx;      // 当前最优解
    static float bestc;      // 当前最优值
    static float cc;         // 当前费用
    static float [][]a;      // 图 G 的邻接矩阵
    
    public static float tsp(int []v) {
        x = new int[n + 1];		// 置 x 为单位排列
        for(int i = 1; i <= n; i++) x[i] = i;
        bestc = Float.MAX_VALUE; bestx = v; cc = 0;
        backtrack(2);		// 搜索 x[2:n] 的全排列
        return bestc;
    }
    public static void backtrack(int i) {
        if(i == n) {
            if(a[x[n-1]][x[n]] < Float.MAX_VALUE && 
               a[x[n]][1] < Float.MAX_VALUE && 
               (bestc == Float.MAX_VALUE || 
               cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc)) {
                for(int j = 1; j <= n; j++) bestx[j] = x[j];
                bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
            }
        }
        else {
            for(int j = i; j <= n; j++)
                if(a[x[i-1]][x[j]] < Float.MAX_VALUE &&
                  (bestc == Float.MAX_VALUE || cc + a[x[i-1]][x[j]] < bestc)) {
                    swap(x, i, j);
                    cc += a[x[i-1]][x[i]];
                    backtrack(i + 1);
                    cc -= a[x[i-1]][x[i]];
                    swap(x, i, j);
                }
        }
    }
}

如果不考虑更新 bestx 所需的计算时间,算法 backtrack 需要 O((n-1)!) 计算时间。算法在最坏情况下需要更新当前最优解 O((n-1)!) 次,更新 bestx 需要 O(n) 时间,总时间复杂度 O(n!)

圆排列问题

给定 n 个大小不等的圆 c_1,c_2,\ldots,c_n ,现要将这 n 个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从 n 个圆的所有排列中,找出有最小长度的圆排列。

圆排列问题的解空间是一棵排列树,设开始时 a=[r_1,r_2,\ldots, r_n] 是所给的 n 个圆的半径,则相应的排列树由 a[1:n] 的所有排列构成。

回溯算法中,center 用于计算当前所选择的圆在当前圆排列中圆心的横坐标。compute 用于计算当前圆排列长度。变量 min 记录当前最小圆排列长度。数组 r 表示当前圆排列。

数组 x 记录当前圆排列中各圆的圆心横坐标。规定当前圆排列第一个圆的圆心横坐标为 0

递归回溯中,当 i>n 时,算法搜索至叶结点,得到新的圆排列方案,计算当前圆排列的长度,更新最优值。当 i < n 时,选择下一个圆加入排列中,计算限界函数,进行剪枝或深度优先展开。

public class Circles {
    static int n;			// 待排列圆的个数
    static float min;     // 当前最优值
    static float []x;     // 当前圆排列圆心横坐标
    static float []r;     // 当前圆排列
    
    public static float circlePerm(int nn, float []rr) {
        n = nn; min = 100000; x = new float[n + 1]; r = rr;
        backtrack(1);
        return min;
    }
    public static void backtrack(int t) {
        if(t > n) compute();
        else
            for(int j = t; j <= n; j++) {
                swap(r, t, j);
                float centerx = center(t);
                if(centerx + r[t] + r[1] < min) {	// 下界约束
                    x[t] = centerx;
                    backtrack(t + 1);
                }
                swap(r, t, j);
            }
    }
    public static float center(int t) {		// 计算当前所选择圆的圆心横坐标
        float temp = 0;
        for(int j = 1; j < t; j++) {
            float valuex = (float)(x[j] + 2.0*Math.sqrt(r[t]*r[j]));
            // 由 x^2 + (r1-r2)^2 = (r1+r2)^2 => x = 2*sqrt(r1*r2)
            if(valuex > temp) temp = valuex;
        }
        return temp;
    }
    public static float compute() {		// 计算当前圆排列的长度
        float low = 0, high = 0;
        for(int i = 1; i <= n; i++) {
            if(x[i] - r[i] < low) low = x[i] - r[i];
            if(x[i] + r[i] > high) high = x[i] + r[i];
        }
        if(high - low < min) min = high - low;
    }
}

最坏情况下,算法需要 O(n!) 次计算圆排列长度,每次计算圆排列长度需要 O(n) 的计算时间,故算法的时间复杂度为 O((n+1)!) 。算法的改进:算法中的对称排列具有相同的圆排列长度,可以只计算一次;如果已知的 n 个圆中有 k 个圆有相同的半径,这 k 个圆产生 k! 个相同圆排列,可只计算一次。

分支限界

分支限界法的基本思想

分支限界法与回溯法比较

相同:都是在问题的解空间树中搜索问题解的算法。

不同:求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标是找出满足约束条件的一个解,或在满足约束条件的解中找出在某种意义下的最优解。搜索方式:回溯法以深度优先方式搜索解空间树;分支限界法以广度优先或以最小耗费(最大效益)优先方式搜索。

搜索策略

在扩展结点处,分支限界法先生成其所有儿子结点(分支),然后再从当前活结点表中选择下一个扩展结点(广度优先)。为了有效地选择下一个扩展结点,加快搜索,通常在每一个活结点处计算一个函数值(限界),根据此函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支前进,以尽快找到一个最优解。

在分支限界法中,每一个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一个结点成为当前扩展结点,并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

从活结点表选择下一扩展结点的不同方式导致不同的分支限界法。

  1. 队列式(FIFO)分支限界法:按照队列先进先出(FIFO)原则选取下一结点为扩展结点。
  2. 优先队列式分支限界法:按照优先队列中规定的优先级选取优先级最高的结点为扩展结点。

优先队列中,结点优先级通常用一个与结点相关的数值 p 表示,优先级高低与 p 值大小相关。

  1. 最大优先队列: p 值较大的结点的优先级较高,通常用最大堆实现,用 removeMax 抽取堆中的下一个结点成为当前扩展结点,体现最大效益优先的原则。
  2. 最小优先队列: p 值较小的结点的优先级较高,通常用最小堆实现,用 removeMin 抽取堆中的下一个结点成为当前扩展结点,体现最小费用优先的原则。

队列式分支限界法的搜索过程与解空间树的广度优先遍历算法的唯一不同之处在于队列式分支限界法不搜索以不可行结点为根的子树。在寻求问题的最优解时可以用剪枝函数加速搜索。它给出每个可行结点相应的子树可能获得的最大价值的上界。如果上界不比当前最优值更大,则可以剪枝。另一方面,可以将由此上界函数确定的每个结点的上界值作为优先级,以其非增序抽取当前扩展结点。

装载问题

由前面可以知道,装载问题是一个子集选取问题,解空间数是一棵子集树。

队列式分支限界法

算法 maxLoading 实现对解空间的分支限界搜索,队列 queue 用于存放活结点表,队列元素的值表示活结点相应的当前装载量。当元素的值为 -1 时,表示队列到达解空间树同一层结点的尾部。

算法 enQueue 用于将活结点加入到活结点队列中。首先检查 i 是否等于 n

  • 如果 i=n ,则表示当前活结点为一个叶结点。由于叶结点不会被进一步扩展,因此不必加入到活结点队列中。只要检查叶结点表示的可行解是否优于当前最优解,并适时更新最优解。

  • i<n 时,当前活结点是内部结点,应加入活结点队列中。

在算法 maxLoading 的 while 循环中,首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。两个儿子结点都产生后,当前扩展结点被舍弃。

活结点队列中的队列元素被取出作为当前扩展结点。由于队列中的每一层结点之后都有同层结束标记 -1 ,故在取队首元素时,活结点队列一定不空。当取出的元素是 -1 时,判断队列是否为空。

  • 队列为空:没有活结点,算法结束。

  • 队列非空:控制进入下一层,将尾部标记 -1 加入活结点队列,算法开始处理下一层。

取出的元素不是 -1 时,控制不会进入下一层,扩展当前结点,检查左右子树。

public class FIFOBBLoading {
    static int n;
    static int bestw;			 // 当前最优载重量
    static ArrayQueue queue;	// 活结点队列
    
    public static int maxLoading(int []w, int c) {
        n = w.length - 1; bestw = 0;
        queue = new ArrayQueue();
        queue.put(new Integer(-1));		// 同层结点尾部标志
        
        int i = 1;		// 当前扩展结点所处的层
        int ew = 0;		// 扩展结点所相应的载重量
        
        while(true) {	// 搜索子集空间树
            // 检查左儿子结点
            if(ew + w[i] <= c) enQueue(ew + w[i], i);	// x[i] = 1
            // 右儿子结点总是可行的
            enQueue(ew, i);		// x[i] = 0
            ew = ((Interger)queue.remove()).intValue();		// 取下一扩展结点
            if(ew == -1) {		// 同层结点尾部
                if(queue.isEmpty()) return bestw;
                queue.put(new Interger(-1));	// 同层结点尾部标志
                ew = ((Interger)queue.remove()).intValue();		// 取下一扩展结点
                i++;		// 进入下一层
            }
        }
    }
    public static void enQueue(int wt, int i) {		// 将活结点加入活结点队列中
        if(i == n) {	// 可行叶结点
            if(wt > bestw) bestw = wt;
        }
        else queue.put(new Interger(wt));	// 非叶结点
    }
}

算法改进

设 bestw 是当前最优解;ew 是当前扩展结点相应的重量; r 是剩余集装箱重量。

则当 \text{ew}+r\leq \text{bestw} 时,可将其右子树剪去。回溯法中,初始状态 \text{bestw}=0 ,直到搜素到第一个叶子结点时更新 bestw 的值。因此算法在搜索到第一个叶结点之前,总有 \text{bestw}=0,\,r>0 ,剪枝策略不会起作用,即总有 \text{ew}+r>\text{bestw} 。为使右子树剪枝策略尽早生效,应尽早更新 bestw。

算法最终得到的 bestw 值,是子集树中所有可行结点相应重量的最大值,而结点相应的重量只有搜索进入左子树时增加,因此,可以在每一次进入左子树时更新 bestw 的值。

算法在每次进入左子树时提前更新了 bestw,因此将一个活结点加入队列时,左儿子结点的重量不会大于 bestw,不必更新 bestw,可直接将该活结点加入队列,不必调用 enQueue 算法完成插入。

public class FIFOBBLoading {
    static int n;
    static int bestw;          // 当前最优载重量 
    static ArrayQueue queue;	// 活结点队列
    
    public static int maxLoading(int []w, int c) {
        n = w.length - 1; bestw = 0;
        queue = new ArrayQueue();
        queue.put(new Integer(-1));		// 同层结点尾部标志
        
        int i = 1;		// 当前扩展结点所处的层
        int ew = 0;		// 扩展结点所相应的载重量
        int r = 0;		// 剩余集装箱重量
        for(int j = 2; j <= n; j++) r += w[j];
        
        while(true) {	// 搜索子集空间树
            // 检查左儿子结点
            int wt = ew + w[i];		// 左儿子结点的重量
            if(wt <= c) {		// 可行结点
                if(wt > bestw) bestw = wt;
                if(i < n) queue.put(new Interger(wt));	// 加入活结点队列
            }
            // 检查右儿子结点
            if(ew + r > bestw && i < n) queue.put(new Interger(ew)); // 可能含最优解
            ew = ((Interger)queue.remove()).intValue();		// 取下一扩展结点
            if(ew == -1) {		// 同层结点尾部
                if(queue.isEmpty()) return bestw;
                queue.put(new Interger(-1));	// 同层结点尾部标志
                ew = ((Interger)queue.remove()).intValue();		// 取下一扩展结点
                i++;		// 进入下一层
                r -= w[i];		// 剩余集装箱重量
            }
        }
    }
}

构造最优解

为了在算法结束后能方便地构造出与最优值相应的最优解,算法必须存储相应子集树中从活结点到根结点的路径。因此,可在每个结点处设置指向其父结点的指针,并设置左右儿子标志。

public static class QNode {
    QNode parent;          // 父结点
    boolean leftChild;    // 左儿子标志
    int weight;				// 结点所相应的载重量
    public QNode(QNode theParent, boolean theLeftChild, int theWeight) {
        parent = theParent; leftChild = theLeftChild; weight = theWeight;
    }
}

QNode 的引入导致的修改:算法 enQueue 、同层结束标志的修改。

public static void enQueue(int wt, int i, QNode parent, boolean leftchild) {
    if(i == n) {	// 可行叶结点
        if(wt == bestw) {		// 当前最优载重量
            bestE = parent;
            bestx[n] = (leftchild) ? 1 : 0;
        }
        return;
    }
    QNode b = new QNode(parent, leftchild, wt);	    // 非叶结点
    queue.put(b);
}

在算法结束搜索后,从子集树中与最优值相应的结点处向根结点回溯,构造出相应的最优解,算法可描述如下。算法结束后,bestx 中存放算法找到的最优解。

static int n;
static int bestw;          // 当前最优载重量 
static ArrayQueue queue;	// 活结点队列
static QNode bestE;        // 当前最优扩展结点
static int []bestx;        // 当前最优解

public static int maxLoading(int []w, int c, int []xx) {
    n = w.length - 1; bestw = 0;
    queue = new ArrayQueue();
    queue.put(null);		// 同层结点尾部标志
    QNode e = null; bestE = null; bestx = xx;
    
    int i = 1;		// 当前扩展结点所处的层
    int ew = 0;		// 扩展结点所相应的载重量
    int r = 0;		// 剩余集装箱重量
    for(int j = 2; j <= n; j++) r += w[j];
    
    while(true) {	// 搜索子集空间树
        // 检查左儿子结点
        int wt = ew + w[i];
        if(wt <= c) {	// 可行结点
            if(wt > bestw) bestw = wt;
            enQueue(wt, i, e, true)
        }
        // 检查右儿子结点
        if(ew + r > bestw) enQueue(ew, i, e, false);
        e = (QNode)queue.remove();		// 取下一扩展结点
        if(e == null) {		// 同层结点尾部
            if(queue.isEmpty()) break;
            queue.put(null);	// 同层结点尾部标志
            e = (QNode)queue.remove();		// 取下一扩展结点
            i++;		// 进入下一层
            r -= w[i];		// 剩余集装箱重量
        }
        ew = e.weight;		// 新扩展结点相应的载重量
    }
    for(int j = n - 1; j > 0; j--) {	// 构造最优解,注意:bestx[n] 在 enQueue 已更新
        best[j] = (bestE.leftChild) ? 1 : 0;
        bestE = bestE.parent;
    }
    return bestw;
}

优先队列式分支限界法

用最大优先队列存储活结点表,活结点 x 在优先队列中的优先级定义为从根结点到结点 x 的路径所对应的载重量再加上剩余集装箱的重量之和。优先队列中,优先级最大的活结点成为下一个扩展结点。以结点 x 为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点相应的载重量与其优先级相同。在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解,此时可终止算法。

算法的搜索过程中保存当前已构造出的部分解空间树,这样在算法确定了达到最优值的叶结点时,就可以在解空间树中从该叶结点开始向根结点回溯,构造出相应最优解。

值得注意的是,叶子结点作为算法的结束条件,是需要入优先队列的。优先队列打乱了结点之间的层次关系,因此,每个结点都要记录自己所在的层次。

算法中用元素类型为 HeapNode 的最大堆来表示活结点优先队列。

public static class BBnode {
    BBnode parent;			// 父结点
    boolean leftChild;    // 左儿子结点标志
    public BBnode(BBnode par, boolean ch) {
        parent = par; leftChild = ch;
    }
}
public static class HeapNode implements Comparable {
    BBnode liveNode;
    int uweight;		// 活结点优先级(上界)
    int level;        // 活结点在子集树中所处的层序号
    
    public HeapNode(BBnode node, int up, int lev) {
        liveNode = node; uweight = up; level = lev;
    }
    public int compareTo(Object x) {
        int xuw = ((HeapNode)x).uweight;
        if(uweight < xuw) return -1;
        if(uweight == xuw) return 0;
        return 1;
    }
    public boolean equals(Object x) {
        return uweight == ((HeapNode)x).uweight;
    }
}

在解装载问题的优先队列分支限界法中,算法 addLiveNode 将新产生的活结点加入到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。

public static void addLiveNode(int up, int lev, BBnode par, boolean ch) {
    BBnode b = new BBnode(par, ch);
    HeapNode node = new HeapNode(b, up, lev);
    heap.put(node);
}

i+1 层结点的剩余重量 r[i] 定义为: r[i]=\sum_{j=i+1}^n w[j] 。变量 e 是子集树中当前扩展结点,ew 是相应的重量。算法的 while 循环体产生当前扩展结点的左右儿子结点。如果当前扩展结点的左儿子是可行结点,即它所相应的重量未超过船载重量,则将它加入子集树的第 i+1 层,并插入最大堆。扩展结点的右儿子结点总是可行的,直接插入子集树的最大堆中。接着算法从最大堆中取出最大元作为下一扩展结点。如果下一个扩展结点是叶结点,即子集树的 n+1 层结点,则其相应的可行解为最优解。

public static int maxLoading(int []w, int c, int []bestx) {
    heap = new MaxHeap();
    int n = w.length - 1;
    BBnode e = null;    // 当前扩展结点
    int i = 1;         // 当前扩展结点所处的层
    int ew = 0;			// 扩展结点所相应的载重量
    int[] r = new int[n + 1];	// 定义剩余重量数组 r
    for(int j = n - 1; j > 0; j--) r[j] = r[j + 1] + w[j + 1];
    // 搜索子集空间树
    while(i != n + 1) {		// 非叶结点
        // 检查当前扩展结点的儿子结点
        if(ew + w[i] <= c)		// 左儿子结点为可行结点
            addLiveNode(ew + w[i] + r[i], i + 1, e, true);
        addLiveNode(ew + r[i], i + 1, e, false);
        // 取下一扩展结点
        HeapNode node = (HeapNode)heap.removeMax();
        i = node.level;
        e = node.liveNode;
        ew = node.uweight - r[i-1];	// 即第 i 层优先级:uweight = ew + r[i-1]
    }
    // 构造最优解
    for(int j = n; j > 0; j--) {
        bestx[i] = (e.leftChild) ? 1 : 0;
        e = e.parent;
    }
    return ew;
}

单源最短路经问题

在给定的有向图 G 中,每一边都有一个非负边权,求从源顶点 s 到目标顶点 t 之间的最短路径。

解单源最短路径问题的优先队列分支限界法用极小堆来存储活结点表。优先级是结点所对应的当前路长。算法从 G 的源顶点 s 和空优先队列开始,结点 s 被扩展后,儿子结点被依次插入堆中。

此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,依次检查与当前扩展结点相邻的顶点。如果从当前扩展结点 i 到顶点 j 有边可达,且从源出发,途径顶点 i 再到顶点 j 的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。结点的扩展过程一直继续到活结点优先队列为空时为止。算法还可以利用结点间的控制关系进行剪枝。从源顶点 s 出发,两条不同的路径到达图 G 的同一顶点。由于两条路径的路长不同,因此可以将路长较大的路径所对应的树中的结点(被控制结点)为根的子树剪去。具体算法可描述为:

public class BBShortest {
    public static class HeapNode implements Comparable {
        int i;				// 顶点编号
        float length;	  // 当前路长
        
        public HeapNode(int ii, float ll) {
            i = ii; length = ll;
        }
        public int compareTo(Object x) {
            float xl = ((HeapNode)x).length;
            if(length < xl) return -1;
            if(length == xl) return 0;
            return 1;
        }
    }
    static float [][]a;		// 图 G 的邻接矩阵
    
    public static void shortest(int v, float []dist, int []p) {
        int n = p.length - 1;
        MinHeap heap = new MinHeap();
        HeapNode enode = new HeapNode(v, 0);	// 定义源为初始扩展结点
        for(int j = 1; j <= n; j++) dist[i] = Float.MAX_VALUE;
        dist[v] = 0;
        while(true) {		// 搜索问题的解空间
            for(int j = 1; j <= n; j++)
                if(a[enode.i][j] < Float.MAX_VALUE &&
                  enode.length + a[enode.i][j] < dist[j]) {
                    // 顶点 i 到顶点 j 可达,且满足约束
                    dist[j] = enode.length + a[enode.i][j];
                    p[j] = enode.i;
                    HeapNode node = new HeapNode(j, dist[j]);
                    heap.put(node);		// 加入活结点优先队列
                }
            if(heap.isEmpty()) break;
            else enode = (HeapNode)heap.removeMin();	// 取下一扩展结点
        }
    }
}

算法结束后,dist 返回从源到各顶点的最短距离,可通过前驱顶点数组 p 构造最短路径。

0 - 1 背包问题

在解 0 - 1 背包问题的优先队列式分支限界法中,活结点优先队列中结点元素的优先级为已装的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和

子集树中以结点 node 为根的子树中任一结点的价值不超过 node.upperProfit(上界函数 bound 计算出价值的上界),因此用最大堆实现活结点优先队列。算法首先检查当前扩展结点的左儿子结点的可行性。如果可行,则将它加入到子集树和活结点队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列中。

由于每一步都是从活结点优先队列中取上界值最高的结点作为扩展结点,当扩展到叶子结点时,优先队列中的所有活结点价值上界均不超过该叶子结点的价值,即问题的最优值。

public static class BBnode {
    BBnode parent;          // 父结点
    boolean leftChild;		// 左儿子结点标志
    public BBnode(BBnode par, boolean ch) {
        parent = par; leftChild = ch;
    }
}
public static class HeapNode implements Comparable {
    BBnode liveNode;       // 活结点
    double upperProfit;		// 结点的价值上界
    double profit;         // 结点相应的价值
    double weight;         // 结点相应的重量
    int level;             // 活结点在子集树中所处的层序号
    public HeapNode(BBnode node, double up, double pp, double ww, int lev) {
        liveNode = node; upperProfit = up; profit = pp; weight = ww; level = lev;
    }
    public int compareTo(Object x) {
        double xup = ((HeapNode)x).upperProfit;
        if(upperProfit < xup) return -1;
        if(upperProfit == xup) return 0;
        return 1;
    }
}
public static class Element implements Comparable {
    int id;        // 编号
    double d;		// 单位重量价值
    public Element(int idd, double dd) {
        id = idd; d = dd;
    }
    public int compareTo(Object x) {
        double xd = ((Element)x).d;
        if(d < xd) return -1;
        if(d == xd) return 0;
        return 1;
    }
    public boolean equals(Object x) {
        return d == ((Element)x).d;
    }
}
public class BBKnapsack {
    static double c;        // 背包容量
    static int n;           // 物品总数
    static double []w;      // 物品重量数组
    static double []p;      // 物品价值数组
    static double cw;       // 当前重量
    static double cp;       // 当前价值
    static int []bestx;     // 最优解
    static MaxHeap heap;    // 活结点优先队列
    
    public static double bound(int i) {		// 计算结点所相应价值上界
        double cleft = c - cw;    // 剩余容量
        double 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;
    }
    public static void addLiveNode(double up, double pp, double ww, 
                                  int lev, BBnode par, boolean ch) {
        // 将一个新的活结点插入到子集树和最大堆中
        BBnode b = new BBnode(par, ch);
        HeapNode node = new HeapNode(b, up, pp, ww, lev);
        heap.put(node);
    }
}

首先完成对输入数据的预处理,即将物品按单位重量价值排序。然后进行分支限界搜索。

public static double knapsack(double []pp, double []ww, double cc, int []xx) {
    c = cc; n = p.length - 1;
    // 定义按单位重量价值排序的物品数组
    Element []q = new Element[n];
    double ws = 0.0;	// 装包物品重量
    double ps = 0.0;	// 装包物品价值
    for(int i = 1; i <= n; i++) {
        q[i - 1] = new Element(i, pp[i]/ww[i]);
        ps += pp[i]; ws += ww[i];
    }
    if(ws <= c) {		// 所有物品装包
        for(int i = 1; i <= n; i++) xx[i] = 1;
        return ps;
    }
    MergeSort.mergeSort(q);		// 按单位重量价值排序
    p = new double[n + 1]; w = new double[n + 1];
    for(int i = 1; i <= n; i++) {
        p[i] = pp[q[n - i].id]; w[i] = ww[q[n - i].id];		// 从大到小
    }
    cw = 0.0; cp = 0.0;
    bestx = new int[n + 1];
    heap = new MaxHeap();
    
    double maxp = bbKnapsack();		// 求解问题
    for(int i = 1; i <= n; i++) xx[q[n - i].id] = bestx[i];
    return maxp;
}
public static double bbKnapsack() {
    BBnode enode = null;
    int i = 1;
    double bestp = 0.0;        // 当前最优值
    double up = bound(1);		// 价值上界
    while(i != n + 1) {		// 搜索子集空间树
        // 检查当前扩展结点的左儿子结点
        double wt = cw + w[i];
        if(wt <= c) {		// 左儿子结点是可行结点
            if(cp + p[i] > bestp) bestp = cp + p[i];
            addLiveNode(up, cp + p[i], cw + w[i], i + 1, enode, true);
        }
        up = bound(i + 1);
        // 检查当前扩展结点的右儿子结点
        if(up >= bestp) addLiveNode(up, cp, cw, i + 1, enode, false);
        // 取下一扩展结点
        HeapNode node = (HeapNode)heap.removeMax();
        enode = node.liveNode;
        cw = node.weight; cp = node.profit;
        up = node.upperProfit; i = node.level;
    }
    for(int j = n; j > 0; j--) {	// 构造最优解
        bestx[j] = (enode.leftChild) ? 1 : 0;
        enode = enode.parent;
    }
    return cp;
}

旅行售货员问题

旅行售货员问题的解空间是一棵排列树,从根结点到任一叶结点的路径定义了一条周游路线,要在图 G 中找出费用最小的周游路线。对排列树搜索的优先队列分支限界法有两种不同的实现方式。

  • 只用优先队列存储活结点,每个活结点存储从根到该活结点的相应路径。
  • 用优先队列存储活结点,且同时存储当前已构造出的部分排列树。

不同点:结点结构不同,前者的结点中需要一个数组,保存相应路径,后者的结点中只需记录当前结点到其父结点的路径;构造最优解的方法不同,前者活结点保存了根到活结点的相应路径,算法结束时,不必回溯构造最优解,后者活结点本身不存储从根到活结点的相应路径,必要时可以从存储的部分排列树中回溯得到路径。以下讨论第一种实现方式。

用最小堆表示活结点优先队列,最小堆中元素类型为 HeapNode,该类型结点包含域 x ,用于记录当前解; s 表示结点在排列树中的层次,从排列树的根结点到该结点的路径为 x[0:s] ,需要进一步搜索的顶点是 x[s+1:n-1] ,cc 表示当前费用,lcost 表示子树费用的下界,rcost 是 x[s:n-1] 中顶点最小出边费用和(类似于装载问题中的 r )。其中,lcost 是优先队列的优先级。

public class BBTSP {
    public static class HeapNode implements Comparable {
        float lcost,	// 子树费用下界
              cc,		 // 当前费用
              rcost;	// x[s:n-1] 中顶点最小出边费用和
        int s;			 // 根结点到当前结点的路径为 x[0:s]
        int []x;		 // 需要进一步搜索的顶点是 x[s+1:n-1]
        public HeapNode(float lc, float ccc, float rc, int ss, int []xx) {
            lcost = lc; cc = ccc; rcost = rc; s = ss; x = xx;
        }
        public int compareTo(Object x) {
            float xlc = ((HeapNode)x).lcost;
            if(lcost < xlc) return -1;
            if(lcost == xlc) return 0;
            return 1;
        }
    }
    static float [][]a;		// 图 G 的邻接矩阵
}

算法首先计算出图中每个顶点的最小费用出边并用 minOut 记录。如果所给的有向图中某个顶点没有出边,则该图不可能有回路。算法的第 1 个扩展结点是排列树中根结点的唯一儿子结点。在该结点处,已确定的回路中唯一顶点为顶点 1 ,因此,初始时有:

s=0,\,x[0]=1,\,x[1:n-1]=(2,3,\ldots,n),\,\text{cc}=0,\,\,\text{rcost}=\sum_{i=s}^n \text{minout}[i]

算法用用 bestc 记录当前最优值。while 循环体完成对内部结点的扩展,对于当前扩展结点,

  • 首先考虑 s=n-2 的情形,此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用,将该叶结点插入优先队列,否则舍去。
  • s<n-2 时,算法依次产生当前扩展结点的所有子结点。由于当前扩展结点所相应的路径是 x[0:s] ,其可行结点是从剩余结点 x[s+1:n-1] 中选取的顶点 x[i] ,且 (x[s],x[i]) 是所给有向图中的一条边。对于每一个可行子结点,计算出前缀 (x[0:s],x[i]) 的费用 cc 和相应的下界 lcost。当 \text{lcost}<\text{bestc} 时,将这个可行结点插入活结点优先队列。

排列树的一个叶结点成为当前扩展结点时算法结束。当 s=n-1 时,已找到回路前缀是 x[0:n-1] ,它已包含图的所有 n 个顶点。因此,相应的扩展结点表示一个叶结点。该叶结点所相应的回路的费用等于 cc 和 lcost 的值,剩余的活结点的 lcost 值不小于已找到回路的费用,不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路,算法结束。

public static float bbTSP(int v[]) {
    int n = v.length - 1;
    MinHeap heap = new MinHeap();
    float []minOut = new float[n + 1];		// minOut[i]:顶点 i 的最小出边费用
    float minSum = 0;		// 最小出边费用和
    for(int i = 1; i <= n; i++) {	// 计算 minOut[i] 和 minSum
        float min = Float.MAX_VALUE;
        for(int j = 1; j <= n; j++)
            if(a[i][j] < Float.MAX_VALUE && a[i][j] < min)
                min = a[i][j];
        if(min == Float.MAX_VALUE) return Float.MAX_VALUE;	// 无回路
        minOut[i] = min; minSum += min;
    }
    int []x = new int[n];
    for(int i = 0; i < n; i++) x[i] = i + 1;
    HeapNode enode = new HeapNode(0, 0, minSum, 0, x);
    float bestc = Float.MAX_VALUE;
    while(enode != null) {		// 搜索排列空间树
        x = enode.x;	// 一定要更新 x,不然跳出循环无法获得最优解
        if(enode.s == n - 1) break;
        if(enode.s == n - 2) {		// 扩展结点为叶结点的父结点
            // 再加两条边构成回路,判断是否优于当前最优解
            if(a[x[n-2]][x[n-1]] < Float.MAX_VALUE &&
              a[x[n-1]][1] < Float.MAX_VALUE &&
              enode.cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1] < bestc) {
                bestc = enode.cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1];
                enode.cc = bestc; enode.lcost = bestc; enode.s++;
                heap.put(enode);
            }
        }
        else {
            // 产生当前扩展结点的儿子结点
            for(int i = enode.s + 1; i < n; i++)
                if(a[x[enode.s]][x[i]] < Float.MAX_VALUE) {
                    // 可行儿子结点
                    float cc = enode.cc + a[x[enode.s]][x[i]];
                    float rcost = enode.rcost - minOut[x[enode.s]];
                    float b = cc + rcost;		// 下界
                    if(b < bestc) {
                        // 子树可能含最优解,结点插入最小堆
                        int []xx = new int[n];
                        for(int j = 0; j < n; j++) xx[j]=x[j];
                        xx[enode.s + 1] = x[i];
                        xx[i] = x[enode.s + 1];
                        HeapNode node = new HeapNode(b, cc, rcost, enode.s + 1, xx);
                        heap.put(node);
                    }
                }
        }
        enode = (HeapNode)heap.removeMin();		// 取下一扩展结点
    }
    for(int i = 0; i < n; i++) v[i + 1] = x[i]; 	// 复制最优解
    return bestc;
}

批处理作业调度问题

n 个作业的集合 \{J_1,J_2,\ldots,J_n\} 。每个作业必须先由机器 1 处理,然后由机器 2 处理。作业 J_i 需要机器 j 的处理时间为 t_{ji} 。对于一个确定的作业调度,设 F_{ji} 是作业 i 在机器 j 上完成处理的时间。所有作业在机器 2 上完成处理的时间和称为该作业的完成时间和 f=\sum_{i=1}^n F_{2i}

批处理作业调度问题要求对于给定的 n 个作业,制定最佳调度方案,使其完成时间和最小。

用优先队列式分支限界法解此问题。可以证明存在最佳作业调度使得在机器 1 和机器 2 上作业以相同次序完成。在作业调度问题相应的排列空间树中,每一个结点 e 都对应于一个已安排的作业集 M ,以该结点为根的子树中所含叶子结点的完成时间和可以表示为:

f=\sum_{i\in M}F_{2i}+\sum_{i\notin M}F_{2i},\quad M\subseteq\{1,2,\ldots,n\}

|M|=r L 是以结点 e 为根的子树的一个叶结点,相应的作业调度为 \{p_k,k=1,2,\ldots,n\} ,其中, p_k 是第 k 个安排的作业。如果从结点 e 开始到叶结点 L 的路上,每个作业 p_k 在机器 1 上完成处理后都能立即在机器 2 上开始处理,即从 p_{r+1} 开始,机器 1 没有空闲时间,则对叶结点 L 有:

\sum_{i\notin M}F_{2i}=\sum_{k=r+1}^{n}[F_{1p_r}+(n-k+1)t_{1p_k}+t_{2p_k}]=S_1

如果不能做到这一点,则 S_1 只会增加,即 \sum_{i\notin M}F_{2i}\geq S_1

类似的,如果从结点 e 开始到结点 L ,从作业 p_{r+1} 开始,机器 2 没有空闲时间,则有:

\sum_{i\notin M}F_{2i}\geq \sum_{k = r+1}^n \left[\max\left(F_{2p_r},F_{1p_r}+\min_{i\notin M}(t_{1i})\right)+(n-k+1)t_{2p_k}\right]=S_2

由此,得到在结点 e 处相应子树中叶结点完成时间和的下界是 f\geq\sum_{i\in M}F_{2i}+\max\{S_1,S_2\} ,其中 S_1 S_2 的计算依赖于叶子节点 L 相应的作业调度。注意到如果选择 p_k ,使 t_{1p_k} k\geq r+1 时按非减序排列,则 S_1 取得极小值 \hat{S_1} 。同理如果选择 p_k 使 t_{2p_k} 按非减序排序,则 S_2 取得极小值 \hat{S_2} 。且 \hat{S_1} \hat{S_2} 与叶结点的调度无关,从而有 f\geq\sum_{i\in M}F_{2i}+\max\{\hat{S_1},\hat{S_2}\} ,用此可作为优先级和限界函数。

算法中用一个最小堆来表示活结点优先队列。最小堆中元素类型是 HeapNode。每一个 HeapNode 类型的结点包含域 x ,用来表示结点所相应的作业调度。 s 表示该结点已安排的作业是 x[1:s] \text{f}[1] 表示当前已安排的作业在机器 1 上的最后完成时间; \text{f}[2] 表示当前已安排作业在机器 2 上的最后完成时间;sf2 表示当前已安排作业在机器 2 上的完成时间和;bb 表示当前完成时间和的下界。

public static class HeapNode implements Comparable {
    int s,     // 已安排的作业数
        sf2,   // 当前机器 2 上的完成时间和
        bb;    // 当前完成时间和下界
    int []f;   // f[1]:机器1最后完成时间,f[2]:机器2最后完成时间
    int []x;	// 当前作业调度
    public HeapNode(int n) {
        x = new int[n];
        for(int i = 0; i < n; i++) x[i] = i;
        s = 0; f = new int[3]; f[1] = 0; f[2] = 0; sf2 = 0; bb = 0;
    }
    public HeapNode(HeapNode e, int []ef, int ebb, int n) {
        x = new int[n];
        for(int i = 0; i < n; i++) x[i] = e.x[i];
        f = ef; sf2 = e.sf2 + f[2]; bb = ebb; s = e.s + 1;
    }
    public int compareTo(Object x) {
        int xbb = ((HeapNode)x).bb;
        if(bb < xbb) return -1;
        if(bb == xbb) return 0;
        return 1;
    }
}
public class BBFlow {
    static int n;              // 作业数
               bestc;          // 最小完成时间和
    static int [][]m;          // 各作业所需的处理时间数组
    static int [][]b;          // 各作业所需的处理时间排序数组
    static int [][]a;          // 数组 m 和 b 的对应关系数组
    static int []bestx;        // 最优解
    static boolean [][]y;		// 工作数组
    
    public static void sort() {		// 对各作业在机器 1 和机器 2 上所需时间排序
        int c = new int[n];
        for(int j = 0; j < 2; j++) {
            for(int i = 0; i < n; i++) {
                b[i][j] = m[i][j];
                c[i] = i;
            }
            for(int i = 0; i < n - 1; i++)
                for(int k = n - 1; k > i; k--)
                    if(b[k][j] < b[k - 1][j]) {
                        swap(b, k, j, k - 1, j);
                        swap(c, k, k - 1);
                    }
            for(int i = 0; i < n; i++) a[c[i]][j] = i;
        } 
    }
    public static int bound(HeapNode enode, int []f) {	// 计算完成时间和的下界
        for(int k = 0; k < n; k++)
            for(int j = 0; j < 2; j++)
                y[k][j] = false;
        for(int k = 0; k <= enode.s; k++)
            for(int j = 0; j < 2; j++)
                y[a[enode.x[k]][j]][j] = true;
        f[1] = enode.f[1] + m[enode.x[enode.s]][0];
        f[2] = ((f[1] > enode.f[2]) ? f[1] : enode.f[2]) + m[enode.x[enode.s]][1];
        int sf2 = enode.sf2 + f[2];
        int s1 = 0, s2 = 0, k1 = n - enode.s, k2 = n - enode.s, f3 = f[2];
        // 计算 s1 的值
        for(int j = 0; j < n; j++)
            if(!y[j][0]) {
                k1--;
                if(k1 == n - enode.s - 1)
                    f3 = (f[2] > f[1] + b[j][0]) ? f[2] : f[1] + b[j][0];
                s1 += f[1] + k1 * b[j][0];
            }
        // 计算 s2 的值
        for(int j = 0; j < n; j++)
            if(!y[j][1]) {
                k2--;
                s1 += b[j][1];
                s2 += f3 + k2 * b[j][1];
            }
        // 返回完成时间和的下界
        return sf2 + ((s1 > s2) ? s1 : s2);
    }
}

bbFlow 是算法的主体,算法开始时,将排列树的根结点置为当前扩展结点。在初始扩展结点处还没有选定的作业,故 s=0 ,数组 x 初始化为单位排列。算法的 while 循环完成对排列树内部结点的有序展开。算法依次从活结点优先队列中取出具有最小完成时间和下界的结点作为当前扩展结点,并加以扩展。首先考虑 \text{enode.}s=n 的情形,此时扩展结点 enode 是排列树的叶结点。 \text{enode.}x 表示相应于该叶结点的作业调度。 \text{enode.sf2} 是该叶结点的完全时间和。小于 bestc 时更新最优值和最优解。

\text{enode.}s<n 时,算法依次产生当前扩展结点的所有儿子结点。对于当前结点的每一个儿子结点 node,计算出其相应的完成时间和的下界 bb,当 \text{bb}<\text{bestc} 时,将该儿子结点插入到活结点优先队列中。当 \text{bb}\geq\text{bestc} 时,以 node 为根的子树中不可能有最优解,舍去。

public static int bbFlow(int nn) {
    n = nn; sort();	// 对各作业在机器 1 和机器 2 上所需时间排序
    MinHeap heap = new MinHeap();
    HeapNode enode = new HeapNode(n);
    do {	// 搜索排列空间树
        if(enode.s == n) {		// 叶结点
            if(enode.sf2 < bestc) {
                bestc = enode.sf2;
                for(int i = 0; i < n; i++) bestx[i] = enode.x[i];
            }
        }
        else // 产生当前扩展结点的儿子结点
            for(int i = enode.s; i < n; i++) {
                swap(enode.x, enode.s, i);
                int []f = new int[3];
                int bb = bound(enode.f);
                if(bb < bestc) {	// 子树可能含最优解,结点插入最小堆
                    HeapNode node = new HeapNode(enode, f, bb, n);
                    heap.put(node);
                }
                swap(enode.x, enode.s, i);
            }	// 完成结点扩展
        enode = (HeapNode)heap.removeMin();
    } while(enode != null && enode.s <= n);
    return bestc;
}
1赞
粤 ICP 备 2020080455 号