我的书签
添加书签
移除书签算法被公认为是计算机科学的基石，算法理论研究的是算法的设计技术和分析技术。前者回答的是“对特定的问题，如何提出一个算法来求解？”这样的问题，即如何设计一个有效的算法解决特定的问题；后者回答的是“该算法是否足够好？”，即对已设计的算法如何评价或判断其优劣，或者对求解同一个问题的多个算法如何进行比较和评价。二者是互相依存的，设计出的算法需要检验和评价，对算法的分析反过来又可以帮助改进算法的设计。
8.1 算法设计与分析的基本概念
8.1.1 算法
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列 5 个重要特性。
（1）有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（2）确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
（3）可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
（4）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
（5）输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
8.1.2 算法设计
算法设计是一件非常困难的工作，通常设计一个“好”的算法应考虑多个目标，包括正确性、可读性、健壮性和高效性等。由于实际问题各种各样，问题求解的方法千变万化，所以算法设计又是一个灵活的充满智慧的过程，需要设计人员根据实际情况具体问题具体分析。
存在多种算法设计技术（也称为算法设计策略），它们是设计算法的一般性方法。已经证明这些技术对于设计好的算法非常有用，在掌握了这些技术之后，设计新的和有用的算法会变得容易。经常采用的算法设计技术主要有分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。另外，在解决计算机领域以外的问题时，这些技术也能起到很好的指导作用。
8.1.3 算法分析
通常，求解一个问题可能会有多种算法可以选择，选择的主要标准首先是算法的正确性、可靠性、简单性和易理解性，其次是算法的时间复杂度和空间复杂度要低，这是算法分析技术的主要内容。
从基本概念上看，算法分析是指对一个算法所需要的资源进行估算，这些资源包括内存、通信带宽、计算机硬件和时间等，所需要的资源越多，该算法的复杂度就越高。不言而喻，对于任何给定的问题，设计出复杂度尽可能低的算法是设计算法时追求的重要目标。另一方面，当给定问题有很多种算法时，选择其中复杂度最低者是一个重要准则。因此，算法的复杂度分析对算法的设计和选择有重要的指导意义和实用价值。
而在计算机资源中，最重要的是时间和空间（存储器）资源，因此复杂度分析主要包括时间复杂度和空间复杂度分析。
8.1.4 算法的表示
常用的表示算法的方法有自然语言、流程图、程序设计语言和伪代码等。
（1）自然语言。其最大的优点是容易理解，缺点是容易出现二义性，并且算法通常很冗长。
（2）流程图。其优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。
（3）程序设计语言。其优点是能用计算机直接执行，缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性。此外，还要求算法设计者掌握程序设计语言及编程技巧。
（4）伪代码。伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，同时结合自然语言来表达。计算机科学家从来没有对伪代码的书写形式达成过共识。在伪代码中，可以采用最具表达力的、最简明扼要的方法来表达一个给定的算法。
考虑到下午试题的算法题不仅考核算法设计和分析技术，还同时考核算法的 C 程序设计语言实现，因此，本章采用 C 程序设计语言表示算法。
8.2 算法分析基础
8.2.1 时间复杂度
由于时间复杂度与空间复杂度分别对算法占用的时间和空间资源进行分析，计算方法相似，且空间复杂度分析相对简单一些，因此下面主要讨论时间复杂度。算法的时间复杂度分析主要是分析算法的运行时间，即算法执行所需要的基本操作数。
不同规模的输入所需要的基本操作数是不相同的，例如用同一个排序算法排序 100 个数和排序 10 000 个数所需要的基本操作数是不相同的，因此考虑特定输入规模的算法的具体操作数既是不现实的也是不必要的。在算法分析中，可以建立以输入规模 $n$ 为自变量的函数 $T(n)$ 来表示算法的时间复杂度。
即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为 3 种情况。
（1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为 $\Omega(n \lg n)$，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度的算法。
（2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它给我们提供一个保障，实际情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且对于许多算法来说，平均情况通常与最坏情况下的时间复杂度一样。
（3）平均情况。算法的平均运行时间，一般来说，这种情况很难分析。举个简单的例子，现要排序 10 个不同的整数，输入就有 $10!$ 种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下 3 个步骤进行。
① 将所有的输入按其执行时间分类。
② 确定每类输入发生的概率。
③ 确定每类输入的执行时间。
下式给出了一般算法在平均情况下的复杂度分析。
$$ T(n) = \sum_{i=1}^{m} p_i \times t_i $$
其中，$p_i$ 表示第 $i$ 类输入发生的概率；$t_i$ 表示第 $i$ 类输入的执行时间，输入分为 $m$ 类。
8.2.2 渐进符号
以输入规模 $n$ 为自变量建立的时间复杂度实际上还是较复杂的，例如 $an^2+bn+c$，不仅与输入规模有关，还与系数 $a$、$b$ 和 $c$ 有关。此时可以对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低阶项和高阶项的系数，仅考虑 $n^2$。当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。下面简单介绍 3 种常用的标准方法来简化算法的渐进分析。
（1）$O$ 记号。定义为：给定一个函数 $g(n)$，$O(g(n)) = {f(n): \text{存在正常数 } c \text{ 和 } n_0, \text{ 使得对所有的 } n \geq n_0, \text{ 有 } 0 \leq f(n) \leq cg(n)}$，如图 8-1（a）所示。$O(g(n))$ 表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界。
（2）$\Omega$ 记号。定义为：给定一个函数 $g(n)$，$\Omega(g(n)) = {f(n): \text{存在正常数 } c \text{ 和 } n_0, \text{ 使得对所有的 } n \geq n_0, \text{ 有 } 0 \leq cg(n) \leq f(n)}$，如图 8-1（b）所示。$\Omega(g(n))$ 表示一个函数集合，往往用该记号给出一个算法运行时间的渐进下界。
（3）$\Theta$ 记号。定义为：给定一个函数 $g(n)$，$\Theta(g(n)) = {f(n): \text{存在正常数 } c_1, c_2 \text{ 和 } n_0, \text{ 使得对所有的 } n \geq n_0, \text{ 有 } 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)}$，如图 8-1（c）所示。$\Theta(g(n))$ 表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界和渐进下界，即渐进紧致界。
由上述定义可知，$f(n) = \Theta(g(n))$ 当且仅当 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$。
【例 8.1】判断下列等式是否成立。
（1）$10n^2+4n+2 = O(n^2)$ （2）$10n^2+4n+2 = O(n^3)$ （3）$10n^2+4n+2 = O(n)$
（4）$10n^2+4n+2 = \Omega(n^2)$ （5）$10n^2+4n+2 = \Omega(n^3)$ （6）$10n^2+4n+2 = \Omega(n)$
（7）$10n^2+4n+2 = \Theta(n^2)$ （8）$10n^2+4n+2 = \Theta(n^3)$ （9）$10n^2+4n+2 = \Theta(n)$
解：（1）$\surd$ （2）$\surd$ （3）$\times$ （4）$\surd$ （5）$\times$ （6）$\surd$ （7）$\surd$ （8）$\times$ （9）$\times$
8.2.3 递归式
从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本节主要讨论递归算法的时间复杂度分析方法。
（1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。
【例 8.2】求 $T(n) = \begin{cases} 1 & , n=1 \ T(n-1)+n & , n>1 \end{cases}$ 的解。
解：$T(n) = T(n-1)+n$
$= T(n-2)+(n-1)+n$
$\vdots$
$= 1+2+\dots+(n-1)+n$
$= n(n+1)/2$
$= O(n^2)$
（2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。在用代换法解递归式时需要 3 个步骤：猜测解的形式；用数学归纳法证明猜测的正确性；求出使解真正有效的常数。
【例 8.3】确定 $T(n) = \begin{cases} 1 & , n=1 \ 2T(n/2)+n & , n>1 \end{cases}$ 的上界。
解：首先猜测其解为 $T(n) = O(n \lg n)$。目标是要证明 $T(n) \leq cn \lg n$，其中，$c>0$ 为常数。
然后假设这个解对 $n/2$ 成立，即 $T(n/2) \leq cn \lg(n/2)/2$。
对递归式做替换，得到 $T(n) \leq 2 \cdot cn \lg(n/2)/2 + n$
$= cn \lg n - cn + n$
$\leq cn \lg n \quad (c \geq 1)$
尽管代换法提供了一种证明递归式解的正确性的简单方法，但并不存在通用的方法来猜测递归式的正确解，这种猜测需要经验，有时甚至是创造性的。由于往往很难得到“好”的猜测，因此这种方法较难用。
（3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供“好”的猜测，然后用代换法证明。在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将树中每一层内结点的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层的总代价。当用递归式表示分治算法的时间复杂度时，递归树方法尤其有用。
【例 8.4】确定 $T(n) = \begin{cases} c & , n=1 \ 4T(n/2)+cn & , n>1 \end{cases}$ 的紧致界。
解：用递归树法求解，图 8-2（a）$\sim$（d）给出了递归树的构造过程。
将递归树每一层代价相加就可以得到递归式的解，如下式所示。
$$ T(n) = (1+2+2^2+\dots+2^{\lg n-1})cn + \Theta(n^2) $$
$$ = (2^{\lg n}-1)cn + \Theta(n^2) $$
$$ = \Theta(n^2) $$
（4）主方法。主方法也称为主定理，给出了求解以下形式的递归式的快速方法。
$$ T(n) = aT(n/b) + f(n) $$
其中，$a \geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个渐进的正函数。
【定理 8.1】（主定理）设 $a \geq 1$ 和 $b > 1$ 为常数，$f(n)$ 为函数，$T(n)$ 为定义在非负整数上的递归式，$T(n) = aT(n/b) + f(n)$，其中，$n/b$ 指 $\lfloor n/b \rfloor$ 或 $\lceil n/b \rceil$，那么 $T(n)$ 可能有如下的渐进紧致界。
（1）若对于某常数 $\varepsilon > 0$，有 $f(n) = O(n^{\log_b a - \varepsilon})$，则 $T(n) = \Theta(n^{\log_b a})$。
（2）若 $f(n) = \Theta(n^{\log_b a} \lg^k n)$，则 $T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$。
（3）若对于某常数 $\varepsilon > 0$，有 $f(n) = \Omega(n^{\log_b a + \varepsilon})$，且对于常数 $c < 1$ 与所有足够大的 $n$ 有 $af(b/n) \leq cf(n)$，则 $T(n) = \Theta(f(n))$。
【例 8.5】用主方法求解下列递归式。
（1）$T(n) = 9T(n/3)+n$
（2）$T(n) = T(2n/3)+1$
（3）$T(n) = 3T(n/4)+n \lg n$
解：（1）$a=9$，$b=3$，$f(n)=n$。$\log_b a = 2$，$f(n) = O(n^{\log_b a - \varepsilon})$，其中，$\varepsilon = 1$，属于情况（1），因此有 $T(n) = \Theta(n^{\log_b a}) = \Theta(n^2)$。
（2）$a=1$，$b=3/2$，$f(n)=1$。$\log_b a = 0$，$f(n) = \Theta(n^{\log_b a} \lg^k n)$，其中，$k=0$，属于情况（2），因此有 $T(n) = \Theta(n^{\log_b a} \lg^{k+1} n) = \Theta(\lg n)$。
（3）$a=3$，$b=4$，$f(n)=n \lg n$。$\log_b a \approx 0.793$，$f(n) = \Omega(n^{\log_b a + \varepsilon})$，其中，$\varepsilon \approx 0.207$，属于情况（3），因此有 $T(n) = \Theta(f(n)) = \Theta(n \lg n)$。
8.3 分治法
8.3.1 递归的概念
递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。在计算机算法设计与分析中，递归技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析，为此在介绍其他算法设计方法之前先讨论它。
递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体。
【例 8.6】阶乘函数。
阶乘函数可递归地定义为：
$$ n! = \begin{cases} 1 & , n=0 \ n(n-1)! & , n>0 \end{cases} $$
阶乘函数的自变量 $n$ 的定义域是非负整数。递归式的第一式给出了这个函数的一个初始值，是递归的边界条件。递归式的第二式是用较小自变量的函数值来表示较大自变量的函数值的方式来定义 $n$ 的阶乘，是递归体。$n!$ 可以递归地计算如下：
int Factorial(int num) {if (num == 0)return 1;if (num > 0)return num * Factorial(num - 1);}
8.3.2 分治法的基本思想
分治与递归就像一对孪生兄弟，经常同时应用于算法设计之中，并由此产生许多高效的算法。我们知道，任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。问题的规模越小，解题所需要的计算时间往往越少，从而较容易处理。例如，对于 $n$ 个元素的排序问题，当 $n=1$ 时，不需要任何比较；当 $n=2$ 时，只要做一次比较即可；……而当 $n$ 较大时，问题就不那么容易处理了。要想直接解决一个较大的问题，有时是相当困难的。分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。如果规模为 $n$ 的问题可分解成 $k$ 个子问题，$1 < k \leq n$，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。
一般来说，分治算法在每一层递归上都有 3 个步骤。
（1）分解。将原问题分解成一系列子问题。
（2）求解。递归地求解各子问题。若子问题足够小，则直接求解。
（3）合并。将子问题的解合并成原问题的解。
8.3.3 分治法的典型实例
以上讨论的是分治法的基本思想和一般原则，下面用一些具体例子来说明如何针对具体问题用分治思想来设计有效算法。
【例 8.7】归并排序。
归并排序算法是成功应用分治法的一个完美的例子，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列进行排序，最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照上述分治算法的 3 个步骤进行。
（1）分解。将 $n$ 个元素分成各含 $n/2$ 个元素的子序列。
（2）求解。用归并排序对两个子序列递归地排序。
（3）合并。合并两个已经排好序的子序列以得到排序结果。
归并排序算法的 C 代码如下：
void MergeSort(int A[], int p, int r) {int q;if (p < r) {q = (p + r) / 2;MergeSort(A, p, q);MergeSort(A, q + 1, r);Merge(A, p, q, r);}}
函数 $\text{Merge}(A, p, q, r)$ 的 C 代码如下：
void Merge(int A[], int p, int q, int r) {int n1 = q - p + 1, n2 = r - q, i, j, k;int L[50], R[50];for (i = 0; i < n1; i++)L[i] = A[p + i];for (j = 0; j < n2; j++)R[j] = A[q + j + 1];L[n1] = INT_MAX;R[n2] = INT_MAX;i = 0;j = 0;for (k = p; k < r + 1; k++) {if (L[i] < R[j]) {A[k] = L[i];i++;} else {A[k] = R[j];j++;}}}
其中，$A$ 是数组，$p$、$q$ 和 $r$ 是下标，满足 $p \leq q < r$。$\text{Merge}$ 显然可在 $O(n)$ 时间内完成，因此合并排序算法对 $n$ 个元素进行排序所需的计算时间 $T(n)$ 满足：
$$ T(n) = \begin{cases} O(1) & , n \leq 1 \ 2T(n/2) + O(n) & , n > 1 \end{cases} $$
解此递归式可知 $T(n) = O(n \log n)$。
【例 8.8】最大子段和问题。
给定由 $n$ 个整数（可能有负整数）组成的序列 $a1, a_2, \dots, a_n$，求该序列形如 $\sum{k=i}^{j} a_k$ 的子段和的最大值。当序列中所有整数均为负整数时，其最大子段和为 0。依此定义，所求的最大值为
$$ \max \left{ 0, \max{1 \leq i \leq j \leq n} \sum{k=i}^{j} a_k \right} $$
例如，当 $(a1, a_2, a_3, a_4, a_5, a_6) = (-2, 11, -4, 13, -5, -2)$ 时，最大子段和为 $\sum{k=2}^{4} a_k = 20$。
最大子段和问题的分治策略如下。
（1）分解。如果将所给的序列 $A[1..n]$ 分为长度相等的两段 $A[1..n/2]$ 和 $A[n/2+1..n]$，分别求出这两段的最大子段和，则 $A[1..n]$ 的最大子段和有 3 种情形。
① $A[1..n]$ 的最大子段和与 $A[1..n/2]$ 的最大子段和相同。
② $A[1..n]$ 的最大子段和与 $A[n/2+1..n]$ 的最大子段和相同。
③ $A[1..n]$ 的最大子段和为 $\sum_{k=i}^{j} a_k$，且 $1 \leq i \leq n/2$，$n/2+1 \leq j \leq n$。
（2）解决。①和②这两种情形可递归求得。对于情形③，容易看出，$A[n/2]$ 与 $A[n/2+1]$ 在最优子序列中。因此可以在 $A[1..n/2]$ 中计算出 $s1 = \max{1 \leq i \leq n/2} \sum{k=i}^{n/2} a[k]$，并在 $A[n/2+1..n]$ 中计算出 $s2 = \max{n/2+1 \leq i \leq n} \sum{k=n/2}^{i} a[k]$。则 $s1+s2$ 即为出现情形③的最优值。
（3）合并。比较在分解阶段的 3 种情况下的最大子段和，取三者之中的较大者为原问题的解。
据此可设计出求解最大子段和的分治算法如下。
int MaxSubSum(int *Array, int left, int right) {int sum = 0;int i;if (left == right) { /*分解到单个整数，不可继续分解*/if (Array[left] > 0)sum = Array[left];elsesum = 0;} else {/*从 left 和 right 的中间分解数组*/int center = (left + right) / 2; /*划分的位置*/int leftsum = MaxSubSum(Array, left, center);int rightsum = MaxSubSum(Array, center + 1, right);/*计算包含 center 的最大值，判断是情形 1、情形 2 还是情形 3*/int s1 = 0;int lefts = 0;for (i = center; i >= left; i--) {lefts = lefts + Array[i];if (lefts > s1)s1 = lefts;}int s2 = 0;int rights = 0;for (i = center + 1; i <= right; i++) {rights = rights + Array[i];if (rights > s2)s2 = rights;}sum = s1 + s2;/*情形 1*/if (sum < leftsum)sum = leftsum;/*情形 2*/if (sum < rightsum)sum = rightsum;}return sum;}
其中，$\text{Array}$ 为数组，$\text{left}$ 和 $\text{right}$ 表示数组下标。对于长度为 $n$ 的序列，可以调用 $\text{MaxSubSum}(\text{Array}, 0, n-1)$ 来获得其最大子段和。
分析算法时间复杂度如下：对应分解中的①和②两种情形，需要分别递归求解，对应情形③，两个并列 for 循环的时间复杂度为 $O(n)$，因此得到下列递归式。
$$ T(n) = \begin{cases} O(1) & , n \leq 1 \ 2T(n/2) + O(n) & , n > 1 \end{cases} $$
解此递归式可知 $T(n) = O(n \log n)$。
8.4 动态规划法
8.4.1 动态规划法的基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常按照以下几个步骤进行。
（1）找出最优解的性质，并刻画其结构特征。
（2）递归地定义最优解的值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）$\sim$（3）是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤（4）可以省略。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中根据所记录的信息快速构造出一个最优解。
动态规划法是一个非常有效的算法设计技术，那么何时可以应用动态规划来设计算法呢？对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。
（1）最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。
（2）重叠子问题。重叠子问题指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。
8.4.2 动态规划法的典型实例
【例 8.9】0-1 背包问题。
有 $n$ 个物品，第 $i$ 个物品价值为 $v_i$，重量为 $w_i$，其中 $v_i$ 和 $w_i$ 均为非负数，背包的容量为 $W$，$W$ 为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题可以形式化描述如下：
目标函数为 $\max \sum_{i=1}^{n} v_i x_i$
约束条件为 $\sum_{i=1}^{n} w_i x_i \leq W$，$x_i \in {0, 1}$
满足约束条件的任一集合 $(x_1, x_2, \dots, x_n)$ 是问题的一个可行解，问题的目标是要求问题的一个最优解。考虑一个实例，假设 $n=5$，$W=17$，每个物品的价值和重量如表 8-1 所示，可将物品 1、2 和 5 装入背包，背包未满，获得价值 22，此时问题解为 $(1, 1, 0, 0, 1)$；也可以将物品 4 和 5 装入背包，背包装满，获得价值 24，此时解为 $(0, 0, 0, 1, 1)$。
表 8-1 物品的价值和重量
| 物品编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 价值 $v$ | 4 | 5 | 10 | 11 | 13 |
| 重量 $w$ | 3 | 4 | 7 | 8 | 9 |
下面根据动态规划的 4 个步骤求解该问题。
(1) 刻画 0-1 背包问题的最优解的结构
可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品 $n$，即 $xn=1$，那么其余 $x_1, x_2, \cdots, x{n-1}$ 一定构成子问题 $1,2,\cdots,n-1$ 在容量为 $W-wn$ 时的最优解。如果这个最优解不包含物品 $n$，即 $x_n=0$，那么其余 $x_1, x_2, \cdots, x{n-1}$ 一定构成子问题 $1,2,\cdots,n-1$ 在容量为 $W$ 时的最优解。
(2) 递归定义最优解的值
根据上述分析的最优解的结构递归地定义问题最优解。设 $c[i,w]$ 表示背包容量为 $w$ 时 $i$ 个物品导致的最优解的总价值，得到下式。显然，问题要求 $c[n,W]$。
(3) 计算背包问题最优解的值
基于上述递归式，以自底向上的方式计算最优解的值，C代码如下：
int** KnapsackDP(int n,int W,int* Weights,float* Values){int i,w;/*为二维数组申请空间*/int** c = (int **)malloc(sizeof(int *)*(n + 1));for (i = 0; i <= n; i++)c[i] = (int *)malloc(sizeof(int)*(W + 1));/*初始化二维数组*/for(w = 0;w <= W;w++)c[0][w] = 0;for(i = 1;i <= n;i++){c[i][0] = 0;for(w = 1;w <= W;w++){if(Weights[i - 1] <= w){ /*如果背包剩余重量大于物品重量*/if(Values[i - 1] + c[i - 1][w - Weights[i - 1]] > c[i - 1][w]){ /*重量为w的背包中放入该物品*/c[i][w] = Values[i - 1] + c[i - 1][w - Weights[i - 1]];}else{/*重量为w的背包中不放入该物品*/c[i][w] = c[i - 1][w];}}}}return c;}
上述C代码的时间复杂度为 $O(nW)$。表8-2给出了上述实例填表的信息，从表中可以很容易地看出最优解的值为 $24$。
(4) 根据计算的结果构造问题最优解
根据上一步计算的 $c$ 数组很容易构造问题的最优解。判断 $c[i,w]$ 与 $c[i-1,w]$ 的值是否相等，若相等，则说明 $x_i=0$，否则为 $1$。得到最优解的C代码如下：
void OutputKnapsackDP(int n,int W,int *Weights,float *Values,int **c){int x[n];int i;for(i = n;i > 1;i--){if(c[i][W] == c[i - 1][W]) /*重量为W的最优选择的背包中不包含该物品*/x[i - 1] = 0;else{x[i - 1] = 1;W = W - Weights[i-1]; /*更新背包目前的最大容量*/}}if(c[1][W] == 0) /*第一个物品不放入背包*/x[0] = 0;else /*第一个物品放入背包*/x[0] = 1;for(i = 0;i < n;i++)if(x[i] == 1)printf("Weigh: %d,Value: %f\n",Weights[i],Values[i]);}
构造最优解的时间复杂度为 $O(n)$。在上述例子中，$C[5,17]=24 \ne C[4,17]=21$，$x_5=1$；$C[4,8]=11 \ne C[3,8]=10$，$x_4=1$；$C[2,0]=C[2,0]=C[1,0]=0$，$x_3=x_2=x_1=0$，因此最优解为 $(0,0,0,1,1)$。
【例 8.10】最长公共子序列（LCS）
非形式化地讲，子序列是指从给定序列中随意地（不一定是连续的）去掉若干元素（可能一个也不去掉）后所形成的序列。令序列 $X=x1x_2\cdots x_m$，序列 $Y=y_1y_2\cdots y_k$ 是 $X$ 的子序列，存在 $X$ 的一个严格递增下标序列 $
给定两个序列 $X$ 和 $Y$，称序列 $Z$ 是 $X$ 和 $Y$ 的公共子序列，是指 $Z$ 同时是 $X$ 和 $Y$ 的子序列。最长公共子序列问题定义为：给定序列 $X=x_1x_2\cdots x_m$ 和序列 $Y=y_1y_2\cdots y_n$，求这两个序列的最长公共子序列。
如果用穷举法求解该问题，列举出 $X$ 的所有子序列，一一检查其是否是 $Y$ 的子序列，并随时记录所发现的公共子序列，最终求出最长公共子序列，时间复杂度为 $O(2^m n)$，是指数级的时间复杂度，对于长序列来说不可行。而动态规划法可以有效地求解最长公共子序列问题。
(1) 刻画最长公共子序列问题的最优子结构
定理8.2证明了LCS具有最优子结构。
【定理 8.2】 LCS 的最优子结构。设 $X=x_1x_2\cdots x_m$ 和 $Y=y_1y_2\cdots y_n$ 是两个序列，$Z=z_1z_2\cdots z_k$ 是 $X$ 和 $Y$ 的一个最长公共子序列。
① 如果 $xm=y_n$，那么 $z_k=x_m=y_n$，且 $Z{k-1}$ 是 $X{m-1}$ 和 $Y{n-1}$ 的一个最长公共子序列。
② 如果 $xm \ne y_n$，那么 $z_k \ne x_m$，蕴含着 $Z$ 是 $X{m-1}$ 和 $Y$ 的一个最长公共子序列。
③ 如果 $xm \ne y_n$，那么 $z_k \ne y_n$，蕴含着 $Z$ 是 $X$ 和 $Y{n-1}$ 的一个最长公共子序列。
(2) 递归定义最优解的值
设 $l[i,j]$ 表示序列 $X_i$ 和 $Y_j$ 的最长公共子序列的长度，如果 $i=0$ 或 $j=0$，则其中有一个序列长度为 $0$，因此LCS长度为 $0$。由LCS的最优子结构可导出以下递归式。
l[i,j]=\begin{cases}0&,i=0\text{或}j=0\l[i-1,j-1]+1&,i,j>0\text{且}x_i=y_j\\max(l[i-1,j],l[i,j-1])&,i,j>0\text{且}x_i\ne y_j\end{cases}
(3) 计算最优解的值
根据上述递归式自底向上地求出最优解的值。将 $l[i,j]$ 的值存储在表 $l[1..m,1..n]$ 中，以行为主序从左到右计算表 $l$ 中的元素，同时维持表 $b[1..m,1..n]$，用其中的元素 $b[i,j]$ 记录使得 $l[i,j]$ 取最优值的最优子结构。以下给出该算法的C代码，分别用 str1 和 str2 表示序列 $X$ 和 $Y$。
int** Lcs_Length(const char* str1,const char* str2,int str1_length,int str2_length){int i,j;/*为矩阵l、b分配空间*/int** l = (int **)malloc(sizeof(int *)*(str1_length + 1));int** b = (int **)malloc(sizeof(int *)*(str1_length + 1));for (i = 0; i <= str1_length; i++){l[i] = (int *)malloc(sizeof(int)*(str2_length + 1));b[i] = (int *)malloc(sizeof(int)*(str2_length + 1));}/*初始化矩阵*/for(i = 1;i <= str1_length;i++)l[i][0] = 0;for(i = 0;i <= str2_length;i++)l[0][i] = 0;for(i = 1;i <= str1_length;i++){for(j = 1;j <= str2_length;j++){if(str1[i - 1] == str2[j - 1]){l[i][j] = l[i - 1][j - 1] + 1;b[i][j] = 0; /* 0代表指向右上方的箭头 */}else if(l[i - 1][j] >= l[i][j - 1]){l[i][j] = l[i - 1][j];b[i][j] = 1; /* 1代表指向上方的箭头 */}else{l[i][j] = l[i][j - 1];b[i][j]=2; /* 2代表指向右方的箭头 */}}}return b;}
从上述C代码可知，算法的时间复杂度为 $O(mn)$。根据上述算法，已知 $X=ABCBDAB$ 和 $Y=BDCABA$，则对应的表 $l$ 和 $b$ 如图8-3所示。
(4) 构造最优解
用表 $b$ 中的信息构造 $X$ 和 $Y$ 的一个LCS。从 $b[m,n]$ 开始，在表中沿着箭头的方向跟踪，当 $b[i,j]=”\nwarrow”$ 时，表示 $x_i=y_j$ 为LCS中的元素，C代码如下所示，分别用 str1 和 str2 表示序列 $X$ 和 $Y$。在图8-3所示的例子中，过程 OutputLCS 将产生以下输出：BCBA。
void OutputLcs(const char *str1,const int** b,int str1_length,int str2_length){if(str1_length == 0||str2_length == 0) /*两个字符串中任何一个长度为零*/return;if(b[str1_length][str2_length] == 0){ /*箭头指向右上*/OutputLcs(str1,b,str1_length - 1,str2_length - 1);printf("%c",str1[str1_length - 1]);}else if(b[str1_length][str2_length] == 1) /*箭头指向上*/OutputLcs(str1,b,str1_length-1,str2_length);else /*箭头指向右*/OutputLcs(str1,b,str1_length,str2_length-1);}
8.5 贪心法
8.5.1 贪心法的基本思想
作为一种算法设计技术，贪心法是一种简单的方法。和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换而言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。举一个简单的贪心法例子，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在采用贪心法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为 $1$、$5$ 和 $11$ 单位的硬币，而希望找回总额为 $15$ 单位的硬币，按贪心算法，应找 $1$ 个 $11$ 单位面值的硬币和 $4$ 个 $1$ 单位面值的硬币，共找回 $5$ 个硬币。但最优的解答应是 $3$ 个 $5$ 单位面值的硬币。
我们知道，贪心算法并不总能得到最优解，那么对于一个具体的问题，如何得知是否可以用贪心法来求解以及能否得到问题的最优解呢？这个问题很难得到肯定的回答。但是，从许多可以用贪心法求得最优解的问题中看到，这类问题一般具有两个重要的性质。
(1) 最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
(2) 贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。
8.5.2 贪心法的典型实例
【例 8.11】活动选择问题
活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时如何选择最大的相容活动集合。假设有一个需要使用某一资源（如教室等）的 $n$ 个活动组成的集合 $S={a1, a_2, \cdots, a_n}$，该资源一次只能被一个资源占用。每个活动 $a_i$ 有一个开始时间 $s_i$ 和结束时间 $f_i$，且 $0 \le s_i \le f_i < \infty$。一旦被选择后，活动 $a_i$ 就占据半开时间区间 $[s_i, f_i)$。如果两个活动 $a_i$ 和 $a_j$ 的时间区间互不重叠，则称活动 $a_i$ 和 $a_j$ 是兼容的。活动选择问题就是要选择出一个由互相兼容的活动组成的最大子集合。考虑表8-3中的活动集合，其中各活动已经按结束时间的单调递增顺序进行了排序。从表中可以看到，子集 ${a_3, a_9, a{11}}$ 由相互兼容的活动组成。然而，它不是最大的子集，子集 ${a1, a_4, a_8, a{11}}$ 更大。事实上，${a1, a_4, a_8, a{11}}$ 是一个最大的相互兼容活动子集。另外，还有一个最大子集是 ${a2, a_4, a_9, a{11}}$。
经分析，该问题具有最优子结构，可以用动态规划法求解。但同时该问题还具有贪心选择性质，因此可以用贪心法更简单地求解。
定义集合 $S{ij}={a_k \in S: f_i \le s_k < f_k \le s_j}$。为了完整地表示问题，加入两个虚拟活动 $a_0$ 和 $a{n+1}$，其中，$f0=0$，$s{n+1}=\infty$，这样 $S=S_{0,n+1}$。
【定理 8.3】 对于任意非空子问题 $S{ij}$，设 $a_m$ 是 $S{ij}$ 中具有最早结束时间的活动。
那么，(1) 活动 $am$ 在 $S{ij}$ 的某个最大兼容活动子集中。
(2) 子问题 $S{im}$ 为空，所以选择 $a_m$ 将使 $S{mj}$ 为唯一可能非空的子问题。
（证明略）
假设对 $n$ 个活动按其结束时间单调递增进行了排序，排序的时间复杂度为 $O(n\lg n)$。下面给出解决活动选择问题的贪心算法的递归形式和迭代形式。
递归贪心算法：
int OptimalSubset[100];/*递归贪心算法*/int RecursiveActivitySelector(int* s,int *f,int index,int n){ /*s[0]和f[0]为0,活动开始时间和结束时间从下标1开始存储*/int m = index + 1;static int activity_number = 0;while(m <= n && s[m] <= f[index]) /*寻找开始时间晚于index结束的活动*/m++;if(m <= n){OptimalSubset[activity_number++] = m; /*选择找到的活动*/RecursiveActivitySelector(s,f,m,n); /*以活动m的结束时间为基准继续寻找*/}elsereturn activity_number;}
迭代贪心算法：
int GreedyActivitySelector(int *s,int *f,int n){int activity_number = 0;OptimalSubset[activity_number++] = 1; /*选择活动1*/int index = 1;int m;for(m = 2;m <= n;m++){if(s[m] >= f[index]){ /*寻找开始时间晚于index结束的活动*/OptimalSubset[activity_number++] = m; /*选择找到的活动*/index = m; /*继续寻找*/}}return activity_number;}
根据分析，递归贪心算法和迭代贪心算法都能在 $O(n)$ 的时间复杂度内完成。
【例 8.12】背包问题
背包问题的定义与0-1背包问题类似，但是每个物品可以部分装入背包，即在0-1背包问题中，$x_i=0$ 或者 $x_i=1$；而在背包问题中，$0 \le x_i \le 1$。
为了更好地分析该问题，考虑一个例子：$n=5$，$W=100$，表8-4给出了各个物品的重量、价值和单位重量的价值。假设物品已经按其单位重量的价值从大到小排好序。
为了得到最优解，必须把背包放满。现在用贪心策略求解，首先要选出度量的标准。
(1) 按最大价值先放背包的原则。
此时，先放物品 $1$ 和 $4$，获得价值 $65+60=125$，背包还剩容量 $100-30-50=20$，此时物品 $5$ 是价值最大的，但其重量为 $40$，不能全部放入背包。而且一般将物品 $2$ 和 $3$ 放入背包比把物品 $5$ 的一半放入背包能获得更大的价值。因此把物品 $2$ 放入背包，得到价值 $125+20=145$，剩余容量 $20-10=10$。此时可再放入物品 $3$ 的 $1/3$，得到总价值 $145+1.5 \times 10=160$，对应的解为 ${1, 1, 1/3, 1, 0}$。
(2) 按最小重量先放背包的原则。
此时，将物品 $2$、$3$、$1$ 和 $5$ 放入背包中，刚好装满，得到价值 $20+30+65+40=155$，对应的解为 ${1, 1, 1, 0, 1}$。
(3) 按最大单位重量价值先放背包的原则。
此时，将物品 $1$、$2$ 和 $3$ 放入背包中，得到价值 $65+20+30=115$，剩余容量 $100-30-10-20=40$。此时可再放入物品 $4$ 的 $4/5$，得到总价值 $115+4/5 \times 60=163$，对应的解为 ${1, 1, 1, 4/5, 0}$。可以证明，该解为问题的最优解，因此用贪心法求解背包问题，应根据该原则来放置物品。
假设对 $n$ 个物品按其单位重量价值从大到小进行了排序，排序的时间复杂度为 $O(n\lg n)$。
下面给出用贪心法解决背包问题的C代码。
int * GreedyKnapsack(int n,int W,int* Weights,float* Values,float *VW){int i;/*分配空间及初始化*/float* x = (float*)malloc(sizeof(float)*n);for(i = 0;i < n;i++)x[i] = 0;for(i = 0;i < n;i++)if(Weights[i] <= W){ /*如果背包剩余容量可以装下该物品*/x[i] = 1;W = W - Weights[i];}elsebreak;if(i < n){ /*如果还有物品可以部分装入背包中*/x[i] = W / (float)Weights[i];}return x;}
8.6 回溯法
回溯法有”通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时要回溯到根，且根结点的所有子树都已被搜索遍才结束；而用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法，它适用于解一些组合数较大的问题。
8.6.1 回溯法的算法框架
1. 问题的解空间
在应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。例如，对于有 $n$ 种可选择物品的0-1背包问题，其解空间由长度为 $n$ 的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。当 $n=3$ 时，其解空间是 ${(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1)}$。
定义了问题的解空间后，还应将解空间很好地组织起来，使得用回溯法能方便地搜索整个解空间。通常将解空间表示为树或图的形式。例如，对于 $n=3$ 时的0-1背包问题，其解空间用一棵完全二叉树表示，如图8-4所示。
解空间树的第 $i$ 层到第 $i+1$ 层边上的标号给出了变量的值。从树根到叶子的任一路径表示解空间的一个元素。例如，从根结点到结点 $H$ 的路径对应于解空间中的元素 $(1,1,1)$。
2. 回溯法的基本思想
在确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。
例如，对于 $n=3$ 时的0-1背包问题，考虑下面的具体实例：$w=[16,15,15]$，$p=[45,25,25]$，$c=30$。其中，$w$ 表示物品的重量，$p$ 表示物品的价值，$c$ 表示背包能够容纳的最大重量。从图8-4的根结点开始搜索其解空间。
(1) 开始时根结点是唯一的活结点，也是当前的扩展结点。在这个扩展结点处，按照深度优先策略移至结点 $B$ 或结点 $C$。假设选择先移至结点 $B$，此时结点 $A$ 和结点 $B$ 是活结点，结点 $B$ 成为当前的扩展结点。由于选取了 $w_1$（结点 $A$ 到 $B$ 的边上标记为 $1$，表示选择物品），故在结点 $B$ 处剩余背包容量是 $r=14$，获取的价值是 $45$。
(2) 从结点 $B$ 处可以移至结点 $D$ 或 $E$。由于移至结点 $D$ 需要 $w_2=15$ 的背包容量，而现在的背包容量是 $r=14$，故移至结点 $D$ 导致一个不可行的解。而搜索至结点 $E$ 不需要占用背包容量（结点 $B$ 到结点 $E$ 的边上标记为 $0$，表示不需要选择物品），因此是可行的。从而选择移至结点 $E$，此时 $E$ 成为新的扩展结点，结点 $A$、$B$ 和 $E$ 是活结点。在结点 $E$ 处，$r=14$，获取的价值为 $45$。
(3) 从结点 $E$ 处可以移至结点 $J$ 或 $K$。移至结点 $J$ 导致一个不可行解，而移至结点 $K$ 是可行的，于是移至结点 $K$，它成为一个新的扩展结点。由于结点 $K$ 是一个叶子结点，故得到一个可行解，这个解对应的价值为 $45$。解 $x$ 的取值是由根结点到叶子结点 $K$ 的路径唯一确定的，即 $x=(1,0,0)$。由于在结点 $K$ 处已不能再向纵深扩展，所以结点 $K$ 成为死结点。返回到结点 $E$，此时在 $E$ 处也没有可扩展的结点，它也成为一个死结点。
(4) 返回结点 $B$ 处，结点 $B$ 同样成为死结点，从而结点 $A$ 再次成为当前扩展结点。结点 $A$ 还可以继续扩展，从而达到结点 $C$。此时 $r=30$，获取的价值为 $0$。
(5) 从结点 $C$ 可移至结点 $F$ 或 $G$。假设移至结点 $F$，它成为新的扩展结点。结点 $A$、$C$ 和 $F$ 是活结点。在结点 $F$ 处，$r=15$，获取的价值为 $25$。从结点 $F$ 移至结点 $L$ 处，此时 $r=0$，获取的价值为 $50$。由于 $L$ 是一个叶子结点，而且是迄今为止找到的获取价值最高的可行解，因此记录这个可行解。结点 $L$ 不可扩展，返回到结点 $F$ 处。
按此方式继续搜索，可搜索整个解空间。搜索结束后找到的最好解就是0-1背包问题的最优解。
综上所述，运用回溯法解题通常包含以下3个步骤。
(1) 针对所给问题，定义问题的解空间。 (2) 确定易于搜索的解空间结构。 (3) 以深度优先的方式搜索解空间。
3. 回溯法的算法框架
回溯法的算法框架有非递归和递归两种方式。
非递归方式：
BackTracking(X)1 计算解X的第一个元素的候选集合S2 k ← 13 while k > 0 do4 while S_k ≠ Φ do5 x_k ← S_k中的下一个元素6 S_k ← S_k - {x_k}7 if X = {x_1,x_2,…,x_k}是问题的解8 then 输出X9 k ← k + 110 计算解X的第k个元素的候选集合S_k11 k ← k - 112 return
递归方式：
BackTrackingDFS(X,k)1 if X=(x_1,x_2,…,x_k)是问题的解2 then 输出X3 else k ← k + 14 计算解X的第k个元素的候选集合S_k5 while S_k ≠ Φ do6 x_k ← S_k中的下一个元素7 S_k ← S_k - {x_k}8 BackTrackingDFS(X,k)9 return
4. 回溯法的限界函数
问题的解空间往往很大，为了有效地进行搜索，需要在搜索的过程中对某些结点进行剪枝，而对哪些结点进行剪枝，需要设计限界函数来判断。因此，限界函数的设计是回溯法的一个核心问题，也是一个很难的问题。设计限界函数的通用的指导原则是尽可能多和尽可能早地”杀掉”不可能产生最优解的活结点。好的限界函数可以大大减少问题的搜索空间，从而大大提高算法的效率。下面通过例子来说明。
8.6.2 回溯法的典型实例
【例 8.13】0-1背包问题
0-1背包问题的定义如例8.9所示。
图8-4给出了0-1背包问题的一个解空间树的示例。在该问题中，目标是为了得到最大的价值，因此可以”杀掉”那些不可能产生最大价值的活结点。那么，如何判断哪些结点扩展后不可能产生最大价值呢？考虑贪心策略，先对所有物品按其单位重量价值从大到小排序，对搜索空间树中的某个结点，如 $F$，已经确定了某些 $X(i)$，$1 \le i \le k$，而其他的 $X(i)$，$k+1 \le i \le n$ 待定。此时可以将0-1背包问题松弛为背包问题，求从 $F$ 结点扩展下去，计算能获得的最大价值。若该价值比当前已经得到的某个可行解的值要小，则该结点不必再扩展。
若所有物品已经按其单位重量价值从大到小排序。假设前 $k$（包含 $k$）个物品是否放入背包已经确定，现在考虑在当前背包的剩余容量下，若是背包问题，那么能获得的最大价值是多少？即求背包中物品的价值上界。C代码如下：
float Bound(float *Values,int* Weights,float * VW,int n,int W,float Profit_Gained,int Weight_Used,int k){/*Profit_Gained、Weight_Used、k分别为当前已经获得的价值、背包的重量、已经确定的物品*/int i;for(i = k + 1;i < n;i++){if(Weight_Used+Weights [i] <= W){Profit_Gained += Values[i];Weight_Used += Weights[i];}else{Profit_Gained += VW[i]*(W - Weight_Used);Weight_Used = W;return Profit_Gained;}}return Profit_Gained;}int * Knapsack(float *Values,int* Weights,float * VW,int n,int W){/*Values为物品的价值数组，Weights为物品的重量数组，VW为物品Values/Weights的数组，W为背包的最大容量*/int current_weight = 0;float current_profit = 0;int Weight = 0;float Profit = -1;int index = 0;/*为数组X、Y分配空间*/int* X = (int*)malloc(sizeof(int)*n);int* Y = int*)malloc(sizeof(int)*n);while(1){while(index < n && current_weight + Weights[index] <= W){current_profit += Values[index];current_weight += Weights[index];Y[index] = 1;index++;}if(index >= n){Weight = current_weight;Profit = current_profit;index = n;int i;for(i = 0;i < n;i++)X[i] = Y[i];}elseY[index] = 0;while (Bound(Values,Weights,VW,n,W,current_profit,current_weight,index) <= Profit){while(index != 0 && Y[index] != 1){ //向前回溯index--;}if(index == 0){ //输出结果return X;}Y[index] = 0;current_profit -= Values[index];current_weight -= Weights[index];}index++;}}
其中，$W$、$n$、Weights、Values、Weight、Profit 和 $X$ 分别表示背包的总容量、物品个数、重量数组、价值数组、获得最大价值时背包的重量、背包获得的最大价值和问题的最优解。
假设 $n=8$，$W=110$，物品的价值和重量如表8-5所示。
则根据上述C代码得到如图8-5所示的搜索空间树。
图8-5所示树中的结点内若有数据，则上面表示背包当前的重量，下面表示背包当前的价值；结点内若无数据，则旁边的数据表示在现有的选择下背包能获得的价值的上界。$X(i)=1$ 和 $X(i)=0$ 分别表示第 $i$ 个物品放入和不放入背包中。浅灰色结点表示对应可行解的值，根据图8-5，存在5个可行解，其值分别为139、149、151、96、159，对应的解分别为 $X_1=(1,1,1,1,1,0,0,0)$、$X_2=(1,1,1,1,0,1,0,0)$、$X_3=(1,1,1,1,0,0,1,0)$、$X_4=(1,1,1,1,0,0,0,0)$、$X_5=(1,1,1,0,1,1,0,0)$。其中，$X_5$ 为最优解，其值为 $159$。
【例 8.14】$n$ 皇后问题
这是来源于国际象棋的一个问题。$n$ 皇后问题要求在一个 $n \times n$ 格的棋盘上放置 $n$ 个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的其他任何棋子。因此，$n$ 皇后问题等价于要求在一个 $n \times n$ 格的棋盘上放置 $n$ 个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。
求解过程从空棋盘开始，设在第1行至第 $m$ 行都已经正确地放置了 $m$ 个皇后，再在第 $m+1$ 行上找合适的位置放第 $m+1$ 个皇后，直到在第 $n$ 行也找到合适的位置放置第 $n$ 个皇后，就找到了一个解。接着改变第 $n$ 行上皇后的位置，希望获得下一个解。另外，在任一行上有 $n$ 种可选的位置。开始时，位置在第1列，以后改变时，顺次选择第2列、第3列、$\cdots$、第 $n$ 列。当第 $n$ 列也不是一个合理的位置时，就要回溯，去改变前一行的位置。图8-6给出了回溯法求解4皇后问题的搜索过程。
$n$ 皇后问题的限界函数可以根据问题的定义直接设计，即任意两个皇后不在同行、同列和同一斜线上，C代码如下。
int Place(int *Column,int index){int i;for(i = 1;i < index;i++){int Column_differ = abs(Column[index] - Column[i]);int Row_differ = abs(index - i);if(Column[i] == Column[index] || Column_differ == Row_differ)/*有皇后与其在同列或同一斜线上*/return 0;}return 1; /*没有皇后与其同行、同列或同对角线*/}void N_Queue(int n){int Column_Num[n + 1];int index = 1;int i;int answer_num = 0;for(i = 1;i <= n;i++)Column_Num[i] = 0;while(index > 0){Column_Num[index]++;while(Column_Num[index] <= n && !Place(Column_Num,index)) /*寻找皇后的位置*/Column_Num[index]++;if(Column_Num[index] <= n){if(index == n){ /*最后一个皇后放置成功*/answer_num++;for(i = 1;i <= n;i++)Column_Num[index]++;}else{ /*继续寻找下一个皇后的位置*/index++;Column_Num[index] = 0;}}elseindex--; /*当前皇后无法放置，回溯至上一个皇后*/}}
8.7 分支限界法
分支限界法类似于回溯法，也是一种在问题的解空间树 $T$ 上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出 $T$ 中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法在解空间树 $T$ 上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树 $T$，而分支限界法以广度优先或以最小耗费优先的方式搜索解空间树 $T$。分支限界法的搜索策略是每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。人们已经利用分支限界法解决了大量离散最优化的实际问题。
与回溯法相似，限界函数的设计是分支限界法的一个核心问题，也是一个很难的问题。如何设计限界函数来有效地减小搜索空间是应用分支限界法要考虑的问题。
根据从活结点表中选择下一扩展结点的不同方式，可将分支限界法分为几种不同的类型。最常用的有以下两种。
(1) 队列式（FIFO，先进先出）分支限界法。队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选择下一个结点作为扩展结点。
(2) 优先队列式分支限界法。优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点作为扩展结点。
优先队列中规定的结点优先级通常用一个与该结点相关的数值 $p$ 来表示。结点优先级的高低与 $p$ 值的大小相关。最大优先队列规定 $p$ 值较大的结点优先级较高。在算法实现时，通常用一个最大堆来实现最大优先队列，用最大堆的 Deletemax 操作抽取堆中下一个结点成为当前扩展结点。类似地，最小优先队列规定 $p$ 值较小的结点优先级较高。在算法实现时，常用一个最小堆来实现最小优先队列，用最小堆的 Deletemin 操作抽取堆中下一个结点成为当前扩展结点。
例如，$n=3$ 时0-1背包问题的一个实例：$w=[16,15,15]$，$p=[45,25,25]$，$c=30$，其解空间树如图8-4所示。
用队列式分支限界法解此问题时，用一个队列来存储活结点表。算法从根结点 $A$ 出发。
(1) 初始时活结点队列为空。
(2) 结点 $A$ 是当前扩展结点，它的两个儿子结点 $B$ 和 $C$ 均为可行结点，故将这两个儿子结点按照从左到右的顺序加入活结点队列，并且舍弃当前扩展结点 $A$。
(3) 按照先进先出的原则，下一个扩展结点是活结点队列的队首结点 $B$。扩展结点 $B$ 得到其儿子结点 $D$ 和 $E$。由于 $D$ 是不可行结点，故被舍去。$E$ 是可行结点，被加入活结点队列。此时活结点队列中的元素是 $C$ 和 $E$。
(4) $C$ 成为当前扩展结点，它的两个儿子结点 $F$ 和 $G$ 均为可行结点，因此被加入活结点队列。此时活结点队列中的元素是 $E$、$F$、$G$。
(5) 扩展下一个结点 $E$，得到结点 $J$ 和 $K$。$J$ 是不可行结点，因而被舍去。$K$ 是一个可行的叶子结点，表示所求问题的一个可行解，其价值为 $45$。此时活结点队列中的元素是 $F$ 和 $G$。
(6) 当前活结点队列的队首结点 $F$ 成为下一个扩展结点。它的两个儿子结点 $L$ 和 $M$ 均为叶子结点。$L$ 表示获得价值为 $50$ 的可行解，$M$ 表示获得价值为 $25$ 的可行解。
(7) $G$ 是最后一个扩展结点，其儿子结点 $N$ 和 $O$ 均为可行叶子结点。最后活结点队列为空，算法终止。算法搜索得到最优解的值为 $50$，对应的解为 $(0,1,1)$。
8.8 概率算法
前面讨论的算法对于所有合理的输入都给出正确的输出，概率算法将这一条件放宽，把随机性的选择加入到算法中。在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。
一般情况下，概率算法具有以下基本特征。
(1) 概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列。
(2) 概率算法在运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运行路径。
(3) 概率算法的结果不能保证一定是正确的，但能限制其出错概率。
(4) 概率算法在不同的运行过程中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。
概率算法大致分为4类：数值概率算法、蒙特卡罗（Monte Carlo）算法、拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
(1) 数值概率算法。数值概率算法常用于数值问题的求解。这类算法得到的往往是近似解，且近似解的精度随计算时间的增加不断提高。在多数情况下，要计算出问题的精确解是不可能的或者是没有必要的，因此用数值概率算法可得到相当满意的解。
(2) 蒙特卡罗算法。蒙特卡罗算法用于求问题的精确解。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此，一般情况下，无法有效地判定所得到的解是否肯定正确。
(3) 拉斯维加斯算法。拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。拉斯维加斯算法找到正确解的概率随它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。
(4) 舍伍德算法。舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂度与其在平均情况下的计算复杂度有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。
8.9 近似算法
迄今为止，所有的难解问题都没有多项式时间算法，采用回溯法和分支限界法等算法设计技术可以相对有效地解决这类问题。然而，这些算法的时间性能常常是无法保证的。近似算法是解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低。近似算法是这样一个过程：虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解。为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间相差的程度。显然，这个差别越小，近似算法越具有实用性。
衡量近似算法性能最重要的标准有以下两个。
(1) 算法的时间复杂度。近似算法的时间复杂度必须是多项式阶的，这是近似算法的基本目标。
(2) 解的近似程度。近似最优解的近似程度也是设计近似算法的重要目标。近似程度与近似算法本身、问题规模，乃至不同的输入实例有关。
8.10 数据挖掘算法
1. 数据挖掘概述
在当今的大数据时代，数据挖掘、机器学习和人工智能这些名词在我们的生活、工作和学习中已经是耳熟能详的词汇。我们需要各种技术来分析爆炸式增长的各类数据，以发现隐含在这些数据中的有价值的信息和知识。作为一门交叉学科，数据挖掘利用机器学习方法对多种数据，包括数据库数据、数据仓库数据、Web数据等进行分析和挖掘。数据挖掘的核心是算法，其主要功能包括分类、回归、关联规则和聚类等。
2. 分类
分类是一种有监督的学习过程，根据历史数据预测未来数据的模型。分类的数据对象属性分为两类，一般属性和分类属性或者目标属性。对数据分类有两个步骤：学习模型和应用模型，在分类过程中，涉及到的数据包括训练数据集、测试数据集和未知数据。学习模型是指基于训练数据集采用分类算法建立学习模型。而应用模型是指应用测试数据集的数据到学习模型中，根据输出来评估模型的好坏以及将未知数据输入到学习模型中，预测数据的类型。
存在多种分类算法。决策树归纳是一种自顶向下的递归树算法，使用一种属性选择度量为树的每个非叶子节点选择待分裂的属性。ID3、C4.5 和 CART 是典型的决策树算法，它们使用不同的属性选择度量。朴素贝叶斯算法和贝叶斯信念网络基于后验概率的贝叶斯公式进行分类，前者假设类条件独立，即数据对象的各个属性之间互相独立，后者考虑属性之间的关系。后向传播（BP）算法是使用梯度下降法的神经网络方法。它搜索一组权重，对数据建模，使得数据对象的预测类型和实际类型之间的平均平方距离最小。支持向量机（SVM）是一种用于线性和非线性数据的分类算法。它把输入数据变换到较高维空间，使用称作支持向量的基本元组，从中发现分离数据的超平面。
可以用混淆矩阵来评估分类模型的质量。如对于两类问题，混淆矩阵给出真正例（True Positive）、真负例（True Negative）、假正例（False Positive）、假负例（False Negative）。基于这些量可以计算分类模型的准确率、灵敏度（召回率）、特效性、精度、F度量等。可以用显著性检验和 ROC 曲线来评价不同分类模型的好坏。
把已知类别的数据集分为训练集和测试集时，可以采用保持、随机抽样、交叉检验和自助法。而可以将多个分类模型组合起来以提高分类的质量，其中袋装、提升和随机森林是典型的组合分类方法。
3. 频繁模式和关联规则挖掘
挖掘海量数据中的频繁模式和关联规则可以有效地指导企业发现交叉销售机会、进行决策分析和商务管理等。一个典型的应用是购物篮分析，即顾客经常购买的商品集合，从而分析顾客的购买习惯。而其中，沃尔玛公司对其顾客购买数据进行分析时，发现购买尿布的客户通常也会购买啤酒，根据这一规律，他们在摆放货架时，有意的把啤酒和尿布放到一起，以便顾客购买。这就是有名的啤酒尿布故事。频繁模式时频繁出现在数据集中的模式，要求满足最小支持度阈值，如啤酒和尿布频繁的出现在同一购物篮中。关联规则是形如 $A \Rightarrow B$ 的规则，其中 $A$ 和 $B$ 表示数据集中的子集，要求 $AB$ 既要满足最小支持度阈值，还要满足最小置信度阈值。如同时购买啤酒和尿布的购物篮满足最小支持度阈值，同时 $A \Rightarrow B$ 满足最小置信度阈值。支持度和置信度的定义如下：
\text{Support}(A \Rightarrow B) = P(A \cup B)
\text{Confidence}(A \Rightarrow B) = P(B|A)
求解关联规则首先要求出数据集中的频繁模式，然后由频繁模式产生关联规则。
人们提出了多种关联规则挖掘算法：类 Apriori 算法；基于频繁模式增长的方法，如 FP-growth；使用垂直数据格式的算法，如 ECLAT。
4. 聚类
聚类是一种无监督学习过程。根据数据的特征，将相似的数据对象归为一类，不相似的数据对象归到不同的类中，这就是聚类，每个聚类也称为簇。”物以类聚，人以群分”就是聚类的典型描述。
聚类的典型算法有：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于统计模型的方法。基于划分的方法将 $n$ 个数据对象划分为 $k$ 个不相交的集合，每个集合称为一个簇。典型的算法有 $k$-均值、$k$-中心点算法等。基于层次的方法将数据对象集进行层次的分解。根据其是自底向上还是自顶向下分解，可以分为凝聚的方法和分裂的方法，而前者的典型算法是 AGNES，后者的典型算法是 DIANA。基于密度的方法基于数据对象的邻域来进行聚类分析，因此可以识别各种形状的簇，以及一个数据对象可以属于多个不同的簇，DBSCAN、OPTICS 和 DENCLUE 是其中的典型算法。基于网格的方法把对象空间量化为有限个单元，形成一个网格结构。所有的聚类操作在该网格上进行，STING 和 CLIQUE 是其中的两个算法。基于统计模型的算法将数据对象集看作多个服从不同分布的数据集构成，聚类的目的是识别出这些不同的分布的数据对象，EM 算法是其中的一个典型算法。
5. 数据挖掘的应用
数据挖掘在多个领域已有成功的应用。在银行和金融领域，可以进行贷款偿还预测和顾客信用政策分析、针对定向促销的顾客分类与聚类、洗黑钱和其他金融犯罪侦破等；在零售和电信业，可以进行促销活动的效果分析、顾客忠诚度分析、交叉销售分析、商品推荐、欺骗分析等。
8.11 智能优化算法
1. 智能优化算法概述
优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、VLSI 技术和计算机工程等。鉴于实际工程问题的复杂性、约束性、非线性、多极小、建模困难等特点，寻求一种适合于大规模并行且具有智能特征的算法已成为有关学科的一个主要研究目标和引人注目的研究方向。20世纪80年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在诸多领域得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，因而通常被称作智能优化算法，或称现代启发式算法。
2. 人工神经网络
人工神经网络（ANN）是一个以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态响应而进行信息处理。人工神经网络技术与计算机技术的结合，为人类进一步研究模拟人类智能及了解人脑思维的奥秘开辟了一条新途径。
人工神经网络是由许多人工神经元按一定规则连接构成的，其互连模式有许多种类，常见的一种分类是前馈网络和反馈网络。其中，基于 BP 算法的多层前向神经网络，成功地解决了多层神经网络中隐含层神经元连接权值的学习问题。而且，BP 算法是数据挖掘和机器学习中有监督学习的一个重要算法。
目前流行的深度学习的概念源于人工神经网络的研究。含多隐层的多层感知器就是一种深度学习结构。深度学习通过组合低层特征形成更加抽象的高层表示属性类别或特征，以发现数据的分布式特征表示。深度学习的概念由 Hinton 等人于2006年提出。基于深度置信网（DBN）提出非监督贪心逐层训练算法，为解决深层结构相关的优化难题带来希望，随后提出多层自动编码器深层结构。此外 Lecun 等人提出的卷积神经网络是第一个真正多层结构学习算法，它利用空间相对关系减少参数数目以提高训练性能。深度学习是机器学习研究中的一个新的领域，其动机在于建立、模拟人脑进行分析学习的神经网络，它模仿人脑的机制来解释数据，例如图像，声音和文本。同机器学习方法一样，深度机器学习方法也有监督学习与无监督学习之分。不同的学习框架下建立的学习模型很是不同。例如，卷积神经网络（CNNs）就是一种深度的监督学习下的机器学习模型，而深度置信网（DBNs）就是一种无监督学习下的机器学习模型。
3. 遗传算法
遗传算法是源于模拟达尔文的”优胜劣汰、适者生存”的进化论和孟德尔.摩根的遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。其本意是在人工适应系统中设计一种基于自然的演化机制。
遗传算法是建立在自然选择和群体遗传学基础上，通过自然选择、杂交和变异实现搜索的方法，其基本过程是：首先采用某种编码方式将解空间映射到编码空间（可以是位串、实数等，具体问题中，可以直接采用解空间的形式进行编码，也可以直接在解的表示上进行遗传操作，从而易于引入特定领域的启发式信息，可以取得比二进制编码更高的效率。实数编码一般用于数值优化，有序串编码一般用于组合优化），每个编码对应问题的一个解，称为染色体或个体；其次通过随机的方法产生初始解（被称为群体或种群），在种群中根据适应值或某种竞争机制选择个体（适应值就是解的满意程度，可以由外部显式适应度函数计算，也可以由系统本身产生，如由个体在种群中的存活量和繁殖量确定），再次使用各种遗传操作算子（包括杂交，变异等）产生下一代（下一代可以完全替代原种群，即非重叠种群，也可以部分替代原种群中一些较差的个体，即重叠种群），如此进化下去，直到满足期望的终止条件。遗传算法中使用适应度这个概念来度量种群中的各个个体在优化过程中有可能达到最优解的优良程度。度量个体适应度的函数称为适应度函数，适应度函数的定义一般与具体问题有关。
4. 模拟退火算法
模拟退火算法（SA）是一种求解全局优化算法。模拟退火算法的基本思想来源于物理退火过程，所谓物理退火过程包括3个阶段。
(1) 加温阶段。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。
(2) 等温阶段。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡。
(3) 冷却阶段。其目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降从而得到低能的晶体结构。
模拟退火算法的思想是：先将固体加热至熔化，再让其徐徐冷却，凝固成规整晶体。在加热固体时，固体内部的粒子随着温度的升高，粒子排列从较有序的结晶状态转变为无序的液态，这个过程称为熔解，此时内能增大；冷却时，液体粒子随着温度的徐徐降低，粒子渐趋有序，液体凝固成固体的晶态，这个过程称为退火。最后在常温时达到基态，内能减为最小。
5. 禁忌搜索算法
禁忌搜索算法（TS）是模拟人类智力过程的一种全局搜索算法，是对局部邻域搜索的一种扩展。禁忌包含两个方面的意思，一方面，当沿着产生相反结果的道路走下去时，也不会陷入一个圈套而导致无处可逃，另一方面，在必要情况下，保护措施允许被淘汰，也就是说，某种措施被强制运用时，禁忌条件就宣布无效。
禁忌搜索算法的基本思想是：首先确定一个初始可行解 $x$，$x$ 可以从一个启发式算法获得或在可行解集合 $X$ 中任意选择；定义可行解 $x$ 的邻域移动集 $S(x)$，从邻域移动集中挑选一个能改进当前解 $x$ 的移动 $x’ \in S(x)$，再从新解 $x’$ 开始，重复搜索，如果邻域移动集中只能接受比前一个可行解 $x$ 更好的解，搜索就可能陷入循环。为了避免陷入循环和局部最优，构造一个短期循环记忆表即禁忌表来存储刚刚进行过的 $|T|$（$|T|$ 为禁忌表长度）个邻域移动，这些移动称为禁忌移动，对于当前的移动，在以后的 $|T|$ 次循环内是禁止的，以避免回到原始解，$|T|$ 次后释放该移动。禁忌表是一个循环表，搜索过程中被循环地修改使禁忌表始终保存着 $|T|$ 个移动，当迭代中所发现的最好解无法改进或无法离开时，算法停止。
从上述描述中可以看到，禁忌搜索算法是从一个初始可行解出发，选择一系列使目标函数值减少最多（假设求极小值问题）的特定搜索方向（即移动）作为试探，同时为了避免陷入局部最优解，禁忌搜索采用了一种灵活的”记忆”技术，即禁忌表来对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。禁忌表中保存了最近若干次迭代过程中所实现的移动，凡是处于禁忌表中的移动，在当前迭代过程中是不允许实现的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解，从而防止了循环，帮助算法摆脱局部最优解。另外，为了尽可能不错过产生最优解的”移动”，禁忌搜索算法采用藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。
6. 蚁群算法
蚂蚁是一种群居类动物，常常成群结队地出现于人类的日常生活环境中。科学工作者发现，蚂蚁的个体行为极其简单，群体却表现出极其复杂的行为特征，能够完成复杂的任务。蚂蚁还能够适应环境的变化，表现在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径等。
蚂蚁之所以能够”闻糖”而聚，是因为蚂蚁释放的化学信息物质——信息素和生物学特性所决定的。通过观察，人类发现蚂蚁个体之间是通过信息素进行信息传递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，与个体之间的信息交流与相互协作起着重要的作用。基于此，相关学者提出了一系列的蚁群优化（ACO）算法。
蚁群算法的原理：蚂蚁在寻找食物或者寻找回巢的路径中，会在它们经过的地方留下一些信息素，而信息素能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动（具体表现在后到的蚂蚁选择有信息素的路径的可能性，比选择没有信息素的路径的可能性大得多），而后到者留下的信息素会对原有的信息素进行加强，并如此循环下去。这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大（因为残留的信息素浓度较大）。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。这种行为表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后到者选择该路径的概率就越大，因此距离近的食物源会吸引越来越多的蚂蚁，信息素浓度的增长速度就会越快，同时通过这种信息的交流，蚂蚁也就寻找到食物与蚁穴之间的最短路径了。
蚁群算法的模型：蚁群算法的主要根据是信息正反馈原理和某种启发式算法的有机结合，其优化过程主要包括选择、更新以及协调3个过程。在选择过程中，信息素浓度越高的路径被选择的概率越大；在更新过程中，路径上的信息素随蚂蚁的经过而增长，同时也随时间的推移而挥发；在协调过程中，蚂蚁之间通过信息素进行信息交流相互协作。在选择和更新过程中，较好的解（较短的路径）通过路径上的信息素得到加强，从而引导下一代蚂蚁向较优解邻域搜索使算法收敛，同时更新过程的信息素挥发又使得算法具有探索能力增加解的多样性，使得算法不易陷入局部最优。
7. 粒子群优化算法
粒子群算法的基本思想：鸟群觅食飞行时，在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适宜的距离。通过对类似生物群体行为的研究，发现生物群体中存在着一种信息共享机制，为群体的进化提供了一种优势，这就是基本粒子群算法形成的基础。
后来，有学者提出了粒子群优化算法（PSO）。PSO 算法将鸟群运动模型中的栖息地类比为所求问题的解空间中可能解的位置，通过个体间的信息传递，引导整个群体向可能解的方向移动，增加发现较好解的可能性。群体中的鸟被抽象为一个个没有质量、没有形状的”粒子”，通过这些”粒子”的相互协作和信息共享，在解空间中寻找最优解。
在 PSO 算法中，每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，我们称之为”粒子”。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值，并且知道自己到目前为止发现的最好位置和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置。这个可以看作是粒子的同伴的经验。每个粒子根据下列信息改变自己的当前位置：① 当前位置；② 当前速度；③ 当前位置与自己最好位置之间的距离；④ 当前位置与自身的群体最好位置之间的距离。飞行经验是指该粒子本身所找到的最优位置，称之为个体极值；同伴飞行经验是指该粒子周围的粒子目前找到的最优解，称之为群体极值。当以整个种群为同伴时，算法称之为全局粒子群算法；当同伴只取种群的一部分粒子时，则形成了局部粒子群算法。PSO 算法中所有粒子均有一个适应值，通常由目标函数决定，另外每个粒子均有一个速度决定它们飞翔的方向与距离，然后粒子群追随当前的最优粒子在解空间中搜索。PSO 算法由随机初始化形成的粒子而组成的一个种群，以迭代的方式进行搜索而得到最优解。
第9章 数据库技术基础
数据库技术是研究数据库的结构、存储、设计、管理和应用的一门软件学科。数据库系统本质上是一个用计算机存储信息的系统。数据库管理系统是位于用户与操作系统之间的一层数据管理软件，其基本目标是提供一个可以方便、有效地存取数据库信息的环境。数据库就是信息的集合，它是收集计算机数据的仓库或容器，系统用户可以对这些数据执行一系列操作。设计数据库系统的目的是为了管理大量信息，给用户提供数据的抽象视图，即系统隐藏有关数据存储和维护的某些细节。对数据的管理涉及信息存储结构的定义、信息操作机制的提供、安全性保证，以及多用户对数据的共享问题。
本章主要介绍一些数据库的背景知识和基本概念，使读者了解数据库的基本内容，形成数据库系统的总体框架，了解数据库系统在计算机系统中的地位以及数据库系统的功能。
9.1 基本概念
9.1.1 数据库与数据库系统
数据是描述事物的符号记录，它具有多种表现形式，可以是文字、图形、图像、声音和语言等。信息是现实世界事物的存在方式或状态的反映。信息具有可感知、可存储、可加工、可传递和可再生等自然属性，信息已是社会各行各业不可缺少的资源，这也是信息的社会属性。数据是信息的符号表示，而信息是具有特定释义和意义的数据。
数据库系统（DataBase System，DBS）是一个采用了数据库技术，有组织地、动态地存储大量相关数据，方便多用户访问的计算机系统。广义上讲，DBS 是由数据库、硬件、软件和人员组成的。
(1) 数据库（DataBase，DB）。数据库是统一管理的、长期储存在计算机内的、有组织的相关数据的集合。其特点是数据间联系密切、冗余度小、独立性较高、易扩展，并且可为各类用户共享。
(2) 硬件。硬件是构成计算机系统的各种物理设备，包括存储数据所需的外部设备。硬件的配置应满足整个数据库系统的需要。
(3) 软件。软件包括操作系统、数据库管理系统及应用程序。数据库管理系统简称 DBMS，它是数据库系统的核心软件，需要在操作系统的支持下工作，解决如何科学地组织和储存数据，如何高效地获取和维护数据。其主要功能包括数据定义功能、数据操纵功能、数据库的运行管理和数据库的建立与维护。
(4) 人员。人员主要有4类。第一类为系统分析员和数据库设计人员，系统分析员负责应用系统的需求分析和规范说明，他们和用户及数据库管理员一起确定系统的硬件配置，并参与数据库系统的概要设计；数据库设计人员负责数据库中数据的确定、数据库各级模式的设计。第二类为应用程序员，负责编写使用数据库的应用程序，这些应用程序可对数据进行检索、建立、删除或修改。第三类为最终用户，他们应用系统的接口或利用查询语言访问数据库。第四类用户是数据库管理员（Data Base Administrator，DBA），负责数据库的总体信息控制。DBA 的具体职责包括决定数据库中的信息内容和结构；决定数据库的存储结构和存取策略；定义数据库的安全性要求和完整性约束条件；监控数据库的使用和运行；改进数据库的性能；重组和重构数据库，以提高系统的性能。
9.1.2 数据库管理系统的功能
数据库管理系统（DataBase Management System，DBMS）主要实现对共享数据有效地组织、管理和存取，故 DBMS 应具有以下六个方面的功能。
1. 数据定义
DBMS 提供数据定义语言（Data Definition Language，DDL），用户可以对数据库的结构进行描述，包括外模式、模式和内模式的定义；数据库的完整性定义；安全保密定义，如口令、级别和存取权限等。这些定义存储在数据字典中，是 DBMS 运行的基本依据。
2. 数据库操作
DBMS 向用户提供数据操纵语言（Data Manipulation Language，DML），实现对数据库中数据的基本操作，例如检索、插入、修改和删除。DML分为两类，即宿主型和自含型。所谓宿主型是指将 DML 语句嵌入某种主语言（如 C、COBOL 等）中使用；自含型是指可以单独使用 DML 语句，供用户交互使用。
3. 数据库运行管理
数据库在运行期间多用户环境下的并发控制、安全性检查和存取控制、完整性检查和执行、运行日志的组织管理、事务管理和自动恢复等是 DBMS 的重要组成部分，这些功能可以保证数据库系统的正常运行。
4. 数据的组织、存储和管理
DBMS 分类组织、存储和管理各种数据，包括数据字典、用户数据和存取路径等。因此要确定以何种文件结构和存取方式在存储级上组织这些数据，以提高存取效率。实现数据间的联系、数据组织和存储的基本目标是提高存储空间的利用率。
5. 数据库的建立和维护
数据库的建立和维护包括数据库的初始建立、数据的转换、数据库的转储和恢复、数据库的重组和重构、性能监测和分析等。
6. 其他功能
其他功能包括：DBMS 的网络通信功能，一个 DBMS 与另一个 DBMAS 或文件系统的数据转换功能，异构数据库之间的互访和互操作能力等。
9.1.3 数据库管理系统的特征及分类
1. DBMS 的特征
通过 DBMS 来管理数据具有以下特点。
(1) 数据结构化且统一管理。数据库中的数据由 DBMS 统一管理。由于数据库系统采用复杂的数据模型表示数据结构，数据模型不仅描述数据本身的特点，还描述数据之间的联系。数据不再面向某个应用，而是面向整个应用系统。数据易维护、易扩展，数据冗余明显减少，真正实现了数据的共享。
(2) 有较高的数据独立性。数据的独立性是指数据与程序独立，将数据的定义从程序中分离出去，由 DBMS 负责数据的存储，应用程序关心的只是数据的逻辑结构，无须了解数据在磁盘上的数据库中的存储形式，从而简化应用程序，大大减少了应用程序编制的工作量。数据的独立性包括数据的物理独立性和数据的逻辑独立性。
(3) 数据控制功能。DBMS 提供了数据控制功能，以适应共享数据的环境。数据控制功能包括对数据库中数据的安全性、完整性、并发和恢复的控制。
① 数据库的安全性。数据库的安全性（Security）是指保护数据库以防止不合法的使用所造成的数据泄漏、更改或破坏。这样，用户只能按规定对数据进行处理，例如，划分了不同的权限，有的用户只能有读数据的权限，有的用户有修改数据的权限，用户只能在规定的权限范围内操纵数据库。
② 数据的完整性。数据库的完整性是指数据库的正确性和相容性，是防止合法用户使用数据库时向数据库加入不符合语义的数据，保证数据库中的数据是正确的，避免非法的更新。
③ 并发控制。在多用户共享的系统中，许多用户可能同时对同一数据进行操作。DBMS 的并发控制子系统负责协调并发事务的执行，保证数据库的完整性不受破坏，避免用户得到不正确的数据。
④ 故障恢复。数据库中的4类故障是事务内部故障、系统故障、介质故障及计算机病毒。故障恢复主要指恢复数据库本身，即在故障引起数据库当前状态不一致时将数据库恢复到某个正确状态或一致状态。恢复的原理非常简单，就是要建立冗余（Redundancy）数据。换句话说，确定数据库是否可恢复的方法就是其包含的每一条信息是否都可以利用冗余存储在别处的信息重构。冗余是物理级的，通常认为逻辑级是没有冗余的。
2. DBMS 的分类
DBMS 通常可分为以下三类。
(1) 关系数据库系统（Relation DataBase Systems，RDBS）。关系数据库系统是建立在关系数据库模型基础上的数据库，借助于集合代数等概念和方法来处理数据库中的数据。目前主流的关系数据库有 Oracle、Db2、Sybase、Microsoft SQL Server、Microsoft Access、MySQL 等。在关系模型中，实体以及实体间的联系都是用关系来表示的。在一个给定的现实世界领域中，相应的所有实体及实体之间联系的关系的集合构成一个关系数据库，也有型和值之分。关系数据库的型也称为关系数据库模式，它是对关系数据库的描述，是关系模式的集合。关系数据库的值也称为关系数据库，是关系的集合。关系数据库模式与关系数据库通常统称为关系数据库。
(2) 面向对象的数据库系统（Object-Oriented DataBase System，OODBS）。面向对象的数据库系统是支持以对象形式对数据建模的数据库管理系统，包括对对象的类、类属性的继承和子类的支持。面向对象数据库系统主要有两个特点：一是面向对象数据模型能完整地描述现实世界的数据结构，能表达数据间的嵌套、递归联系；二是具有面向对象技术的封装性和继承性提高了软件的可重用性。
(3) 对象关系数据库系统（Object-Oriented Relation DataBase System，ORDBS）。对象关系数据库系统是在传统的关系数据模型基础上提供元组、数组、集合等更为丰富的数据类型以及处理新的数据类型操作的能力，这样形成的数据模型被称为”对象关系数据模型”，基于对象关系数据模型的 DBS 称为对象关系数据库系统。
9.1.4 数据库系统的体系结构
数据库系统是数据密集型应用的核心，其体系结构受数据库运行所在的计算机系统的影响很大，尤其是受计算机体系结构中的连网、并行和分布的影响。从不同的角度或不同层次上看，数据库系统体系结构不同；从最终用户的角度看，数据库系统体系结构分为集中式、分布式、C/S（客户端/服务器）和并行结构；从数据库管理系统的角度看，数据库系统体系结构一般采用三级模式结构。
1. 集中式数据库系统
分时系统环境下的集中式数据库系统结构诞生于20世纪60年代中期。当时的硬件和操作系统决定了分时系统环境下的集中式数据库系统结构成为早期数据库技术的首选结构。在这种系统中，不仅数据是集中的，数据的管理也是集中的，数据库系统的所有功能（从形式的用户接口到 DBMS 核心）都集中在 DBMS 所在的计算机上，如图9-1所示。大多数关系 DBMS 的产品也是从这种系统结构开始发展的，目前这种系统还在使用。
2. 客户端/服务器结构
随着网络技术的迅猛发展，很多现代软件都采用客户端/服务器体系结构，如图9-2所示。在这种结构中，一个处理机（客户端）的请求被送到另一个处理机（服务器）上执行。其主要特点是客户端与服务器 CPU 之间的职责明确，客户端主要负责数据表示服务，服务器主要负责数据库服务。采用客户端/服务器结构后，数据库系统功能分为前端和后端。前端主要包括图形用户界面、表格生成和报表处理等工具；后端负责存取结构、查询计算和优化、并发控制以及故障恢复等。前端与后端通过 SQL 或应用程序来接口。ODBC（开放式数据库互连）和 JDBC（Java 程序数据库连接）标准定义了应用程序和数据库服务器通信的方法，即定义了应用程序接口，应用程序用它来打开与数据库的连接、发送查询和更新以及获取返回结果等。
数据库服务器一般可分为事务服务器和数据服务器。
(1) 事务服务器。事务服务器也称查询服务器。它提供一个接口，使得客户端可以发出执行一个动作的请求，服务器响应客户端请求，并将执行结果返回给客户端。用户端可以用 SQL，也可以通过应用程序或使用远程过程调用机制来表达请求。一个典型的事务服务器系统包括多个在共享内存中访问数据的进程，包括服务器进程、锁管理进程、写进程、监视进程和检查点进程。
(2) 数据服务器。数据服务器系统使得客户端可以与服务器交互，以文件或页面为单位对数据进行读取或更新。数据服务器与文件服务器相比提供更强的功能，所支持的数据单位可以比文件还要小，如页、元组或对象；提供数据的索引机制和事务机制，使得客户端或进程发生故障时数据也不会处于不一致状态。
3. 并行数据库系统
并行体系结构的数据库系统是多个物理上连在一起的 CPU，而分布式系统是多个地理上分开的 CPU。并行体系结构的数据库类型分为共享内存式多处理器和无共享式并行体系结构。
1) 共享内存式多处理器
共享内存式多处理器是指一台计算机上同时有多个活动的 CPU，它们共享单个内存和一个公共磁盘接口，如图9-3所示。这种并行体系结构最接近于传统的单 CPU 处理器结构，其设计的主要挑战是用 $N$ 个 CPU 来得到 $N$ 倍单 CPU 的性能。但是，由于不同的 CPU 对公共内存的访问是平等的，这样可能会导致一个 CPU 访问的数据被另一个 CPU 修改，所以必须要有特殊的处理。然而，由于内存访问采用的是一种高速机制，这种机制很难保证进行内存划分时不损失效率，所以这些共享内存访问问题会随着 CPU 个数的增加变得难以解决。
2) 无共享式并行体系结构
无共享式并行体系结构是指一台计算机上同时有多个活动的 CPU，并且它们都有自己的内存和磁盘，如图9-4所示，图中粗线表示高速网络。在不产生混淆的情况下，该结构的数据库系统也称为并行数据库系统。各个承担数据库服务责任的 CPU 划分它们自身的数据，通过划分的任务以及通过每秒兆位级的高速网络通信完成事务查询。
4. 分布式数据库系统
分布式 DBMS 包括物理上分布、逻辑上集中的分布式数据库结构和物理上分布、逻辑上分布的分布式数据库结构两种。前者的指导思想是把单位的数据模式（称为全局数据模式）按数据来源和用途合理地分布在系统的多个结点上，使大部分数据可以就地或就近存取。数据在物理上分布后，由系统统一管理，使用户不感到数据的分布。后者一般由两部分组成：一是本结点的数据模式，二是本结点共享的其他结点上有关的数据模式。结点间的数据共享由双方协商确定。这种数据库结构有利于数据库的集成、扩展和重新配置。
9.1.5 数据库的三级模式结构
实际上，数据库的产品很多，它们支持不同的数据模型，使用不同的数据库语言，建立在不同的操作系统上。数据的存储结构也各不相同，但体系结构基本上都具有相同的特征，采用”三级模式和两级映像”，如图9-5所示。
数据库系统采用三级模式结构，这是数据库管理系统内部的系统结构。数据库有”型”和”值”的概念，”型”是指对某一数据的结构和属性的说明，”值”是型的一个具体赋值。
数据库系统设计员可以在视图层、逻辑层和物理层对数据进行抽象，通过外模式、概念模式和内模式来描述不同层次上的数据特性。
1. 概念模式
概念模式也称模式，它是数据库中全部数据的逻辑结构和特征的描述，由若干个概念记录类型组成，只涉及型的描述，不涉及具体的值。概念模式的一个具体值称为模式的一个实例，同一个模式可以有很多实例。
概念模式反映的是数据库的结构及其联系，所以是相对稳定的；而实例反映的是数据库某一时刻的状态，所以是相对变动的。
需要说明的是，概念模式不仅要描述概念记录类型，还要描述记录间的联系、操作以及数据的完整性和安全性等要求。但是，概念模式不涉及存储结构、访问技术等细节。只有这样，概念模式才算做到了”物理数据独立性”。
描述概念模式的数据定义语言称为”模式 DDL（Schema Data Definition Language）”。
2. 外模式
外模式也称用户模式或子模式，是用户与数据库系统的接口，是用户用到的那部分数据的描述。它由若干个外部记录类型组成。用户使用数据操纵语言对数据库进行操作，实际上是对外模式的外部记录进行操作。
描述外模式的数据定义语言称为”外模式 DDL”。有了外模式后，程序员不必关心概念模式，只与外模式发生联系，按外模式的结构存储和操纵数据。
3. 内模式
内模式也称存储模式，是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式，定义所有的内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。例如，记录的存储方式是顺序存储，按照 B 树结构存储，还是 Hash 方法存储；索引按照什么方式组织；数据是否压缩存储，是否加密；数据的存储记录结构有何规定。
描述内模式的数据定义语言称为”内模式 DDL”。
注意，内部记录并不涉及物理记录，也不涉及设备的约束。它比内模式更接近于物理存储和访问的那些软件机制，是操作系统的一部分（即文件系统）。例如，从磁盘上读、写数据。
总之，数据按外模式的描述提供给用户，按内模式的描述存储在磁盘上，而概念模式提供了连接这两级模式的相对稳定的中间层，并使得两级中任意一级的改变都不受另一级影响。
4. 两级映像
数据库系统在三级模式之间提供了两级映像：模式/内模式映像、外模式/模式映像。正因为这两级映像保证了数据库中的数据具有较高的逻辑独立性和物理独立性。
(1) 模式/内模式映像。存在于概念级和内部级之间，实现了概念模式和内模式之间的相互转换。
(2) 外模式/模式映像。存在于外部级和概念级之间，实现了外模式和概念模式之间的相互转换。
数据的独立性是指数据与程序独立，将数据的定义从程序中分离出去，由 DBMS 负责数据的存储，从而简化应用程序，大大减少应用程序编制的工作量。数据的独立性是由 DBMS 的二级映像功能来保证的。数据的独立性包括数据的物理独立性和数据的逻辑独立性。
(1) 数据的物理独立性。数据的物理独立性是指当数据库的内模式发生改变时，数据的逻辑结构不变。由于应用程序处理的只是数据的逻辑结构，这样物理独立性可以保证，当数据的物理结构改变时，应用程序不用改变。但是，为了保证应用程序能够正确执行，需要修改概念模式和内模式之间的映像。
(2) 数据的逻辑独立性。数据的逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构发生变化后，用户程序也可以不修改。但是，为了保证应用程序能够正确执行，需要修改外模式和概念模式之间的映像。
9.1.6 大数据
1. 大数据产生的背景
大数据（Big Data）是指”无法用现有的软件工具提取、存储、搜索、共享、分析和处理的海量的、复杂的数据集合”。大数据产生的背景主要有以下4个方面。
(1) 数据来源和承载方式的变革。由于物联网、云计算、移动互联网等新技术的发展，用户在线的每一次点击、每一次评论、每一个视频点播，都是大数据的典型来源；而遍布地球各个角落的手机、PC、平板电脑及传感器成为数据来源和承载方式。可见，只有大连接与大交互，才有大数据。
(2) 全球数据量出现爆炸式增长。由于视频监控、智能终端、网络商店等快速普及，使得全球数据量出现爆炸式增长。许多研究表明，未来数年数据量会呈现指数增长。根据麦肯锡全球研究院（MGI）估计，全球企业2010年在硬盘上存储了超过7EB（$1\text{EB}$ 等于 $10^9\text{GB}$）的新数据，而消费者在 PC 和笔记本等设备上存储了超过6EB的新数据。据 IDC（Internet Data Center）预测，到2020年，全球以电子形式存储的数据量将达32ZB。
(3) 大数据已经成为一种自然资源。许多研究者认为：大数据是”未来的新石油”，已成为一种新的经济资产类别。一个国家拥有数据的规模、活性及解释运用的能力将成为综合国力的重要组成部分。
(4) 大数据日益重要，不被利用就是成本。大数据作为一种数据资产当仁不让地成为现代商业社会的核心竞争力，不被利用就是企业的成本。因为，数据资产可以帮助和指导企业对整个业务流程进行有效的运营和优化，帮助企业做出最明智的决策。
2. 大数据的特征
大数据（Big Data）是指”无法用现有的软件工具提取、存储、搜索、共享、分析和处理的海量的、复杂的数据集合”。业界通常用”4V”来概括大数据的特征。
大量化（Volume）指数据体量巨大。随着 IT 技术的迅猛发展，数据量级已从 TB（$10^{12}$ 字节）发展至 PB 乃至 ZB，可称海量、巨量乃至超量。当前，典型个人计算机硬盘的容量为 TB 量级，而一些大企业的数据量已经接近 EB 量级。
多样化（Variety）指数据类型繁多。相对于以往便于存储的以文本为主的结构化数据，非结构化数据越来越多，包括网络日志、音频、视频、图片、地理位置信息等，这些多类型的数据对数据的处理能力提出了更高的要求。
价值密度低（Value）指大量的不相关信息导致价值密度的高低与数据总量的大小成反比。以视频为例，一部一小时的视频，在连续不间断的监控中，有用数据可能仅有一两秒。因此，如何通过强大的机器算法更迅速地完成数据的价值”提纯”，如何对未来趋势与模式的可预测分析、深度复杂分析（机器学习、人工智能 VS 传统商务智能咨询、报告等），成为目前大数据背景下亟待解决的难题。
快速化（Velocity）指处理速度快。大数据时代对时效性要求很高，这是大数据区分于传统数据挖掘的最显著特征。因为，在大数据环境下数据流通常为高速实时数据流，而且需要快速、持续的实时处理；处理工具也在快速演进，软件工程及人工智能等均可能介入。
3. 理解大数据
大数据不仅仅是指海量的信息，更强调人类对信息的筛选、处理，保留有价值的信息，即让大数据更有意义，挖掘其潜在的”大价值”这才是对大数据的正确理解。为此，有许多问题需要研究与解决。
(1) 高并发数据存取的性能要求及数据存储的横向扩展问题。目前，多从架构和并行等方面考虑解决。
(2) 实现大数据资源化、知识化、普适化的问题，解决这些问题的关键是对非结构化数据的内容理解。
(3) 非结构化海量信息的智能化处理问题，主要解决自然语言理解、多媒体内容理解、机器学习等问题。
大数据时代主要面临三大挑战：软件和数据处理能力、资源和共享管理以及数据处理的可信力。
(1) 软件和数据处理能力。应用大数据技术，提升服务能力和运作效率，以及个性化的服务，比如医疗、卫生、教育等部门。
(2) 资源和共享管理。应用大数据技术，提高应急处置能力和安全防范能力。
(3) 数据处理的可信力。需要投资建立大数据的处理分析平台，实现综合治理、业务开拓等目标。
4. 大数据产生的安全风险
2012年瑞士达沃斯论坛上发布的《大数据大影响》报告称，数据已成为一种新的经济资产类别，就像货币或黄金一样。因此，也带来了更多安全风险。
(1) 大数据成为网络攻击的显著目标。在互联网环境下，大数据是更容易被”发现”的大目标。这些数据会吸引更多的潜在攻击者，如数据的大量汇集，使得黑客成功攻击一次就能获得更多数据，无形中降低了黑客的攻击成本，增加了”收益率”。
(2) 大数据加大了隐私泄露风险。大量数据的汇集不可避免地加大了用户隐私泄露的风险，因为数据集中存储增加了泄露风险；另外，一些敏感数据的所有权和使用权并没有明确界定，很多基于大数据的分析都未考虑到其中涉及的个体隐私问题。
(3) 大数据威胁现有的存储和安防措施。大数据存储带来新的安全问题，数据大集中的后果是复杂多样的数据存储在一起，很可能出现将某些生产数据放在经营数据存储位置的情况，致使企业安全管理不合规。大数据的大小也影响到安全控制措施能否正确运行。如果安全防护手段的更新升级速度无法跟上数据量非线性增长的步伐，就会暴露大数据安全防护的漏洞。
(4) 大数据技术成为黑客的攻击手段。在企业用数据挖掘和数据分析等大数据技术获取商业价值的同时，黑客也在利用这些大数据技术向企业发起攻击。黑客会最大限度地收集更多的有用信息，例如社交网络、邮件、微博、电子商务、电话和家庭住址等信息，大数据分析使黑客的攻击更加精准。
(5) 大数据成为高级可持续攻击的载体。传统的检测是基于单个时间点进行的基于威胁特征的实时匹配检测，而高级可持续攻击（APT）是一个实施过程，无法被实时检测。此外，大数据的价值低密度性使得安全分析工具很难聚焦在价值点上，黑客可以将攻击隐藏在大数据中，给安全服务提供商的分析制造很大困难。黑客设置的任何一个会误导安全厂商目标信息提取和检索的攻击，都会导致安全监测偏离应有方向。
(6) 大数据技术为信息安全提供新支撑。当然，大数据也为信息安全的发展提供了新机遇。大数据正在为安全分析提供新的可能性，对于海量数据的分析有助于信息安全服务提供商更好地刻画网络异常行为，从而找出数据中的风险点。对实时安全和商务数据结合在一起的数据进行预防性分析，可识别钓鱼攻击，防止诈骗和阻止黑客入侵。网络攻击行为总会留下蛛丝马迹，这些痕迹都以数据的形式隐藏在大数据中，利用大数据技术整合计算和处理资源有助于更有针对性地应对信息安全威胁，有助于找到攻击的源头。
9.2 数据模型
9.2.1 基本概念
模型就是对现实世界特征的模拟和抽象，数据模型是对现实世界数据特征的抽象。对于具体的模型人们并不陌生，如航模飞机、地图和建筑设计沙盘等都是具体的模型。最常用的数据模型分为概念数据模型和基本数据模型。
(1) 概念数据模型。概念数据模型也称信息模型，是按用户的观点对数据和信息建模；是现实世界到信息世界的第一层抽象，强调其语义表达功能，易于用户理解；是用户和数据库设计人员交流的语言，主要用于数据库设计。这类模型中最著名的是实体-联系模型，简称 E-R 模型。
(2) 基本数据模型。它是按计算机系统的观点对数据建模，是现实世界数据特征的抽象，用于 DBMS 的实现。基本的数据模型有层次模型、网状模型、关系模型和面向对象模型（Object Oriented Model）。
9.2.2 数据模型的三要素
数据库结构的基础是数据模型，是用来描述数据的一组概念和定义。数据模型的三要素是数据结构、数据操作和数据的约束条件。
(1) 数据结构。数据结构是所研究的对象类型的集合，是对系统静态特性的描述。
(2) 数据操作。数据操作是对数据库中各种对象（型）的实例（值）允许执行的操作的集合，包括操作及操作规则。例如操作有检索、插入、删除和修改，操作规则有优先级别等。数据操作是对系统动态特性的描述。
(3) 数据的约束条件。数据的约束条件是一组完整性规则的集合。也就是说，对于具体的应用数据必须遵循特定的语义约束条件，以保证数据的正确、有效和相容。例如某单位人事管理中，要求在职的”男”职工的年龄必须大于18岁小于60，工程师的基本工资不能低于1500元，每个职工可担任一个工种，这些要求可以通过建立数据的约束条件来实现。
9.2.3 E-R 模型
概念模型是对信息世界建模，所以概念模型能够方便、准确地表示信息世界中的常用概念。概念模型有很多种表示方法，其中最为常用的是 P.P.S.Chen 于1976年提出的实体-联系方法（Entity Relationship Approach）。该方法用 E-R 图来描述现实世界的概念模型，称为实体-联系模型（Entity-Relationship Model，E-R 模型）。
E-R 模型是软件工程设计中的一个重要方法，因为它接近于人的思维方式，容易理解并且
