第十章 算法设计与分析

一 分治

对于一个规模为 n 的问题将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决。
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3. 利用该问题分解出的子问题的解可以合并为该问题的解。
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

二 动态规划

动态规划法与分治法类似，也是将要求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。

与分治法不同的是动态规划法对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重复求解。

动态规划算法的特征：

1. 最优子结构。问题的最优子结构性质使我们能够以自底向上的方式递归地从子问题的最优解构造出整个问题的最优解。
2. 重叠子问题。在用递归算法自顶向下解问题时，有些子问题被反复计算多次，动态规划法对每个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，可以直接查看结果。

三 贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。

贪心法的特征：

1. 不追求最优解，只求可行解。
2. 每一步都按贪心准则找一个解，故到 n 步后（n 为问题的规模）得到问题的所有解。如找不到所有解，则修改贪心准则，放宽贪心条件或修改算法某些细节，重新从头开始找解。
3. 每一步所找到的解是这一步中的最优解（按贪心准则来说），但每步最优解所形成的整体解并不一定最优。

四 回溯法

称为试探法，按选优条件向前探索，以达到目标。担当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。回溯法把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。 基本思想类同于：

• 图的深度优先搜索
• 二叉树的后序遍历

真题示例

试题四（共 15 分）

阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写答题纸的对应栏内。

【说明】
生物学上通常采用编辑距离来定义两个物种 DNA 序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符所需要的最小操作次数。操作有三种，分别是：插入一个字符、删除一个字符以及将一个字符修改为另一个字符。 用字符数组 str1 和 str2 分别表示长度分别为 len1 和 len2 的字符串，定义二维数组 d 记录求解编辑距离的子问题最优解，则该二维数组可以递归定义为：

【C 代码】
下面是算法的 C 语言实现。

（1）常量和变量说明

1
2
3
4

A，B：两个字符数组  
d：二维数组  
i，j：循环变量  
temp：临时变量

（2）C 程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<stdio.h>
#define N 100

char A[N]="CTGA";
char B[N]="ACGCTA";
int d[N][N];

int min(int a, int b) {
	return a < b ? a : b;
}

int editdistance(char *str1, int len1, char *str2, int len2) {
	int i,j;
	int diff;
	int temp;
	for (i=0; i<=len1; i++) {
		d[i][0]=i;
	}
	for (j=0; j<=len2; j++) {
		____(1)_____;
	}
	for (i=1; i<=len1; i++) {
		for (j=1; j<=len2; j++) {
			if (___(2)___) {
				d[i][j] = d[i-1][j-1];
			} else {
				temp = min(d[i-1][j]+1, d[i][j-1]+1);
				d[i][j] = min(temp, ___(3)____);
			}
		}
	}
	return ____(4)_____;
}

【问题 1】（8 分）
根据说明和 C 代码，填充 C 代码中的空（1）~（4）

【问题 2】（4 分）
根据说明和 C 代码，算法采用了（5）设计策略，时间复杂度为（6）（用 O 符号表示，两个字符串长度分别用 m 和 n 表示）。

【问题 3】（3 分）
已知两个字符串 A=“CTGA” 和 B=“ACGCTA”，根据说明和 C 代码，可得出这两个字符串的编辑距离为（7）。

真题答案

【问题 1】
（1）d[0][j] = j
（2）str1[i-1] == str2[j-1]
（3）d[i-1][j-1]+1
（4）d[len1][len2]

【问题 2】
动态规划，$O(m*n)$

【问题 3】
4