第9章　算法设计与分析

算法被公认为是计算机科学的基石，算法理论研究的是算法的设计技术和分析技术。前者回答的是“对特定的问题，如何提出一个算法来求解？”这样的问题，即面对一个问题，如何设计一个有效的算法；后者回答的是“该算法是否足够好？”，即对已设计的算法，如何评价或判断其优劣。二者是互相依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。

9.1　算法设计与分析的基本概念

9.1.1　算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性。

（1）有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。

（2）确定性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

（3）可行性。一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

（4）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

（5）输出。一个算法有一个或多个输出。这些输出是同输入有着某些特定关系的量。

9.1.2　算法设计

算法设计是一件非常困难的工作，通常设计一个“好”的算法应考虑多个目标，包括正确性、可读性、健壮性和高效性等。由于实际问题各种各样，问题求解的方法千变万化，所以算法设计又是一个灵活的充满智慧的过程，需要设计人员根据实际情况具体问题具体分析。

存在多种算法设计技术（也称为算法设计策略），它们是设计算法的一般性方法。已经证明这些技术对于设计好的算法非常有用，掌握了这些技术之后，设计新的和有用的算法会变得容易。经常采用的算法设计技术主要有分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。另外，在解决计算机领域以外的问题时，这些技术也能起到很好的指导作用。

9.1.3　算法分析

通常求解一个问题可能会有多种算法可供选择，选择的主要标准首先是算法的正确性、可靠性、简单性和易理解性。其次是算法的时间复杂度和空间复杂度要低，这正是算法分析技术的主要内容。

算法分析是指对一个算法所需要的资源进行估算，这些资源包括内存、通信带宽、计算机硬件和时间等，所需要的资源越多，该算法的复杂性就越高。不言而喻，对于任何给定的问题，设计出复杂性尽可能低的算法是设计算法时追求的重要目标。另一方面，当给定问题有很多种算法时，选择其中复杂性最低者，是选用算法时遵循的重要准则。因此，算法的复杂性分析对算法的设计和选用有重要的指导意义和实用价值。

而在计算机资源中，最重要的是时间和空间（存储器）资源，因此复杂性分析主要包括时间复杂性和空间复杂性。

9.1.4　算法的表示

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

（1）自然语言。最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。

（2）流程图。优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。

（3）程序设计语言。优点是能用计算机直接执行，缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性。此外，还要求算法设计者掌握程序设计语言及编程技巧。

（4）伪代码。伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。计算机科学家从来没有对伪代码的书写形式达成过共识。在伪代码中，可以采用最具表达力的、最简明扼要的方法来表达一个给定的算法。本章采用伪代码来表示算法。

本章伪代码的一些约定。

（1）用缩进表示程序中的分程序或程序块结构。

（2）while、for等循环结构和if、then、else等条件结构与Pascal中的相似。其实只要熟悉Pascal、C、C++或者Java中的某一种语言，便可很容易理解伪代码表达的含义。

（3）用▷表示注释。

（4）数组的元素通过“数组名［下标］”的方式访问，下标从1开始。

（5）参数采用按值传递。

（6）布尔运算符and和or具有短路能力。

9.2　算法分析基础

9.2.1　时间复杂性

由于时间复杂性与空间复杂性概念类似，计算方法相似，且空间复杂性分析相对简单些，因此下面将主要讨论时间复杂性。算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。

不同规模的输入所需要的基本操作数是不相同的，如用同一个排序算法排序100个数和排序10000个数所需要的操作数是不相同的，因此考虑特定输入规模的算法的具体操作数既是不现实也是不必要的。在算法分析中，可以建立以输入规模n为自变量的函数T（n）来表示算法的时间复杂度。

即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分析分为三种情况。

（1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω（nlgn），那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。

（2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它给我们提供一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。

（3）平均情况。算法的平均运行时间，一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10！种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按如下三个步骤进行。

①　将所有的输入按其执行时间分类。

②　确定每类输入发生的概率。

③　确定每类输入的执行时间。

下式给出了一般算法在平均情况下的复杂度分析。

其中，p_i表示第i类输入发生的概率；t_i表示第i类输入的执行时间，输入分为m类。

9.2.2　渐进符号

以输入规模n为自变量建立的时间复杂度实际上还是较复杂的，如an²＋bn＋c，不仅与输入规模有关，还与系数a、b和c有关。此时可以对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低阶项和高阶项的系数，仅考虑n²。当输入规模大到使只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。下面简单介绍三种常用的标准方法来简化算法的渐进分析。

（1）Ο记号。给出一个函数的渐进上界。给定一个函数g（n），Ο（g（n））表示为一个函数集合｛f（n）:存在正常数c和n₀，使得对所有的n≥n₀，有0≤f（n）≤cg（n）｝。

（2）Ω记号。给出一个函数的渐进下界。给定一个函数g（n），Ο（g（n））表示为一个函数集合｛f（n）:存在正常数c和n₀，使得对所有的n≥n₀，有0≤cg（n）≤f（n）｝。

（3）Θ记号。给出一个函数的渐进上界和下界，即渐进确界。给定一个函数g（n），Ο（g（n））表示为一个函数集合｛f（n）:存在正常数c₁、c₂和n₀，使得对所有的n≥n₀，有0≤c₁g（n）≤f（n）≤c₂g（n）｝。

图9-1　记号Θ、Ο和Ω的图例

由上述定义可知，f（n）＝Θ（g（n））当且仅当f（n）＝Ο（g（n））和f（n）＝Ω（g（n））。

【例9.1】判断下列等式是否成立？

（1）10n²＋4n＋2＝Ο（n²）

（2）10n²＋4n＋2＝Ο（n³）

（3）10n²＋4n＋2＝Ο（n）

（4）10n²＋4n＋2＝Ω（n²）

（5）10n²＋4n＋2＝Ω（n³）

（6）10n²＋4n＋2＝Ω（n）

（7）10n²＋4n＋2＝Θ（n²）

（8）10n²＋4n＋2＝Θ（n³）

（9）10n²＋4n＋2＝Θ（n）

解：（1）√（2）√（3）×（4）√（5）×（6）√（7）√（8）×（9）×

9.2.3　递归式

从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本节主要讨论递归算法的时间复杂度分析方法。

（1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。

【例9.2】求的解。

解：

（2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时，需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。

【例9.3】确定的上界。

