导图社区 算法设计与分析
- 288
- 5
- 3
- 举报
算法设计与分析
导图介绍了几种基本的算法，包括：分治、动态规划、贪心、回溯和分支限界。适合小白对算法有初步了解。同时配套了大量的案例和图片，帮助理解算法的内容和思想。
编辑于2021-07-23 12:47:52
- 相似推荐
- 大纲
第1章 算法引论
1.1 算法与程序
1. 输入
有零个或多个外部量作为算法的输入
2. 输出
算法产生至少一个量作为输出
3. 确定性
组成算法的每条指令是清晰的、无歧义的
4. 有限性
算法中每条指令的执行次数有限，执行每条指令的时间也有限
1.2 表达算法的抽象机制
1. 高级程序设计语言的好处
· 更接近算法语言，易学、易掌握
· 提供了结构化程序设计的环境和工具，程序可读性好、可维护性高、可靠性高
· 不依赖于机器语言，与硬件关系不大，移植性好、重用率高
· 自动化程度高，开发周期短
2. 抽象数据类型的好处
· 使算法顶层设计与底层实现分离，不必考虑底层实现
· 算法设计与数据结构设计隔开，算法效率得到优化
1.3 算法步骤
1. 问题陈述
· 问题的每句话或每个词的含义是否清楚
· 已经给出了什么信息
· 希望找到什么结果
· 给出的信息是否有冗余部分
· 是否还有什么隐藏信息
· 是否已经做了某种假设
...
2. 模型拟制
· 最适合这个问题的数学模型是什么
· 在已经解决的其它问题中有没有与此类似的问题
...
3. 算法设计（*）
4. 算法正确性证明
· 对每一步提供证明，尤其是要证明在这一步执行前后存在的条件和引理
· 提供依据，证明算法将中止
5. 算法实现（*）
6. 算法复杂性分析
· 需要对算法所需的内存空间和运行时间进行估算或限界
· 能用定量标准来比较同一问题的不同算法的效率
7. 实验测试
（1）实验测试的4个方面
· 选择问题：测试什么，测试目的
· 确定度量指标
· 生成测试数据
· 编程和运行
（2）数据分析
· 比率测试
· 幂测试
8. 文件编制
内容包含: 1. 问题描述和分析 2. 建模和求解 3. 算法设计和正确性证明过程 4. 算法复杂度分析 5. 测试结果记录和分析报告 6. 输入/输出要求及格式描述等
1.4 算法复杂性分析
1. 算法时间复杂度的表示
用 T(N, I)表示算法A在一台抽象计算机上的时间复杂度。其中: · N: 待求解问题的规模 · DN: 所有可能的输入规模为N的输入构成的集合 · P(DN): DN的概率分布 · I: 算法的输入
2. 时间复杂性的度量
· 最坏情况:
· 最好情况:
不作为度量指标
· 平均情况:
3. 渐进复杂度
如果存在正的常数 C 和自然数 N，使得当 n >= N 时有f(n) <= C·g(n) ，则称函数 f(n) 当 n 充分大时上有界，且 g(n) 是它的一个上界，记为 f(n) = O(g(n)) · 紧确上界: f(n) = C·g(n) · 非紧确上界: f(n) < C·g(n) （非紧确上界用 o 表示）
如果存在正的常数 C 和自然数 N，使得当 n >= N 时有f(n) <= C·g(n)，则称函数 f(n) 当 n 充分大时下有界，且 g(n)是它的一个下界，记为 f(n) = W(g(n)) · 紧确下界：f(n) = C·g(n) · 非紧确下界：f(n) > C·g(n), （非紧确下界用 ω 表示）
我们记f(n) = Q(g(n))，当且仅当f(n) = O(g(n))且f(n) = W(g(n))，此时f(n)与g(n)同阶
对于任意给定的 ϵ > 0，都存在正整数 N，使得当 n >= N 时有f(n)/g(n) < ϵ , 则称函数 f(n) 当 n 充分大时的阶比 g(n) 低，为非紧确上界，记为 f(n) = o(g(n))
对于任意给定的 w > 0，都存在正整数 N，使得当 n >= N 时有f(n)/g(n) > w , 则称函数 f(n) 当 n 充分大时的阶比 g(n) 高，为非紧确下界，记为 f(n) = w(g(n))
4. 理解
（1）问题
如何表示 f(n) 上界是 g(n) ？ 按照数学中集合的概念， 应表示为: f(n) ∈ O(g(n))
（2）回答
算法中表示为: f(n) = O(g(n)) 好处：直观表达出复杂度 f(n) 的上界为 g(n) 的含义。 · 不能写成 O(g(n)) = f(n) · 勿使用 O(f) + O(g) = f(N) + G(N) 写法 · O(g(n))也可表示任意一个以g(n)为上界的函数 · O(1) 表示常数
第2章 递归与分治策略
2.1 递归
1. 递归定义
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
2. 常见递归算法
（1）阶乘n!
（2）Fibonacci数列
（3）Ackerman函数
3. 应用举例
（1）排列问题
问题说明
设计递归算法生成 R = {r1, r2, ... , rn} 中元素的全排列
符号约定
· Ri = R - ri
· 集合X中元素的全排列记为perm(X)
· (ri)perm(X) 表示在全排列 perm(X) 的每一个排列前加上前缀 ri 得到的排列
递推公式
（2）整数划分问题
问题说明
将正整数 n 表示成一系列正整数之和：
思路解析
· 按照划分定义，划分的最大加数为n1
· 将最大加数 n1<=m 的划分个数记为q(n,m)
递推公式
（3）Hanoi塔问题
问题说明
设a,b,c是3个塔座。a上有n个圆盘，自上而下由小到大地堆叠，依次编号为1, 2,⋯ , n,现要将a上的圆盘移到b上，并仍按同样顺序叠置。移动圆盘时应遵守以下规则： · 规则1：每次只能移动1个圆盘； · 规则2：任何时刻都不允许将大圆盘压在小圆盘之上； · 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上
递归算法
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); } }
2.2 分治法的基本思想
1. 基本思想
（1）将难以直接解决的大问题分割为若干子问题
（2）分别求解各个子问题
（3）再通过子问题的解合并出大问题的解
2. 一般的算法设计
1. 通用模式代码
divide-and-conquer(P) { if (|P| <= n0) adhoc(P); divide P into smaller subinstances P1, P2, ... , Pk; for (i = 1, i <= k; i++) yi = divide-and-conquer(Pi); return merge(y1, ... , yk); }
2. 说明
|P|
问题P的规模
n0
一个阈值，表示当问题P的规模不超过n0时容易解出，不必分解
adhoc(P)
分治法中的基本子算法
merge(y1, ... yk)
分治法中的合并子算法
3. 相关分析
（1）前提假设
为方便起见，设每一级分解的子问题数为k，分解阈值n0=1，adhor解规模为1的问题耗费1单位时间。记f(n)为将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用的时间，T(n)为该分治法divide-and-conquer(P)解规模为|P|=n的问题所需的计算时间。
（2）递推关系
（3）求解
（4）补充
若f(n) = c·ni，方程的解为:
4. 算法描述
divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 //!1: DIVIDE: 分解问题 divide P into smaller subinstances P1,P2,...,Pk； //!2: CONQUER: 递归的解各子问题 for (i=1,i<=k,i++) yi = divide-and-conquer(Pi); //!3: MERGE: 将各子问题的解合并为原问题的解 return merge(y1,...,yk); }
2.3 二分搜索技术
1. 介绍
二分搜索算法是运用分治策略的一个典型例子。这个方法很好地利用了n个元素已经排好序的条件，使得时间复杂度从顺序查找的O(n)降低为O(logn)
2. 算法描述（java语言）
· 非递归
public static int binarySearch(int[] a, int x, int n) { // 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x // 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int 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 }
· 递归
public static int binSearch(int srcArray[], int start, int end, int key) { int mid = (end - start) / 2 + start; if (srcArray[mid] == key) { return mid; } if (start > end) { return -1; } else if (key > srcArray[mid]) { return binSearch(srcArray, mid + 1, end, key); } else if (key < srcArray[mid]) { return binSearch(srcArray, start, mid - 1, key); } return -1; }
2.4 大整数的乘法
1. 问题介绍
通常，在分析算法复杂性时，都将加法和乘法运算当做基本运算处理。然而在某些情况下，要处理很大的整数，它无法直接在计算机中表示，因此我们需要用软件的方法来实现大整数的计算。 假设X和Y都是n位的二进制大整数，现在计算它们的乘积。为了简单起见，n为2的幂。
2. 算法思路
· 将n位二进制整数X和Y都分为2段，每段长为n/2位，如图:
· 由此，可以得到:
· 将X与Y的乘积写成以下形式:
· 因此计算时每次只需要做3次n/2位整数的乘法，6次加减法和2次移位
3. 递推公式
4. 求解
2.5 Strassen矩阵乘法
1. 问题介绍
在计算矩阵的乘法过程中，我们记两个n阶矩阵为A和B，乘积为C。则计算C的每一个元素C[i][j]需要做n次乘法运算和n - 1次加法计算。因此计算C的n2个元素所需计算时间为O(n3)，这显然需要改进。为了简化问题，我们记n为2的幂。
2. 算法思路
· 将矩阵A、B和C中每一矩阵都分块成4个大小相等的子矩阵，如图:
· 为了减少乘法计算，我们先进行如下7次计算:
· 然后，我们将Cij表示为如下:
3. 递归公式
4. 求解
2.6 棋盘覆盖
1. 问题介绍
在一个2k·2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，该棋盘为特殊棋盘。我们要求用4种不同形态的L型骨牌覆盖给定的特殊棋盘上非特殊方格，且覆盖不允许重复。
2. 算法思路
· 将2k·2k棋盘分割为4个2k-1·2k-1子棋盘，所以特殊方格一定位于其中一个子棋盘，剩下3个无特殊方格的子棋盘:
· 我们用一个L型骨牌覆盖着三个子棋盘的汇合处，如图:
· 循环往复，直至化简为1·1棋盘
3. 递推公式
4. 求解
5. 算法描述
public void chessBoard(int tr, int tc, int dr, int dc, int size) //tr:row, tc:column { if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 if (dr < tr + s && dc < tc + s) // if-else语句处理左上角子棋盘 chessBoard(tr, tc, dr, dc, s); // 特殊方格在此棋盘中 else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s); // 覆盖其余方格 } if (dr < tr + s && dc >= tc + s) // if-else语句处理右上角子棋盘 chessBoard(tr, tc+s, dr, dc, s); // 特殊方格在此棋盘中 else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); // 覆盖其余方格 } if (dr >= tr + s && dc < tc + s) // if-else语句处理左下角子棋盘 chessBoard(tr+s, tc, dr, dc, s); // 特殊方格在此棋盘中 else {// 此棋盘中无特殊方格 board[tr + s][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s); // 覆盖其余方格 } if (dr >= tr + s && dc >= tc + s) // if-else语句处理右下角子棋盘 chessBoard(tr+s, tc+s, dr, dc, s); // 特殊方格在此棋盘中 else { // 此棋盘中无特殊方格 board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); // 覆盖其余方格 } }
2.7 合并排序
1. 算法思想
将待排序的元素分成大小大致相同的2个子集合，分别对子集合进行排序，最终将排序好的子集合合并成为所需要的集合
2. 递归公式
3. 求解
4. 示例
5. 算法描述
public static void mergeSort(Comparable a[], int left, int right) { 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 } }
2.8 快速排序
1. 算法思路
（1）分解
以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）递归求解
递归调用，对a[p:q-1]和a[q+1:r]进行排序
（3）合并
不需要任何计算，递归之后已经排好序了
2. 递归公式
（1）最坏情况
（2）最好情况
3. 求解
（1）最坏情况
（2）最好情况
（3）平均情况
我们对基准p采用随机选择的方法，可以证明在平均情况下快排的复杂度为
4. 算法描述
private static int partition (int p, int r) { int i = p, j = r + 1; Comparable x = a[p]; //固定选择第一个元素作为pivot // 将 <x 的元素交换到左边区域 // 将 >x 的元素交换到右边区域 while (true) { while (a[++i].compareTo(x) < 0 && i<r); while (a[--j].compareTo(x) > 0); if (i >= j) break; MyMath.swap(a, i, j); } a[p] = a[j]; a[j] = x; return j; } private static int randomizedPartition (int p, int r) { int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); }
2.9 线性时间选择
1. 问题介绍
给定从小到大的数组: a[1] a[2] ... a[k] ... a[n] 要求找出其中第k小的元素。k (1<=k<=n)
2. 算法思路
· 随机选择一个pivot
· 比pivot小的前移，比pivot大的后移
· 一轮之后按照pivot将数组划分，且知道pivot的序号j。若要选择第k小的数，分3种情况
（1）k = j : 即为要选择的数，退出算法
（2）k < j : 递归求解左侧子问题
（3）k > j : 递归求解右侧子问题
3. 复杂度分析
· 最坏时间复杂度
· 平均时间复杂度
4. 算法改进
（1）介绍
如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的 2 个子数组的长度都至少为原数组长度的 ε 倍( 0 < ε < 1)，那么就可以在最坏情况下用 O(n) 时间完成选择任务
（2）步骤
· 5 个元素一组，将 n 个输入元素划分成 ⌈n/5⌉ 个组（最后一组可能不满5个元素)。各组内元素用任意算法排好序，并取出各组中位数，共⌈n/5⌉个 ~ O(n)
· 递归调用 select 来找出这 ⌈n/5⌉ 个各组中位数的中位数作为pivot x ~ T(n/5)
· 以 x 划分出2个子数组 ~ O(n)
· 根据 pivot 的序数和当前要选择的序数比较结果，对子数组进行递归调用选择算法 ~ T(3n/4)
（3）分析
· 基准 x 至少比 ë3(n - 5)/10û 个元素(红色)大
· 基准 x 至少比 ë3(n - 5)/10û 个元素(绿色)小
· 当n>=75时，ë3(n - 5)/10û>=n/4，所以按此基准划分所得的2个子数组的长度都至少缩短1/4
（4）复杂度
5. 算法描述
private static Comparable randomizedSelect(int p,int r,int k) { if (p==r) return a[p]; int i = randomizedpartition(p,r), j = i-p+1; if (k<=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); } private static Comparable select (int p, int r, int k) { if (r-p<5) { //用某个简单排序算法对数组a[p:r]排序; bubbleSort(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(s,t-j); //bubble 为bubbleSort 中的一轮冒泡 MyMath.swap(a, p+i, s+2); } //找中位数的中位数， Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k<=j) return select(p,i,k); else return select(i+1,r,k-j); }
2.10 最接近点对问题(*)
2.11 循环赛日程表
1. 问题描述
设计一个满足以下要求的循环比赛日程表: (1) 每个选手必须与其他 n − 1 个选手各赛一次 (2) 每个选手一天只能赛一次 (3) 循环赛一共进行 n − 1 天
2. 算法思路
将所有的选手分为两半，n ( 取2k ) 个选手的比赛日程表就可以通过为 n/2 个选手设计的比赛日程表来决定。 递归地对选手进行分割，直到只剩下 2 个选手时，比赛日程表的制定就变得很简单。这时只要让这 2 个选手进行比赛就可以了。
3. 图解
第3章 动态规划
3.1 矩阵连乘问题
1. 探寻问题
多个矩阵相乘，乘积顺序会影响计算次数。如图
2. 问题介绍
给定 n 个矩阵{A1, A2,⋯ , An}，其中 Ai 与 Ai+1 是可乘的，i = 1, 2,..., n − 1。 给出数乘次数最少的矩阵连乘积顺序
3. 穷举法
（1）算法思路
列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序
（2）算法过程
· 记P(n)为n个矩阵连乘不同计算顺序的数量
· 最外层在k处结合，分为2两个子问题:
· 递归计算
（3）递推公式
（4）求解
4. 动态规划求解
（1）前提假设
· AiAi+1...Aj(i<=j)简记为A[i:j]
（2）最优解的结构特征
A[i : j] 的最优计算次序所包含的矩阵子链 A[i : k] 和 A[k + 1 : j] 的计算次序也一定是最优的。
（3）建立递归关系
用 m[i, j] 表示计算 A[i : j]（1<=i<=j<=n）所需最少乘法次数，则建立以下递归关系:
（4）重叠子问题
递归算法求解时重叠子问题被反复多次计算:
解决方法：填表法（非递归），带备忘录（递归）
（5）算法描述
public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=p.length-1; for (int i = 1; i <= n; i++) m[i][i] = 0; for (int r = 2; r <= n; r++) for (int i = 1; i <= n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = 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]; if (t < m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } int RecurMatrixChain(int i, int j) { if (i==j) return 0; int u=RecurMatrixChain(i, i) + RecurMatrixChain(i+1, j) +p[i-1]*p[i]*p[j]; s[i][j]=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]; if (t < u) { u = t; s[i][j] = k; } } return u; } a <- 0; // 执行前 m 初始化全 0 private 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; }
（6）复杂度分析
· 时间复杂度
· 空间复杂度
3.2 动态规划算法的基本要素
1. 两大要素
（1）最优子结构特性
大规模问题的最优解包含其子问题的最优解
（2）重叠子问题特性
分解问题时会反复产生相同子问题
2. 最优子结构
（1）如何分析问题的最优子结构性质？ 反证法
先假设原问题最优解导出的子问题解不是最优，再说明此时可构造出比原问题最优解更好的解，故矛盾
（2）如何利用最优子结构性质？ 构造递推关系式
以自底向上递归地从子问题的最优解逐步构造出整个问题的最优解
3.3 最长公共子序列
1. 问题描述
给定 2 个序列: X = {x1, x2,..., xm} Y = {y1, y2,..., yn} 求 X 和 Y 的一个最长公共子序列（Longest Common Sequence）
2. 应用举例
· 抄袭代码检测系统
· 网页关键字搜索
· DNA序列匹配
· 音频识别系统
3. 问题分析
（1）前提假设
设序列 X = {x1, x2,..., xm} Y = {y1, y2,..., yn} 的最长公共子序列为 Z = {z1, z2,..., zk}
（2）符号约定
· Xi 表示 X 的前缀，即 Xi = {x1, x2,..., xi}
· Yj : Y 的前缀 Yj = {y1, y2,..., yj}
· 用 LCS(.,.) 表示计算最长公共子序列
· 用 c[i][j] 表示 Xi 和 Yj 的最长公共子序列的长度
（3）情况分析
· m = 0 或 n = 0
· xm = ym（最后元素相等）
· xm != ym（最后元素不等）
则 LCS[Xm][Yn]等于以下两者中的大者: · Xm-1 和 Yn 的最长公共子序列 LCS(Xm-1, Yn) · Xm 和 Yn-1 的最长公共子序列 LCS(Xm, Yn-1)
（4）递推公式
（5）算法描述
Algorithm 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); System.out.print(x[i]); } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); } Algorithm lcsLength(x,y,b) { m <- x.length-1; n <- y.length-1; c[1..m][0]=0; c[0][1..n]=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; } } }
（6）复杂性分析
在所考虑的子问题空间中，总共有 Θ(mn)个不同的子问题，因 此，子问题的规模是多项式级的。 采用动态规划算法自底向上迭代计算最优值时，只需考虑不同 的子问题，能提高算法的效率
3.4 凸多边形的最优三角剖分
1. 基本概念
凸多边形 : P = {v0, v1, ..., vn-1} · n条边 vivi+1（v0 = vn） · 线段 vivj（vi 与 vj 不相邻）弦 · 一条弦将多边形分割成2个多边形 : {vi, vi+1, ..., vj}, {vj, vj+1, ...,vi}
2. 三角剖分
（1）概念
将多边形分割成 互不相交的三角 形的弦的集合 T
（2）性质
· 各弦互不相交，且集合 T 已达到最大
· 恰有 n - 3 条弦和 n - 2 个三角形
3. 权函数的概念
三角形的权函数 w(·) 可以有各种不同定义方法，例如
4. 问题描述
凸多边形的所有可能三角剖分记为集合 F，找出其中权最小的三角剖分。
5. 最优子结构
如果凸多边形 T 为最优三角剖分，其分为两个部分 T1 和 T2，则 T1 和 T2 一定是子多边形的最优三角剖分，且满足:
6. 算法思路
（1）j = i
凸多边形 {vi-1, vi} 退化为一条直线，权值 t[i][j] = 0（递归出口）
（2）j > i
凸子多边形 {v-1i, vi, ..., vj} 至少有3个顶点，存在三角剖分，最优三角剖分的权值 t[i][j]
7. 递推公式
8. 复杂度分析
（1）时间复杂度
（2）空间复杂度
3.5 多边形游戏
1. 游戏玩法
（1）介绍
在 n 个顶点的多边形中，每个顶点被赋予一个整数（可负），每条边被赋予运算符 + 或 *，边依次用整数 1 到 n 编号
（2）规则
· 第 1 步，将一条边删除
· 随后 n - 1 步按如下方式操作: A. 选择一条边 E (其顶点设为 V1 和 V2) B. 用一个新顶点取代边 E 以及顶点 V1 和 V2，将由顶点 V1 和 V2 的整数值通过边 E 上的运算得到的结果赋予新顶点 C. 所有边都被删除，游戏结束 D. 游戏的得分就是所剩顶点的整数值
（3）问题
对于给定的多边形，计算最高得分
（4）举例
2. 问题分析
（1）最优子结构性质
从顶点 i 开始，长为 j (即有 j 个顶点) 的链 P(i, j)
若其最优解中最后一次合并运算发生在边 op[i + s] 处(1<=s<=j-1)，则在 op[i +s] 处原链将分割为2个子链
（2）解的递归结构
3.6 图像压缩
1. 图像变位压缩存储格式
· 将 n 个像素分割成 m 个连续段 {Si}m
·
·
2. 问题描述
确定像素序列 <p1, p2, ..., pn> 的最优分段 S'，按此分段所需的储存空间最少
3. 问题分析
（1）最优子结构性质
设 <p1, p2, ..., pn> 的最优分段为 {Si}m ，其中的第 m 个分段 Sm 的长度为 l[m]，则{Si}m-1 是子问题 <p1, p2, ..., pn-l[m]> 的最优分段
（2）递归公式
（3）复杂度分析
· 时间复杂度
· 空间复杂度
3.7 最优二叉搜索树
1. 基本概念
2. 问题描述
3. 暴力求解的结果
4. 最优子结构性质
（1）描述
（2）证明
5. 递归式
6. 复杂度分析
（1）本算法的复杂度
（2）改进算法
第4章 贪心算法
4.1 活动安排问题
1. 问题描述
有 n 个活动的集合 E = {1, 2, ... , n}，活动 i 持续时间内占用资源，不同活动会发生时间冲突而不相容。求从活动集合中选出最大的相容活动的子集合。
2. 算法描述
（1）步骤
· 先对活动按结束时间按非减序列排序
· 然后从第1项活动开始进行贪心选择
（2）部分代码
public static int greedySelector(int[] s, int[] f, boolean a[]) // 各活动的起止时间存储于数组 s 和 f 中，且按结束时间的非减序排列 { int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { //兼容则选中 a[i]=true; j=i; count++; } else a[i]=false; //不兼容 } return count; }
3. 复杂度分析
1. 不计入排序时间，算法复杂度为 O(n)
2. 计入排序时间，算法复杂度为 O(nlogn)
4. 贪心算法的正确性证明
4.2 贪心算法的基本要素
1. 贪心选择性质
2. 最优子结构性质
3. 贪心算法与动态规划的比较
（1）共同点
都具有最优子结构
（2）不同点
动态规划
保留所有子问题的解
贪心算法
只求解根据贪心策略决定下来的一个子问题的最优解，只保留一条求解路径
4.3 最优装载
1. 问题描述
有一批集装箱要装上一艘载重量为 c 的轮船。其中 集装箱 i 的重量为 wi。在不超过轮船载重量的条 件下将尽可能多的集装箱装上轮船。
2. 贪心选择性质
（1）描述
每次选择是，从剩余集装箱中重量最小的，直至总载重量为不超过容量限制的最大值。
（2）证明
3. 最优子结构性质
（1）说明
（2）证明
4. 算法描述
public static float loading(float c, float [] w, int [] 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; }
5. 复杂度分析
loading 的主要时间负载都在于排序，~ O(nlogn)
4.4 哈夫曼编码
1. 哈夫曼编码
根据字符在文件中出现的频率，建立一个用0, 1串表示各字符的最优表示方式
2. 基本思路
出现频率高的字符编码短，出现频率低的字符编码长
3. 基本概念
（1）前缀码
对字符集 C 每一个字符规定一个 0, 1 串作为其代码，且要求任一字符的代码都不是其他字符代码的前缀。 优点：译码方法简单
（2）编码树
前缀码可表示为一棵完全二叉树（即树中任一内结点都有2个儿子结点）
（3）平均码长
（4）最优前缀码
4. 哈夫曼编码示例
5. 贪心思想
以自底向上构造表示最优前缀码的二叉树 T
6. 算法描述
7. 复杂度分析
8. 正确性证明
（1）贪心选择性质
· 描述
· 证明
（2）最优子结构
· 描述
· 证明
第5章 回溯法
5.1 回溯法的算法框架
1. 基本概念
（1）状态空间
（2）约束定义
· 显示约束
对分量的取值限定
· 隐式约束
不同分量之间的约束
（3）完备性特点
2. 问题的解空间
（1）解向量
问题的解可用 n 元向量 (x1, x2, ... xn) 表示
（2）解空间
对于一个问题实例，满足显示约束条件的所有解向量，构成了该问题实例的一个解空间
3. 几个基本概念
（1）活结点
自身已生成但其儿子还没有全部生成的结点
（2）扩展结点
活结点中，一个正在产生儿子的结点称为扩展结点
（3）死结点
不在进行扩展的结点
4. 回溯法
5. 剪枝
6. 递归回溯
7. 迭代回溯
8. 空间复杂性
回溯法在搜索过程中动态产生问题的解空间, 只保存从根结点到当前扩展结点的路径, 空间复杂度为O(h(n))
9. 两种解空间结构
（1）子集树（组合问题）
· 描述
· 递归算法
· 算法说明
（2）排列树（排列问题）
· 描述
· 递归算法
· 算法说明
5.2 装载问题
1. 问题描述
2. 问题分析
3. 解空间
子集树
4. 剪枝函数
5. 算法描述
private static void backtrack (int i) {// 搜索第i层结点 if (i > n) { // 到达叶结点 更新最优解 bestx,bestw; return; } r -= w[i]; //尝试装入i if (cw + w[i] <= c){ //装入i不能超重——约束条件 思考：为什么这里不用限界函数？？？？？？ // 搜索左子树（装入i） x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; //撤销对i的装入，为分析不装入i准备数据!!!!!!!!!! } else{ //剪枝, do nothing here } //尝试不装入i if (cw + r > bestw){ //i之后总重量w[i+1..n]要足够重————限界条件 x[i] = 0; // 搜索右子树（不装i） backtrack(i + 1); } else{ //剪枝， do nothing here } r += w[i]; }
6. 时间复杂度
O(2n)
5.3 批处理作业调度
1. 基本概念
2. 问题描述
3. 示例
4. 算法思路
5. 算法描述
public class FlowShop{ static int n; // 作业数 static int f1; // 机器1完成处理时间 static int f; // 完成时间和 static int bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间 private static void backtrack(int i) { //程序主程框架：生成 n 全排列的递归算法 if (i > n) { for (int j = 1; j <= n; j++) // 保存当前最佳 minx[j] = x[j]; bestf = f; } else for (int j = i; j <= n; j++) { //依次探测 x[i]...x[n] f1 += m[x[j]][1]; // f2[i] = ((f2[i-1]>f1) ? f2[i-1] : f1)+m[x[j]][2]; f += f2[i]; if (f < minf) { // 限界条件 MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j); } f1 -= m[x[j]][1]; f -= f2[i]; } } }
5.4 符号三角形问题
1. 问题描述
第一行有 n 个符号，计算有多少个不同的符号三角形
2. 算法设计
3. 算法思路
4. 算法描述
//搜索解空间中第 i 层子树 private static void backtrack (int t) { if ((count>half)||(t*(t-1)/2-count>half)) // +或-个数超过一半, 剪枝 return; if (t>n) sum++; // 为一个可行符号三角形，可行解个数（sum）累加 else for (int i=0;i<2;i++) { //第一行右侧增的符号为 0（“-”）或 1（“+”） p[1][t]=i; count+=i; // number of “+” 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++) // 恢复到t count-=p[j][t-j+1]; count-=i; } }
5. 复杂度分析
5.5 n皇后问题
1. 问题描述
在 n × n 格的棋盘上 放置彼此不受攻击的 n 个皇后，即任何 2 个 皇后不放在同一行或同 一列或同一斜线上
2. 解空间表示
3. 剪枝
4. 概念
5. 算法描述
5.6 0-1背包问题
1. 算法思路
2. 动态树解法
第6章 分支限界法
6.1 基本思想
1. 搜索过程
2. 常见两种分支限界法
6.2 单源最短路径问题
1. 问题描述
2. 算法过程
子主题
3. 算法思想
优先级
结点的当前路长交小者优先
数据结构
最小堆作为活结点的优先队列
4. 算法描述
public static void shortest(int v, float [] dist, int [] p) { //详细代码省略... // 核心部分的代码如下 while (true) { // 搜索问题的解空间 for (int j=1;j<=n;j++) // 顶点 i 和 j 间有边，且此路径长小于原先从源点s到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(); } }
6.3 装载问题
1. 问题描述
2. 问题分析
3. 两种思路
· 队列式分支限界
· 优先队列式分支限界
4. 队列式分支限界法
· 剪枝函数
· 算法描述
· 构造最优解
5. 优先队列式分支限界法
6.4 布线问题
1. 问题描述
2. 算法思想
3. 示例
4. 复杂度分析
6.5 0-1背包问题
1. 算法思想
2. 上界函数
private static double bound(int i) { //对i之后物品用分数背包估计上界 double cleft = c - cw; //剩余容量 double b = cp; //价值上界 while (i <= n && w[i] <= cleft) {//n表示物品总数，cleft为剩余空间 cleft -= w[i]; //w[i]表示i所占空间 b += p[i]; //p[i]表示i的价值 i++; } if (i <= n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包 return b; // b为上界函数 }
3. bbKnapsack
private static double BBKnapsack() {// 优先队列式分支限界，返回最大价值，bestx返回最优解 // 变量定义（略）... while (i != n + 1) {// 非叶结点 //检查左儿子节点：加入第i个物品 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); //检查右儿子节点：不加入第i个物品 if (up >= bestp) //上界条件 addLiveNode(up,cp, cw, i + 1, enode, false); //加入活结点优先队列 // 取下一个扩展节点 HeapNode node=(HeapNode) heap.removeMax(); cw = node.weight; cp = node.profit; up = node.upperProfit; i =node.level; } //构造当前最优解（略） ... }
算法设计与分析
第1章 算法引论
第2章 递归与分治策略
第3章 动态规划
第4章 贪心算法
第5章 回溯法
第6章 分支限界法