解：（1）猜测其解为T（n）＝Ο（nlgn）。目标是要证明T（n）≤cnlgn，其中c＞0为常数。

（2）先假设这个界对n/2成立，即T（n/2）≤cnlg（n/2）/2。对递归式做替换，得到T（n）≤2cnlg（n/2）/2＋n＝cnlgn－cn＋n≤cnlgn（c≥1）。

尽管代换法提供了一种证明递归式解的正确性的简单方法，但并不存在通用的方法来猜测递归式的正确解，这种猜测需要经验，有时甚至是创造性的。因为往往很难得到“好”的猜测，因此这种方法较难用。

（3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供“好”的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。

【例9.4】确定的确界。

解：用递归树法求解，图9-2（a）、图9-2（b）、图9-2（c）和图9-2（d）给出了递归树的构造过程。

图9-2　与递归式T（n）＝4T（n/2）＋cn对应的递归树的构造过程

（4）主方法。也称为主定理，给出求解如下形式的递归式的快速方法。

其中，a≥1和b＞1是常数，f（n）是一个渐进的正函数。

【定理9.1】（主定理）设a≥1和b＞1为常数，f（n）为函数，T（n）为定义在非负整数上的递归式，T（n）＝aT（n/b）＋f（n），其中n/b指n/b或n/b，那么T（n）可能有如下的渐进界。

（1）若对于某常数ε＞0，有则

（2）若则

（3）若对于某常数ε＞0，有f（n）＝Ω（n^log_ba+ε），且对常数c＜1与所有足够大的n，有af（b/n）≤cf（n），则T（n）＝Θ（f（n））。

【例9.5】用主方法求解下列递归式。

（1）T（n）＝9T（n/3）＋n

（2）T（n）＝T（2n/3）＋1

（3）T（n）＝3T（n/4）＋nlgn

解：（1）a＝9，b＝3，f（n）＝n。log_ba＝2，其中ε＝1，属于情况（1），因此有

（2）a＝1，b＝3/2，f（n）＝1。log_ba＝0，其中k＝0，属于情况（2），因此有

（3）a＝3，b＝4，f（n）＝nlgn。log_ba≈0.793，其中ε≈0.2，属于情况（3），因此有T（n）＝Θ（f（n））＝Θ（nlgn）。

9.3　分治法

9.3.1　递归的概念

递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。在计算机算法设计与分析中，递归技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析，为此在介绍其他算法设计方法之前先讨论它。

递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体。

【例9.6】阶乘函数。

阶乘函数可递归地定义为：

阶乘函数的自变量n的定义域是非负整数。递归式的第一式给出了这个函数的一个初始值，是递归的边界条件。递归式的第二式是用较小自变量的函数值来表示较大自变量的函数值的方式来定义n的阶乘，是递归体。n！可以递归地计算如下：

9.3.2　分治法的基本思想

分治与递归就像一对孪生兄弟，经常同时应用于算法设计之中，并由此产生许多高效的算法。我们知道，任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。问题的规模越小，解题所需要的计算时间往往也越少，从而也较容易处理。例如，对于n个元素的排序问题，当n＝1时，不需任何比较；当n＝2时，只要做一次比较即可；……而当n较大时，问题就不那么容易处理了。要想直接解决一个较大的问题，有时是相当困难的。分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题，1＜k≤n，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。

一般来说，分治算法在每一层递归上都有三个步骤。

（1）分解。将原问题分解成一系列子问题。

（2）求解。递归地求解各子问题。若子问题足够小，则直接求解。

（3）合并。将子问题的解合并成原问题的解。

9.3.3　分治法的典型实例

以上讨论的是分治法的基本思想和一般原则，下面用一些具体例子来说明如何针对具体问题用分治思想来设计有效算法。

【例9.7】归并排序。

归并排序算法是成功应用分治法的一个完美的例子，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列进行排序，最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照上述分治算法的三个步骤进行。

（1）分解。将n个元素分成各含n/2个元素的子序列。

（2）求解。用归并排序对两个子序列递归地排序。

（3）合并。合并两个已经排好序的子序列以得到排序结果。

归并排序算法的伪代码如下：

过程Merge（A，p，q，r）的伪代码为：

其中，A是数组，p、q和r是下标，满足p≤q＜r。Merge显然可在Ο（n）时间内完成，因此合并排序算法对n个元素进行排序所需的计算时间T（n）满足：

解此递归式可知T（n）＝Ο（nlogn）。

【例9.8】最大子段和问题。

给定由n个整数（可能有负整数）组成的序列a₁，a₂，…，a_n，求该序列形如的子段和的最大值。当序列中所有整数均为负整数时，其最大子段和为0。依此定义，所求的最优值为

例如，当（a₁，a₂，a₃，a₄，a₅，a₆）＝（-2，11，-4，13，-5，-2）时，最大子段和为

最大子段和问题的分治策略如下。

（1）分解。如果将所给的序列A[1..n]分为长度相等的两段A[1..n/2]和A[n/2＋1..n]，分别求出这两段的最大子段和，则A[1..n]的最大子段和有三种情形。

①　A[1..n]的最大子段和与A[1..n/2]的最大子段和相同。

②　A[1..n]的最大子段和与A[n/2＋1..n]的最大子段和相同。

③　A[1..n]的最大子段和为且1≤i≤n/2，n/2＋1≤j≤n。

（2）解决。①和②这两种情形可递归求得。对于情形③，容易看出，A[n/2]与A[n/2＋1]在最优子序列中。因此可以在A[1..n/2]中计算出并在A[n/2＋1..n]中计算出则s1＋s2即为出现情形③的最优值。

（3）合并。比较在分解阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。

据此可设计出求解最大子段和的分治算法如下：

过程MaxSubSum的伪代码为：

其中A为数组，left和right表示数组下标。对应分解中的①和②两种情形，需要分别递归求解，对应情形③，两个并列for循环的时间复杂度为Ο（n），因此得到下列递归式。

解此递归式可知T（n）＝Ο（nlogn）。

【例9.9】循环赛日程安排。

设有n（2^k）位选手参加网球循环赛，循环赛共进行n－1天，每位选手要与其他n－1位选手赛一场，且每位选手每天赛一场，不轮空。试按此要求为比赛安排日程。

设n位选手被顺序编号为1，2，…，n。比赛的日程表是一个n行n－1列的表，第i行列的内容是第i号选手第j天的比赛对手。用分治法设计日程表，就是从其中一半选手（2^k－1位）的比赛日程导出全体（2^k位）选手的比赛日程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直至为n位选手安排好比赛日程为止。

为了从2^k－1位选手的比赛日程表中导出2^k位选手的比赛日程表，假定只有8位选手（如图9-3所示），若1～4号选手之间的比赛日程填在日程表的左上角（4行3列），5～8号选手之间的比赛日程填在日程表的左下角（4行3列），而左下角的内容可以由左上角对应项加上数4得到。至此，剩下的右上角（4行4列）是为编号小的1～4号选手与编号大的5～8号选手之间的比赛安排日程。例如在第4天，让1～4号选手分别与5～8号选手比赛，以后各天，依次由前一天的日程安排，让5～8号选手循环轮转即可。最后，参照右上角得到右下角的比赛日程，如图9-3所示。由以上分析，不难得到为2^k选手安排比赛的算法思路。

图9-3　循环赛日程安排

循环赛日程安排算法的关键在于寻找这4部分元素之间的对应关系，其伪代码如下：

其中A为数组，n＝2^k表示参加比赛的人数。

9.4　动态规划法

9.4.1　动态规划法的基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常可按照以下几个步骤进行。

（1）找出最优解的性质，并刻画其结构特征。

（2）递归地定义最优解的值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造一个最优解。

步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中根据所记录的信息快速构造出一个最优解。

动态规划法是一个非常有效的算法设计技术，那么何时可以应用动态规划来设计算法呢？对一个给定的问题，若其具有以下两个性质，则可以考虑用动态规划法来求解：

（1）最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。

（2）重叠子问题。指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

9.4.2　动态规划法的典型实例

【例9.10】0-1背包问题。

有n个物品，第i个物品价值为v_i，重量为w_i，其中v_i和w_i均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题可以形式化描述如下：

目标函数为

约束条件为x_i∈｛0，1｝

满足约束条件的任一集合（x₁，x₂，…，x_n）是问题的一个可行解，问题的目标是要求问题的一个最优解。考虑一个实例，假设n＝5，W＝17，每个物品的价值和重量如表9-1所示。可将物品1，2和5装入背包，背包未满，获得价值22，此时问题解为（1，1，0，0，1）。也可以将物品4和5装入背包，背包装满，获得价值24，此时解为（0，0，0，1，1）。

表9-1　物品的价值和重量

下面根据动态规划的4个步骤求解该问题。

（1）刻画0-1背包问题的最优解的结构。

可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即x_n＝1，那么其余x₁，x₂，…，x_n－1一定构成子问题1，2，…，n－1在容量W－w_n时的最优解。如果这个最优解不包含物品n，即x_n＝0，那么其余x₁，x₂，…，x_n－1一定构成子问题1，2，…，n－1在容量W时的最优解。

（2）递归定义最优解的值。

根据上述分析的最优解的结构递归地定义问题最优解。设c[i，w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。显然要求c[n，W]。

（3）计算背包问题最优解的值。

基于上述递归式，以自底向上的方式计算最优解的值，伪代码如下：

上述伪代码的时间复杂度为Ο（nW）。表9-2给出了上述实例填表的信息，从表中很容易看出最优解的值为24。

表9-2　0-1背包问题的动态规划法示例

（4）根据计算的结果，构造问题最优解。

根据上一步计算的c数组，很容易构造问题的最优解。判断c[i，w]与c[i－1，w]的值是否相等，若相等，则说明x_i＝0，否则为1。得到最优解的伪代码如下：

构造最优解的时间复杂度为Ο（n）。上述例子中，C[5，17]＝24≠C[4，17]＝21，x₅＝1；C[4，8]＝11≠C[3，8]＝10，x₄＝1；C[2，0]＝C[2，0]＝C[1，0]＝0，x₃＝x₂＝x₁＝0，因此最优解为（0，0，0，1，1）。

【例9.11】矩阵链乘问题。

给定n个矩阵｛A₁，A₂，…，A_n｝，其中A_i与A_i＋1是可乘的，i＝1，2，…，n－1。考虑这n个矩阵的乘积。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵链乘的计算次序完全确定，这时就说该链乘已完全加括号。完全加括号的矩阵链乘可递归地定义为：

（1）单个矩阵是完全加括号的。

（2）矩阵链乘的乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵链乘的乘积B和C的乘积并加括号，即A＝（BC）。

例如，矩阵链乘A₁A₂A₃A₄可以有以下5种完全加括号的方式：（A₁（A₂（A₃A₄）））、（A₁（（A₂A₃）A₄））、（（A₁A₂）（A₃A₄））和（（（A₁A₂）A₃）A₄）。每一种加括号的方式确定了一个计算的次序。不同的计算次序与矩阵链乘的计算量有密切关系。

为了说明该问题，回忆两个矩阵相乘的相关概念。矩阵A和矩阵B可乘的条件是矩阵A的列数等于矩阵B的行数，若A是一个p×q矩阵，B是一个q×r矩阵，则其乘积C＝AB是一个p×r矩阵，且标准的两个矩阵相乘所需要的计算量为pqr次乘法操作。

考虑三个矩阵｛A₁，A₂，A₃｝链乘的例子。设这三个矩阵的维数分别为10×100、100×5和5×50。若按第一种加括号方式（（A₁A₂）A₃）计算，则所需要的乘法次数为10×100×5＋10×5×50＝7500。若按第二种加括号方式（A₁（A₂A₃））计算，则所需要的乘法次数为10×5×50＋10×100×50＝75000。第二种加括号方式乘法次数是第一种的10倍。由此可以看出，不同的加括号方式确定的不同的计算次序对矩阵链乘的运算量影响是巨大的。

矩阵链乘问题定义如下：给定n个矩阵｛A₁，A₂，…，A_n｝，矩阵A_i的维数为p_i－1×p_i，i＝1，2，…，n，如何给矩阵链乘A₁×A₂×…×A_n完全加上括号，使得矩阵链乘中乘法次数最少。

矩阵链乘是非常难的问题，若用穷尽搜索法，能够证明需要指数时间来求解。现在考虑用动态规划法来求解矩阵链乘问题。

（1）刻画矩阵链乘问题的结构。

为简便起见，用A_i..j表示矩阵乘积A_iA_i＋1…A_j的结果，其中i≤j。若问题是非平凡的，即i＜j，那么乘积A_iA_i＋1…A_j一定在A_k与A_k＋1之间被分裂，i≤k＜j。问题A_iA_i＋1…A_j完全加括号的开销等于计算矩阵A_i..k与计算A_k＋1..j的开销，再加上它们的结果相乘的开销。

问题的最优子结构可刻画如下：假定问题A_iA_i＋1…A_j被完全加括号的最优方式是在A_k与A_k＋1之间被分裂，那么分裂之后，最优解A_iA_i＋1…A_j中的子链A_iA_i＋1…A_k一定是问题A_iA_i＋1…A_k的最优加括号方式。同样，最优解A_k＋1A_k＋2…A_j中的子链一定是问题A_k＋1A_k＋2…A_j的最优加括号方式。

（2）递归定义最优解的值。

根据问题的最优解递归地定义问题最优解的开销。设m[i，j]表示计算A_i..j所需的最小乘法次数，得到下列递归式。对于原问题，计算A_1..n的最小开销则为m[1，n]。

（3）计算最优解的值。

根据上述递归式，以自底向上的方式计算最优开销。假设输入为p=<p₀，p₁，…，p_n>，用表m[1..n，1..n]存储m[i，j]，用辅助表s[1..n，1..n]存储哪一个k使得计算m[i，j]时达到最优。最终需要利用s构造问题的一个最优解。算法的伪代码如下。

由上述伪代码很容易得到算法的时间复杂度为Ο（n³）。举个例子说明上述过程，假设n＝6，p=<p₀，p₁，…，p₆>=<30，35，15，5，10，20，25>。则根据上述伪代码，图9-4给出了m[i，j]的计算次序，以及m[i，j]和s[i，j]的值。

（4）构造最优解。

上一步给出了计算矩阵乘积的最少乘法次数（最优解的值），但没有给出具体的乘法次序（最优解）。可以由辅助表s的信息构造最优解，伪代码如下。

图9-4　矩阵链乘的动态规划算法示例

上述例子调用OutputOptimalParens（s,1,6）后得到输出结果（（A₁（A₂A₃））（（A₄A₅）A₆））。

【例9.12】最长公共子序列（LCS）。

非形式化的讲，子序列是指从给定序列中随意地（不一定是连续的）去掉若干元素（可能一个也不去掉）后所形成的序列。令序列X＝x₁x₂…x_m，序列Y＝y₁y₂…y_k是X的子序列，存在X的一个严格递增下标序列＜i₁，i₂，…，i_k＞，使得对所有的j＝1，2，…，k有x_ij＝y_j。例如，X＝ABCBDAB，Y＝BCDB是X的一个子序列。

给定两个序列X和Y，称序列Z是X和Y的公共子序列，是指Z同时是X和Y的子序列。最长公共子序列问题定义为：给定序列X＝x₁x₂…x_m和序列Y＝y₁y₂…y_n，求这两个序列的最长公共子序列。

如果用穷举法求解该问题，列举出X的所有子序列，并一一检查其是否是Y的子序列，并随时记录所发现的公共子序列，最终求出最长公共子序列，时间复杂度为Ο（2^mn），是指数级的时间复杂度，对于长序列来说不可行。而动态规划法可以有效地求解最长公共子序列问题。

（1）刻画最长公共子序列问题的最优子结构。

定理9.2证明了LCS具有最优子结构。

【定理9.2】LCS的最优子结构。设X＝x₁x₂…x_m和Y＝y₁y₂…y_n是两个序列，Z＝z₁z₂…z_k是X和Y的一个最长公共子序列。

（i）如果x_m＝y_n，那么z_k＝x_m＝y_n，且Z_k－1是X_m－1和Y_n－1的一个最长公共子序列。

（ii）如果x_m≠y_n，那么z_k≠x_m，蕴含着Z是X_m－1和Y的一个最长公共子序列。

（iii）如果x_m≠y_n，那么z_k≠y_n，蕴含着Z是X和Y_n－1的一个最长公共子序列。

（2）递归定义最优解的值。

设l[i，j]表示序列X_i和Y_j的最长公共子序列的长度，如果i＝0或j＝0，则其中有一个序列长度为0，因此LCS长度为0。由LCS的最优子结构可导出以下递归式。

（3）计算最优解的值。

根据上述递归式，自底向上地求出最优解的值。将l[i，j]的值存储在表l[1..m，1..n]中，以行为主序从左到右计算表l中的元素，同时维持表b[1..m，1..n]，用其中的元素b[i，j]记录使得l[i，j]取最优值的最优子结构，以下给出该算法的伪代码。

从上述伪代码可知，算法的时间复杂度为Ο（mn）。根据上述算法，已知X＝ABCBDAB和Y＝BDCABA，则对应的表l和b如图9-5所示。

图9-5　用动态规划求解LCS问题示例

（4）构造最优解。

用表b中的信息构造X和Y的一个LCS。从b[m，n]开始，在表中沿着箭头的方向跟踪，当b[i，j]＝″↖″时，表示x_i＝y_j为LCS中的元素，伪代码如下所示。在图9-6所示的例子中，过程OutputLCS将产生如下输出：BCBA。

9.5　贪心法

9.5.1　贪心法的基本思想

作为一种算法设计技术，贪心法是一种简单的方法。和动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。举一个简单的贪心法例子，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在采用贪心法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。

我们知道，贪心算法并不总能得到最优解，那么对一个具体的问题，如何得知是否可以用贪心法来求解，以及能否得到问题的最优解？这个问题很难得到肯定的回答。但是，从许多可以用贪心法求得最优解的问题中看到，这类问题一般具有两个重要的性质。

（1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。

（2）贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。

9.5.2　贪心法的典型实例

【例9.13】活动选择问题。

活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时，如何选择最大的相容活动集合。假设有一个需要使用某一资源（如教室等）的n个活动组成的集合S＝｛a₁，a₂，…，a_n｝。该资源一次只能被一个资源占用。每个活动a_i有个开始时间s_i和结束时间f_i，且0≤s_i≤f_i＜∞。一旦被选择后，活动a_i就占据半开时间区间[s_i，f_i]。如果两个活动a_i和a_j的时间区间互不重叠，则称活动a_i和a_j是兼容的。活动选择问题就是要选择出一个由互相兼容的活动组成的最大子集合。考虑表9-3中的活动集合，其中各活动已经按结束时间的单调递增顺序进行了排序。从表中可以看到，子集｛a₃，a₉，a₁₁｝由相互兼容的活动组成。然而，它不是最大的子集，子集｛a₁，a₄，a₈，a₁₁｝更大。事实上，｛a₁，a₄，a₈，a₁₁｝是一个最大的相互兼容活动子集。另外，还有一个最大子集是｛a₂，a₄，a₉，a₁₁｝。

表9-3　活动集合

经分析，该问题具有最优子结构，可以用动态规划法求解。但同时该问题还具有贪心选择性质，因此可以用贪心法更简单地求解。

定义集合S_ij＝｛a_k∈S∶f_i≤S_k＜f_k≤S_j｝。为了完整地表示问题，加入两个虚拟活动a₀和a_n＋1，其中f₀＝0，s_n＋1＝∞，这样S＝S_0,n＋1。

【定理9.3】对于任意非空子问题S_ij，设a_m是S_ij中具有最早结束时间的活动。

那么，（1）活动a_m在S_ij的某个最大兼容活动子集中。

　　　（2）子问题S_im为空，所以选择a_m将使S_mj为唯一可能非空的子问题。

（证明略）

假设对n个活动按其结束时间单调递增进行了排序，排序的时间复杂度为Ο（nlgn）。下面给出解决活动选择问题的贪心算法的递归形式和迭代形式。

递归贪心算法：

迭代贪心算法：

这两个版本都能在Ο（n）的时间复杂度内完成。

【例9.14】背包问题。

背包问题的定义与0-1背包问题类似，但是每个物品可以部分装入背包，即在0-1背包问题中，x_i＝0或者x_i＝1；而在背包问题中，0≤x_i≤1。

为了更好地分析该问题，考虑一个例子：n＝5，W＝100，表9-4给出了各个物品的重量、价值和单位重量的价值。假设物品已经按其单位重量的价值从大到小排好序。

表9-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×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×60＝163，对应的解为｛1，1，1，4/5，0｝。可以证明，该解为问题的最优解。

假设对n个物品按其单位重量价值从大到小进行了排序，排序的时间复杂度为Ο（nlgn）。下面给出用贪心法解决背包问题的伪代码。

【例9.15】多机调度问题。

假设有n个独立的作业｛1，2，…，n｝，由m台相同的机器｛M₁，M₂，…，M_m｝进行加工处理，作业i所需的处理时间为t_i，每个作业均可在任意一台机器上加工处理，但不可间断或拆分，即一旦一个作业在某台机器上加工处理，便不会再转移到其他的机器上。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

多机调度问题是NP难问题，到目前还没有有效的算法。对于这类问题，用贪心算法求解有时可以得到较好的近似解。贪心法求解多机调度问题时的贪心策略是最长处理时间优先。当m≥n时，只要将机器i上的[0，t_i]时间区间分配给作业i即可；当m＜n时，首先将n个作业按其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的机器。例如，假设有7个作业｛1，2，3，4，5，6，7｝，由3台机器｛M₁，M₂，M₃｝加工处理，各个作业所需要的时间分别为｛2，14，4，16，6，5，3｝。首先将这7个作业按其处理时间从大到小排序，则作业｛4，2，5，6，3，7，1｝的处理时间为｛16，14，6，5，4，3，2｝。图9-6给出了按最长处理时间作业有限的原则时，这7个作业的调度情况及其所需要的总加工处理时间。

图9-6　三台机器的调度问题示例

假设对n个作业按其加工处理时间从大到小进行了排序，排序的时间复杂度为Ο（nlgn）。下面给出用贪心法解决多机调度问题的伪代码。

其中T、d和S分别表示n个作业的处理时间数组、m台机器的空闲时间数组、m台机器所处理的作业列表数组。

9.6　回溯法

回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束；而用来求问题的任一解时，只要搜索到问题的一个解就可结束。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法，它适用于解一些组合数较大的问题。

9.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背包问题，其解空间用一棵完全二叉树表示，如图9-7所示。

解空间树的第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表示背包能够容纳的最大重量。从图9-7的根节点开始搜索其解空间。

图9-7　0-1背包问题的解空间树

（1）开始时根节点是唯一的活节点，也是当前的扩展节点。在这个扩展节点处，按照深度优先策略移至节点B或节点C。假设选择先移至节点B。此时节点A和节点B是活节点，节点B成为当前的扩展节点。由于选取了w1（节点A到B的边上标记为1，表示选择物品），故在节点B处剩余背包容量是r＝14，获取的价值是45。

（2）从节点B处可以移至节点D或E。由于移至节点D需要w2＝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背包问题的最优解。

综上所述，运用回溯法解题通常包含以下三个步骤。

（1）针对所给问题，定义问题的解空间。

（2）确定易于搜索的解空间结构。

（3）以深度优先的方式搜索解空间。

3．回溯法的算法框架

回溯法的算法框架有非递归和递归两种方式。

非递归方式：

4．回溯法的限界函数

问题的解空间往往很大，为了有效地进行搜索，需要在搜索的过程中对某些节点进行剪枝。而对哪些节点进行剪枝，需要设计限界函数来判断。因此，限界函数的设计是回溯法的一个核心问题，也是一个很难的问题。设计限界函数的通用的指导原则是尽可能多和尽可能早地“杀掉”不可能产生最优解的活节点。好的限界函数可以大大减少问题的搜索空间，从而大大提高算法的效率。下面通过例子来说明。

9.6.2　回溯法的典型实例

【例9.16】0-1背包问题。

0-1背包问题的定义如例9.10所示。

图9-7给出了0-1背包问题的一个解空间树的示例。在该问题中，目标是为了得到最大的价值，因此可以“杀掉”那些不可能产生最大价值的活节点。那么如何判断哪些节点扩展后不可能产生最大价值呢？考虑贪心策略，先对所有物品按其单位重量价值从大到小排序，对搜索空间树中的某个节点如F，已经确定了某些X（i），1≤i≤k，而其他的X（i），k＋1≤i≤n待定。此时可以将0-1背包问题松弛为背包问题，求从F节点扩展下去，计算能获得的最大价值。若该价值比当前已经得到的某个可行解的值要小，则该节点不必再扩展。

假设所有物品已经按其单位重量价值从大到小排序。假设前k（包含k）个物品是否放入背包已经确定，现在考虑在当前背包的剩余容量下，若是背包问题，那么能获得的最大价值是多少？即求背包中物品的价值上界，伪代码如下所示。

其中v、w、k和W分别表示当前已经获得的价值、背包的重量、已经确定的物品数和背包的总容量。

其中，W、n、w、v、fw、fp和X分别表示背包的总容量、物品个数、重量数组、价值数组、获得最大价值时背包的重量、背包获得的最大价值和问题的最优解。

假设n＝8，W＝110，物品的价值和重量如表9-5所示。

表9-5　物品的基本信息

则根据上述伪代码得到图9-8所示的搜索空间树。

图9-8　0-1背包问题的回溯法示例

图9-8所示树中的节点内若有数据，则上面表示背包当前的重量，下面表示背包当前的价值；节点内若无数据，则旁边的数据表示在已有的选择下，背包能获得的价值的上界。X（i）＝1和X（i）＝0分别表示第i个物品放入和不放入背包中。浅灰色节点表示对应可行解的值，如存在5个可行解，其值分别为139，149，151，96，159，对应的解分别为X₁＝（1，1，1，1，1，0，0，0），X₂＝（1，1，1，1，0，1，0，0），X₃＝（1，1，1，1，0，0，1，0），X₄＝（1，1，1，1，0，0，0，0），X₅＝（1，1，1，0，1，1，0，0）。其中X₅为最优解，其值为159。

【例9.17】n-皇后问题。

这是来源于国际象棋的一个问题。n后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的其他任何棋子。因此，n后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。

求解过程从空棋盘开始，设在第1行至第m行都已经正确放置了m个皇后的基础上，再在第m＋1行上找合适的位置放第m＋1个皇后。直至在第n行也找到合适的位置放置第n个皇后时，就找到了一个解。接着改变第n行上皇后的位置，希望获得下一个解。另外，在任一行上有n种可选的位置。开始时，位置在第1列，以后改变时，顺次选择第2列、第3列、…、第n列。当第n列也不是一个合理的位置时，就要回溯，去改变前一行的位置。图9-9给出了回溯法求解4皇后问题的搜索过程。

图9-9　回溯法求解4皇后问题的搜索过程

n皇后问题的限界函数可以根据问题的定义直接设计，即任意两个皇后不在同行、同列和同一斜线上，伪代码如下。

用回溯法得到皇后问题的伪代码如下。

9.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，其解空间树如图9-7所示。

用队列式分支限界法解此问题时，用一个队列来存储活节点表。算法从根节点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。

9.8　概率算法

前面讨论的算法对于所有合理的输入都给出正确的输出，概率算法将这一条件放宽，把随机性的选择加入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。

一般情况下，概率算法具有以下基本特征。

（1）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列。

（2）概率算法在运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运行。

（3）概率算法的结果不能保证一定是正确的，但能限制其出错概率。

（4）概率算法在不同的运行过程中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。

概率算法大致分为4类：数值概率算法、蒙特卡罗（Monte Carlo）算法、拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。

（1）数值概率算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解，且近似解的精度随计算时间的增加不断提高。在多数情况下，要计算出问题的精确解是不可能的或没有必要的，因此用数值概率算法可得到相当满意的解。

（2）蒙特卡罗算法。蒙特卡罗算法用于求问题的精确解。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此，一般情况下，无法有效地判定所得到的解是否肯定正确。

（3）拉斯维加斯算法。拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。

（4）舍伍德算法。舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂度与其在平均情况下的计算复杂度有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。

9.9　近似算法

迄今为止，所有的难解问题都没有多项式时间算法，采用回溯法和分支限界法等算法设计技术可以相对有效地解决这类问题。然而，这些算法的时间性能常常是无法保证的。近似算法是解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低。近似算法是这样一个过程：虽然它可能找不到一个最优解，但它总会与待求解的问题提供一个解。为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间相差的程度。显然，这个差别越小，近似算法越具有实用性。

衡量近似算法性能最重要的标准有如下两个。

（1）算法的时间复杂度。近似算法的时间复杂度必须是多项式阶的，这是近似算法的基本目标。

（2）解的近似程度。近似最优解的近似程度也是设计近似算法的重要目标。近似程度与近似算法本身、问题规模，乃至不同的输入实例有关。

下面通过几个实例来说明近似算法的应用。

【例9.18】顶点覆盖问题。

无向图G＝（V，E）的顶点覆盖是顶点集V的一个子集V′，V′⊆V，使得若（u，v）是G的一条边，则u∈V′或者v∈V′。顶点覆盖V′的大小是它所包含的顶点个数｜V′｜。顶点覆盖问题是求出图G中的最小顶点覆盖，即含有顶点数最少的顶点覆盖。

顶点覆盖问题是一个NP难问题，因此，没有一个多项式时间算法有效的求解。虽然要找到图G的一个最小顶点覆盖是很困难的，但要找到图G的一个近似最小覆盖却很容易。可以采用如下策略：初始时边集E′＝E，顶点集V′＝｛｝，每次从边集E′中任取一条边（u，v），把顶点u和v加入到顶点集V′中，再把与u和v顶点相邻接的所有边从边集E′中删除，直到边集E′为空。显然，最后得到的顶点集V′是无向图的一个顶点覆盖，由于每次把尽量多的相邻边从边集E′中删除，可以期望V′中的顶点数尽量少，但不能保证V′中的顶点数最少。图9-10给出了一个顶点覆盖问题的近似算法求解过程。

图9-10　最小覆盖问题的近似算法求解过程

【例9.19】TSP问题。

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，并要求所走的路程最短。

TSP问题是著名的NP完全问题，并不存在有效的多项式时间算法，但是可以设计一个近似算法求解。其过程如下：首先采用Prim算法生成图的最小生成树T，如图9-11（b）所示，图中粗线表示最小生成树中的边。然后对T进行深度优先遍历，经过的路线为a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，得到遍历路线为L＝（a,b,c,h,d,e,f,g）。由序列L得到哈密尔顿回路，即近似最优解，如图9-11（d）所示，其路径长度约为19.074。图9-11（e）所示是图9-11（a）的最优解，其路径长度约为16.084。

图9-11　TSP问题的近似算法求解示例

【例9.20】　子集和数问题。

令S＝｛s₁,s₂,…,s_n｝是一个正整数的集合，子集和数问题要求在这个正整数集合中，找出其和不超过正整数C的最大和数的子集。

考虑用蛮力法求解子集和数问题，为了求得集合S的所有子集和，先将所有子集和的集合初始化为L₀＝｛0｝，然后求得子集和中包含s₁的情况，即L₀中的每一个元素加上s₁，用L₀＋s₁表示对集合L₀中的每个元素加上s₁后得到的新集合，则所有子集和的集合为L₁＝L₀＋（L₀＋s₁）＝｛0,s₁｝；再求得子集和中包含s₂的情况，即L₁中的每一个元素加上s₂，所有子集和的集合为L₂＝L₁＋（L₁＋s₂）＝｛0,s₁,s₂,s₁＋s₂｝。依此类推，一般情况下，为求得子集和中包含s_i（1≤i≤n）的情况，即L_i－1的每一个元素加上S_i，所有子集和的集合为L_i＝L_i－1＋（L_i－1＋s_i）。因为子集和要求不超过正整数C，所以每次合并后都要在L_i中删除所有大于C的元素。例如，若S＝｛104，102，201，101｝，C＝308，利用上述算法求解子集和数问题的过程如图9-12所示。

图9-12　蛮力法求解子集和数问题示例

上述算法具有指数时间复杂度，因此也是非常难的问题。现基于上述思想，用近似算法求解，其基本思想是在迭代过程中，对L_i进行适当的修整，使得在子集和不超过一定误差的前提下，尽可能减少L_i中的元素个数，从而获得算法时间性能的提高。具体方法是：用一个修整参数δ（0＜δ＜1），从集合L_i中删去尽可能多的元素得到L_1i，使得每一个从L_i删除的元素y，在集合L_1i中都有一个修整后的元素z满足（1－δ）*y≤z≤y，可以将z看作是被删去元素y在修整后的集合L_1i中的代表。例如，若S＝｛104，102，201，101｝，C＝308，δ＝0.05，利用上述算法求解子集和数问题的过程如图9-13所示。

图9-13　近似算法求解子集和数问题示例

9.10　NP完全性理论

迄今为止，我们接触过的大部分算法都是多项式时间算法，它们在最坏情况下的运行时间为O（n^k），其中n为输入规模，k为某个常数。我们自然会提出一个问题：是否所有问题都能做多项式时间内解决呢？答案是否定的。例如存在一些问题，如著名的停机问题，是任何计算机不论花费多少时间都不能解决的。还有一些问题尽管可以求解，但它们都不能在多项式O（n^k）的时间内得到解决。一般来说，把在多项式时间内可解的问题看作是容易的问题，而把超过多项式时间才能解决的问题看作是难的问题。本节简要介绍NP完全性理论，它是研究计算问题难易以及一类特殊的难解问题的理论。

关于NP完全性的理论研究是基于某种计算模型针对语言识别问题而进行的，本节从算法的角度给出一种非形式化的简单解释。

1．P类问题和NP类问题

在计算复杂性研究中，经常考虑的是判定问题，因为判定问题可以很容易地表达为语言的识别问题，从而方便地在某种计算模型上进行求解。

【定义9.1】判定问题。一个判定问题是仅仅要求回答yes或no的问题。例如，停机问题就是一个判定问题，但是，停机问题不能用任何计算机算法求解，所以不是所有的判定问题都可以在计算机上求解。

在实际应用中，很多问题都不是判定问题。但是，大多数问题可以很容易地转化为相应的判定问题。如排序问题：将一个整数序列调整为非降序序列。其判定形式可以叙述为：给定一个整数序列，是否可以按非降序排列。哈密尔顿回路问题：在图G＝（V，E）中，从某个顶点出发，求经过所有顶点一次且仅一次，再回到出发点的回路。哈密尔顿回路问题的判定形式可以叙述为：在图G＝（V，E）中，是否有一个回路经过所有顶点一次且仅一次，然后回到出发点。

判定问题有一个重要特性：虽然在计算上对问题求解是困难的，但在计算上判定一个待定解是否解决了该问题却是简单的。例如，求解哈密尔顿回路是个难解问题，但是验证一个给定顶点序列是不是哈密尔顿回路却很容易，只需要检查前n个顶点是否互不相同，而且最后一个顶点和第一个顶点是否相同。

【定义9.2】确定性算法。设A是求解问题Ⅱ的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性算法。

【定义9.3】P类问题。如果对于某个判定问题Ⅱ，存在一个非负整数k，对于输入规模为n的实例，能够以O（n^k）的时间运行一个确定性算法，得到yes或no的答案，则该判定问题Ⅱ是一个P类问题。

P类问题是由具有多项式时间的确定性算法来求解的判定问题组成。对于判定问题定义P类问题，主要是为了能够给出较为严格的NP类问题的定义。事实上，所有易解问题都属于P类问题。

【定义9.4】　设A是求解问题Ⅱ的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性算法。

（1）猜测阶段。在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。

（2）验证阶段。在这个阶段，用一个确定算法验证两件事：首先，检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；另一方面，如果串y是合适的形式，那么算法验证它是否是问题的解，如果是问题的解，则算法停下来并得到yes，否则算法停下来并得到no。

【定义9.5】NP类问题。如果对于某个判定问题Ⅱ，存在一个非负整数k，对于输入规模为n的实例，能够以O（n^k）的时间运行一个非确定性算法，得到yes或no的答案，则该判定问题Ⅱ是一个NP类问题。

对于NP类判定问题，重要的是它必须存在一个确定性算法，能够以多项式时间来检查和验证在猜测阶段所产生的答案。NP类问题是难解问题的一个子类，并不是任何一个在常规计算机上需要指数时间的问题（即难解问题）都是NP类问题。尽管NP类问题是对于判定问题定义的，事实上，可以在多项式时间应用非确定性算法解决的所有问题都属于NP类问题。综上所述，P类问题和NP类问题的主要差别如下。

（1）P类问题可以用多项式时间的确定性算法来进行判定或求解。

（2）NP类问题可以用多项式时间的非确定性算法来进行判定或求解。

如果问题Ⅱ属于P类，则存在一个多项式时间的确定性算法来对它进行判定或求解。显然，对这样的问题Ⅱ，也可以构造一个多项式的非确定性算法来验证其解的正确性。因此，问题Ⅱ也属于NP类问题，即P⊆NP。反之，如果问题Ⅱ属于NP类，则存在一个多项式时间的非确定性算法来猜测并验证它的解，但是，不一定能够构造一个多项式时间的确定性算法来对它进行求解或判定。因此，人们猜测P≠NP。但是，这个不等式是成立还是不成立，至今没有得到证明。

2．NP完全问题

NP完全问题是NP类问题的一个子类，对这个子类中的任何一个问题，如果能够证明用多项式时间的确定性算法来进行求解或判定，那么，NP完全问题中的所有问题都可以通过多项式时间的确定性算法来进行求解或判定。

【定义9.6】问题变换。假设问题Ⅱ′存在一个算法A，对于问题Ⅱ′的输入实例Ⅰ′，算法A求解问题Ⅱ′得到一个输出O′，另外一个问题Ⅱ的输入实例是Ⅰ，对应于输入Ⅰ，问题Ⅱ有一个输出O，则问题Ⅱ变换到问题Ⅱ′是一个三个步骤的过程。

（1）输入转换。把问题Ⅱ的输入Ⅰ转换为问题Ⅱ′的适当输入Ⅰ′。

（2）问题求解。对问题Ⅱ′应用算法A产生一个输出O′。

（3）输出转换。把问题Ⅱ′的输出转换为问题Ⅱ对应于输入Ⅰ的正确输出。

问题变换的一般过程如图9-14所示。

图9-14　问题变换的一般过程

需要强调的是，问题变换的主要目的不是给出解决一个问题的算法，而是给出通过另一个问题理解一个问题的计算时间上下限的一种方式。

【定理9.4】（计算时间下限归约）若已知问题Ⅱ的计算时间下限是T（n），且问题Ⅱ可τ（n）变换到问题Ⅱ′，即Ⅱ∝_τ（n）Ⅱ′，则T（n）-O（τ（n））为问题Ⅱ′的一个计算时间下限。

【定理9.5】（计算时间上限归约）若已知问题Ⅱ的计算时间上限是T（n），且问题Ⅱ可τ（n）变换到问题Ⅱ′，即Ⅱ∝_τ（n）Ⅱ′，则T（n）＋O（τ（n））为问题Ⅱ′的一个计算时间上限。

【定理9.6】设Ⅱ、Ⅱ′和Ⅱ′是三个判定问题，若Ⅱ∝_τ（n）Ⅱ′且Ⅱ′∝_τ（n）Ⅱ″，则Ⅱ∝_τ（n）Ⅱ″。

定理9.4和定理9.5刻画了问题变换与计算复杂性之间的关系，如图9-15所示。而定理9.6则说明了多项式问题变换是可传递的。

图9-15　时间复杂性归约示意图

【定义9.7】NP完全问题。令Ⅱ是一个判定问题，如果问题Ⅱ属于NP类问题，并且对NP类问题中的每一个问题Ⅱ′，都有Ⅱ′∝_pⅡ，则称判定问题Ⅱ是一个NP完全问题。

NP完全问题是NP类问题中最难的一类问题，其中任何一个问题至今都没有找到多项式时间算法。而且NP完全问题有一个重要性质：如果一个NP完全问题能在多项式时间内得到解决，那么NP完全问题中的每一个问题都可以在多项式时间内求解。尽管已经进行了多年的研究，目前还没有一个NP完全问题有多项式时间算法。这些问题也许存在多项式时间算法，因为计算机科学是相对新生的科学，肯定还会有新的算法设计技术有待发现；这些问题也许不存在多项式时间算法，但目前缺乏足够的技术来证明这一点。

已经定义了P类问题、NP类问题和NP完全问题等概念，广义上说，P类问题是可以用确定性算法在多项式时间内求解的一类问题，NP类问题是可以用非确定性算法在多项式时间猜测并验证的一类问题，而且P⊆NP。是否存在一些问题属于NP类问题而不属于P类问题呢？至今，还没有人能证明是否P≠NP。若P≠NP，则说明NP类中的所有问题，包括NP完全问题都不存在多项式时间算法；若P＝NP，则说明NP类中的所有问题，包括NP完全问题都具有多项式时间算法。无论哪一种答案，都将为算法设计提供重要的指导和依据。

NP类问题中还有一些问题，人们还不知道它是属于P类问题还是属于NP完全问题，这些问题还在等待人们证明它们的归属。这类问题包括图的同构问题和线性规划问题。

3．典型的NP完全问题

1971年，Cook通过Cook定理证明了可满足问题（SAT问题）是NP完全的。1972年，Karp证明了十几个问题都是NP完全的。这些NP完全问题的证明思想和技巧，以及利用它们证明的几千个NP完全问题，极大地丰富了NP完全理论。下面列出的是一些基本的NP完全问题。

（1）SAT问题。SAT问题也称为合取范式的可满足问题，来源于许多实际的逻辑推理的应用。一个合取范式形如A₁∧A₂∧…∧A_n，子句A_i（1≤i≤n）形如a₁∨a₂∨…∨a_k，其中，a_i（1≤i≤k）称为文字，为某一布尔变量或该布尔变量的非。SAT问题是指是否存在一组对所有布尔变量的赋值（TRUE或FALSE），使得整个合取范式取值为真。

（2）最大团问题。图G＝（V，E）的团是图G的一个完全子图，即子图中任意两个互异的顶点都有一条边相连。团问题是对于给定的无向图G＝（V，E）和正整数k，是否存在具有k个顶点的团。

（3）图着色问题。给定无向连通图G＝（V，E）和正整数k，是否可以用k种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。

（4）哈密尔顿问题。在图G＝（V，E）中，从某个顶点出发，求经过所有顶点一次且仅一次，再回到出发点的回路。

（5）TSP问题。给定带权图G＝（V，E）和正整数k，是否存在一条哈密尔顿回路，其路径长度小于k。

（6）顶点覆盖问题。设图G＝（V，E），V′是顶点V的子集，若图G的任一条边至少有一个顶点属于V′，则称为图G的顶点覆盖。

顶点覆盖问题是对于图G＝（V，E）和正整数k，是否存在顶点V的一个子集V′，使得图G的任一条边至少有一个顶点属于V′，且｜V′｜≤k。

（7）最长路径问题。给定一个带权图G＝（V，E）和一个正整数k，对于图G中的任意两个顶点v_i，v_j∈V（1≤i，j≤n，i≠j），是否存在从顶点v_i到顶点v_j的长度大于k的简单路径。

（8）子集和问题。给定一个整数集合S和一个正整数k，判断是否存在S的一个子集S′，使得S′中整数的和为k。