《王晓东算法设计与分析课件》由会员分享，可在线阅读，更多相关《王晓东算法设计与分析课件（356页珍藏版）》请在金锄头文库上搜索。
1、中国计算机学会中国计算机学会“21“21世纪大学本科计算机专业系列教材世纪大学本科计算机专业系列教材”算法设计与分析算法设计与分析王晓东王晓东编著编著1主要内容介绍主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法2主要内容介绍（续）主要内容介绍（续）第7章概率算法第8章NP完全性理论第9章近似算法第10章 算法优化策略3第第1 1章章 算法引论算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析本章主要知识点：41.1 算法与程序算法与程序输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少
2、一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 是满足下述性质的指令序列。算法：程序：51.从机器语言到高级语言的抽象1.2 表达算法的抽象机制表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程
3、序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；62.抽象数据类型1.2 表达算法的抽象机制表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化
4、；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 7在本书中，采用Java语言描述算法。1.1.JavaJava程序结构程序结构 1.3 描述算法描述算法以下，对JavaJava语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和appletapplet区别：应用程序的主方法为main，其可在命令行中用命令语句 java 应用程序名 来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理
5、。 （3）import语句：在java程序中可用import语句加载所需的包。例如，import java.io.*;语句加载java.io包。 81.3 描述算法描述算法2.2.JavaJava数据类型数据类型数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:int k;对非基本数据类型：语句 String s; 并不建立具有数据类型String的对象，而是建立一个类型String的
6、引用对象，数据类型为String的对象可用下面的new语句建立。 s = new StringString(“Welcome”);StringString s = new StringString(“Welcome”);91.3 描述算法描述算法表格表格1-1 1-1 JavaJava基本数据类型基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45 3.4*1038int032-2
7、147483648,2147483647long0649.2*1017short016-32768,32767101.3 描述算法描述算法3.3.方法方法在Java中，执行特定任务的函数或过程统称为方法(methods) 。例如，java的MathMath类类给出的常见数学计算的方法如下表所示：方法方法功能功能方法方法功能功能abs(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数
8、tan(x)x的正切111.3 描述算法描述算法3.3.方法方法 计算表达式 值的自定义方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。 （2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法ab可重载为： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 1
9、21.3 描述算法描述算法4.4.异常异常 Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理。 通常用trytry块来定义异常处理。每个异常处理由一个catchcatch语句组成。 public static void main(String args) try f ( ); catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; 131.3 描述算法描述算法5.5.JavaJava的类的类(4)访问修饰访问修饰公有(public) 私有(private)
10、保护(protected) Java的类一般由4个部分组成：(1)类名类名(2)数据成员数据成员(3)方法方法141.3 描述算法描述算法6.6.通用方法通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值。 public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 该方法只适用于该方法只适用于整
11、型数组整型数组该方法具有通用性，适用该方法具有通用性，适用于于ObjectObject类型及其所有子类型及其所有子类类 以上方法修改如下：以上方法修改如下：151.3描述算法描述算法6.6.通用方法通用方法 （1 1）ComputableComputable界面界面 public static Computable sum(Computable a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai);
12、return sum;利用此界面使利用此界面使方法方法sumsum通用化通用化 161.3 描述算法描述算法6.6.通用方法通用方法 （2 2）java.lang.Comparable java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.CpareTo(y)返回x-y的符号，当xy时返回正数。（3 3）OperableOperable 界面界面 有些通用方法同时需要Computable界面和Comparable 界面的支持。为此可定义Operable界面如下:public int
13、erface Operable extends Computable, Comparable （4 4）自定义包装类）自定义包装类 由于Java的包装类如Integer等已定义为final型，因此无法定义其子类，作进一步扩充。为了需要可自定义包装类。 171.3 描述算法描述算法7.7.垃圾收集垃圾收集8.8.递归Java的newnew运算用于分配所需的内存空间。例如， int a = new int500000; 分配2000000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃垃圾收集器圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新分配。 Java允许方法
14、调用其自身。这类方法称为递归方法。public static int sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); 计算一维整型数组前计算一维整型数组前n n个个元素之和的递归方法元素之和的递归方法 181.4 算法复杂性分析算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C
15、表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函数名当中） 191.4 算法复杂性分析算法复杂性分析最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性： 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。201.4 算法复杂性分析算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、o 设f(N)和g(
16、N)是定义在正数集上的正函数。 O O的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。 根据O的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g)； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N)，则O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一个正的常数； (6)f=O(f)。 211.4 算法复杂性分析算法复
17、杂性分析 的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=(g(N)。即f(N)的阶不低于g(N)的阶。 的定义的定义：定义f(N)= (g(N)当且仅当f(N)=O(g(N)且f(N)= (g(N)。此时称f(N)与g(N)同阶。 o o的定义的定义：对于任意给定的0，都存在正整数N0，使得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。 22第第2 2章章 递归与分
18、治策略递归与分治策略23将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。24算法总体思想算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(
19、n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。25算法总体思想算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)26算法总体思想算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向
20、上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法272.1 2.1 递归的概念递归的概念直接或间接地调用自身的算法称为递归算
21、法递归算法。用函数自身给出定义的函数称为递归函数递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。282.1 2.1 递归的概念递归的概念例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。292
22、.1 2.1 递归的概念递归的概念例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：public static int fibonacci(int n) if (n 1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 362.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1
23、n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。37(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划
24、分组成。(3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。2.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。382.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如
25、果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。 39402.1 2.1 递归的概念递归的概念例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上
26、；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。41在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。2.1 2.1
27、 递归的概念递归的概念例例6 6 HanoiHanoi塔问题塔问题 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); 思考题：如果塔的个数变为思考题：如果塔的个数变为思考题：如果塔的个数变为思考题：如果塔的个数变为a,b,c,da,b,c,d四个，现要将四个，现要将四个，现要将四个，现要将n n个圆盘从个圆盘从个圆盘从个圆盘从a a全部移动全部移动全部移动全部移动到到到到d d，移动规则不变，求移动步数最移动规则不变
28、，求移动步数最移动规则不变，求移动步数最移动规则不变，求移动步数最小的方案。小的方案。小的方案。小的方案。42递归小结递归小结优点：优点：结构清晰，可读性强，而且容易用数学归结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是耗费的递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法计算时间还是占用的存储空间都比非递归算法要多。要多。43递归小结递归小结解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消
29、除递归调用，使其转化为非递归算法。化为非递归算法。1.1.采用一个用户定义的栈来模拟系统的递归调用采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化只不过人工做了本来由编译器做的事情，优化效果不明显。效果不明显。2.2.用递推来实现递归函数。用递推来实现递归函数。3.3.通过通过CooperCooper变换、变换、反演变换能反演变换能将一些递归转化将一些递归转化为尾递归，从而迭代求出结果。为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均
30、有较大改善，但其适用范围有限。但其适用范围有限。44分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；该问题所分解出的各个
31、子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。45分治法的基本步骤分
32、治法的基本步骤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); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡
33、平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。46分治法的复杂性分析分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定
34、T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。 47二分搜索技术二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个
35、适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 48二分搜索技术二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这现要在这n个元素中找
36、个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法复杂度分析：算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大
37、小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。思考题：思考题：思考题：思考题：给定给定给定给定a a，用二分法设计出求，用二分法设计出求，用二分法设计出求，用二分法设计出求a an n的算法。的算法。的算法。的算法。49大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: abcd复杂度分析复杂度分析T(n)=O(n2) 没有改进没有改进X = Y
38、= X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 50大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。1.XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd2.XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd复杂度分析复杂度分
39、析T(n)=O(nlog3) =O(n1.59) 较大的改进较大的改进细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。51大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: O(n1.59) 较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Tra
40、nsform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。52StrassenStrassen矩阵乘法矩阵乘法A和B的乘积矩阵C中的元素Ci,j定义为: 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)53StrassenStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)
41、u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进54StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进55StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵
42、的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。56棋盘覆盖棋盘覆盖在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。57棋盘棋盘覆盖覆盖当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊
43、方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 58棋盘棋盘覆盖覆盖 public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc,
44、dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+
45、s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 复杂度分析复杂度分析T(n)=O(4k) 渐进意义下的最优算法59合并排序合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并
46、成为所要求的排好序的集合。 public static void mergeSort(Comparable a, int left, int right) if (leftright) /至少有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 复杂度分析复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法60合并排序合并排序算法mergeS
47、ort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 9761合并排序合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定思考题：思考题：给定给定有序表有序表A1:n，修修改合并排序算法，求出该有序表改合并排序算法，求出该有序表的逆序对数。的逆序对数。62快速排序快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大
48、的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。private static void qSort(int p, int r) if (p= x的元素交换到左边区域 / 将= x的元素交换到右边区域 while (true) while (a+pareTo(x) 0); if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; 初始序列6, 7, 5, 2, 5, 8j-;5, 7, 5, 2, 6, 8i+;5, 6, 5, 2, 7, 8j-
49、;5, 2, 5, 6, 7, 8i+;完成快速排序具有不稳定性不稳定性。6, 7, 5, 2, 5, 85, 2, 5 6 7, 864private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分
50、基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)&稳定性：不稳定稳定性：不稳定65线性时间选择线性时间选择给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=randomizedpartition(p,r), j=i-p+1; if (k
51、=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); 在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。66线性时间选择线性时间选择如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下在最坏情况下用O(n)时间完成选择任务。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短
52、1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。67l将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。l递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。线性时间选择线性时间选择设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小
53、于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。68private static Comparable select (int p, int r, int k) if (r-p5) /用某个简单排序算法对数组ap:r排序; bubbleSort(p,r); return ap+k-1; /将ap+5*i至ap+5*i+4的第3小元素 /与ap+i交换位置; /找中位数的中位数，r-p-4即上面所说的n-5 for ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+
54、5*i, t=s+4; for (int j=0;j3;j+) bubble(s,t-j); 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); 复杂度分析复杂度分析T(n)=O(n)上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n
55、/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。69最接近点对问题最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 u为了使问题易于理解和分析，先来考虑一维一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,
56、|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到能否在线性时间内找到p3,q3？70最接近点对问题最接近点对问题u如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3 (m-d,m，q3 (m,m+d。u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果如果(m-d,m中有中有S中的点，则此点就是中的点，则此点就是S1中最大点。中最大点。u因此，我们用线性
57、时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将从而我们用线性时间就可以将S1的解和的解和S2的解合并成为的解合并成为S的解的解。能否在线性时间内找到能否在线性时间内找到p3,q3？71最接近点对问题最接近点对问题u下面来考虑二维的情形。选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。能否在线性时间内找到能否在线性时间内找到p,q？72最接近点对问题最接近点对问题u考虑
58、P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的满足这个条件的P2中的中的点一定落在一个点一定落在一个d2d的矩形的矩形R中中u由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形矩形R中最多只有中最多只有6个个S中的点中的点。u因此，在分治法的合并步骤中最多只需要检查最多只需要检查6n/2=3n个个候选者候选者能否在线性时间内找到能否在线性时间内找到p3,q3？证明证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知
59、至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)d。这与d的意义相矛盾。73为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。最接近点对问题最接近点对问题7
60、4最接近点对问题最接近点对问题public static double cpair2(S) n=|S|; if (n 2) return ;1. m=S中各点x间坐标的中位数; 构造S1和S2； /S1=pS|x(p)m2. d1=cpair2(S1); d2=cpair2(S2);3. dm=min(d1,d2);4. 设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合； P2是S2中距分割线l的距离在dm之内所有点组成的集合； 将P1和P2中点依其y坐标值排序； 并设X和Y是相应的已排好序的点列；5. 通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可
61、以完成合并； 当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动； 设dl是按这种扫描方式找到的点对间的最小距离；6. d=min(dm,dl); return d;复杂度分析复杂度分析T(n)=O(nlogn)75设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。123
62、456782143658734127856432187655678123465872143785634128765432176循环赛日程表循环赛日程表设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。12345678214365873412785643218765567812346587214
63、3785634128765432177第第3 3章章 动态规划动态规划78动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=79算法总体思想算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=80但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)
64、T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)81如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)Those who cannot remember the past Those who cannot remember the past are
65、 doomed to repeat it. are doomed to repeat it. -George-George Santayana Santayana, , The life of ReasonThe life of Reason, , Book I: Introduction and Book I: Introduction and Reason in Common Reason in Common Sense (1905)Sense (1905)82动态规划基本步骤动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值
66、时得到的信息，构造最优解。83完全加括号的矩阵连乘积完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000, 10500, 36000, 87500, 34500u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式84矩阵连乘问题矩阵连乘问题n给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计
67、算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积85矩阵连乘问题矩阵连乘问题 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P
68、(n)的递推式如下：86矩阵连乘问题矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量87分析最优解的结构分析最优解的结构特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显
69、著特征。88建立递归关系建立递归关系n设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n可以递归地定义mi,j为：这里 的维数为 的位置只有 种可能89计算最优值计算最优值n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每
70、个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法90用动态规划法求最优解用动态规划法求最优解public static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1
71、; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 94最长公共子序列最长公共子序列若给定序列X=x1,x2,xm，
72、则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 95最长公共子序列的结构最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则(1)若xm=yn，则zk=xm
73、=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。 96子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下
74、，由最优子结构性质可建立递归关系如下：97计算最优值计算最优值由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: for (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;构造最长公共子序列构造最长公共子序列Algor
75、ithm lcs(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 98算法的改进算法的改进在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1
76、j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。99凸多边形最优三角剖分凸多边形最优三角剖分用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分多边形的三角剖分是将多边形
77、分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 100三角剖分的结构及其相关问题三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。
78、三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。101最优子结构性质最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 102最优三角剖分的递归结构最优三角剖分的递归结构定义tij，1ijn为凸子多边形vi-1,v
79、i,vj的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置。由此，tij可递归地定义为：103多边形游戏多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。
80、每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。104最优子结构性质最优子结构性质在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为vi，opi+1，vi+j-1。如
81、果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。 105图像压缩图像压缩图像的
82、变位压缩存储格式将所给的象素点序列p1,p2,pn,0pi255分割成m个连续段S1,S2,Sm。第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi位表示。设 则第i个象素段Si为设 ，则hibi8。因此需要用3位表示bi,如果限制1li255，则需要用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需要 位的存储空间。 图像压缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。106图像压缩图像压缩设li，bi，是p1,p2,pn的最优分段。显而易见，l1
83、，b1是p1,pl1的最优分段，且li，bi，是pl1+1,pn的最优分段。即图像压缩问题满足最优子结构性质。设si，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子结构性质易知：其中算法复杂度分析：算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。 107电路布线电路布线在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，如图所示。其中(i)是1,2,n的一个排列。导线(i,(i)称为该电路板上的第i条连线。对于任何
84、1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。 108记 。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)当i=1时，(2)当i1时，2.1 j(i)。此时， 。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。2.2 j(i)，(i,(i)MNS(i,j) 。 则对任意(t,(t) MNS(i,j)有ti且(t)(i)。在这种情况下MNS(i,j)-(i,(i)是N(i-1,(i)-
85、1)的最大不相交子集。 2.3 若 ，则对任意(t,(t) MNS(i,j)有 t1时109流水作业调度流水作业调度n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。分析：分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N=1，2，n。S
86、N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。110流水作业调度流水作业调度设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业(2)，(n)所需的时间。记S=N-(1)，则有T=T(S,b(1)。证明：证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)， (2)， (n)是N的一个
87、调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。由流水作业调度问题的最优子结构性质可知，111Johnson不等式不等式对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i, (2)=j。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJo
88、hnson不等式不等式。112流水作业调度的流水作业调度的Johnson法则法则交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等式时，有由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意i2n时，算法需要(n2n)计算时间。 116算法改进算法改进由m(i,j)的递归式容易证明，在一般情况下，
89、对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点惟一确定。如图所示。对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算，初始时pn+1=(0，0)。 117典型典型例子例子（一）一）n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)
90、xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)118算法改进算法改进函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1确
91、定跳跃点集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是pi中的跳跃点。除受控跳跃点外，pi+1qi+1中的其他跳跃点均为pi中的跳跃点。由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳跃点得到表pi。119典型典型例子例子（二）二）n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始时p6=(0,0)，(w5
92、,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p4=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2
93、，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。120算法复杂度分析算法复杂度分析上述算法的主要计算量在于计算跳跃点集pi(1in)。由于qi+1=pi+1(wi，vi)，故计算qi+1需要O(|pi+1|)计算时间。合并pi+1和qi+1并清除受控跳跃点也需要O(|pi+1|)计算时间。从跳跃点集pi的定义可以看出，pi中的跳跃点相应于xi,xn的0/1赋值。因此，pi中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集pi所花费的计算时
94、间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为O(minnc,2n)。121最优二叉搜索树最优二叉搜索树什么是二叉搜索树？（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3 它的左、右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和 是等数量级的122二叉查找树的期望耗费二叉查找树的期望耗费查找成功与不成功的概率二查找树的期望耗费有 个节
95、点的二叉树的个数为：穷举搜索法的时间复杂度为指数级123二叉查找树的期望耗费示例二叉查找树的期望耗费示例124最优二叉搜索树最优二叉搜索树最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为注意到，可以得到O(n2)的算法125第第4章章 贪心算法贪心算法126第第4章章 贪心算法贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义
96、上的局部最优局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。127第第4章章 贪心算法贪心算法本章主要知识点：4.1 活动安排问题4.2 贪心算法的基本要素4.3 最优装载4.4 哈夫曼编码4.5 单源最短路径4.6 最小生成树4.7 多机调度问题4.8 贪心算法的理论基础1284.1 4.1 活动安排问题活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪
97、心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。1294.1 4.1 活动安排问题活动安排问题 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。130
98、4.1 4.1 活动安排问题活动安排问题在下面所给出的解活动安排问题的贪心算法greedySelectorgreedySelector :public static int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; int j=1; int count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减
99、中且按结束时间的非减序排列序排列 1314.1 4.1 活动安排问题活动安排问题 由于输入的活动以其完成时间的非减序非减序排列，所以算法greedySelectorgreedySelector每次总是选择具有最早完成时具有最早完成时间间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时使剩余的可安排时间段极大化间段极大化，以便安排尽可能多的相容活动。 算法greedySelectorgreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排n个活动，使最多
100、的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlognO(nlogn) )的时间重排。 1324.1 4.1 活动安排问题活动安排问题 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011Si130535688212fi45678910111213141334.1 4.1 活动安排问题活动安排问题 算法算法greedySelectorgreedySelector 的的计算过程计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。134
101、4.1 4.1 活动安排问题活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。1354.2 4.2 贪心算法的基本要素贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算
102、法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质贪心选择性质和最最优子结构性质优子结构性质。 1364.2 4.2 贪心算法的基本要素贪心算法的基本要素1.1.贪心选择性质贪心选择性质 所谓贪心选择性质贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定
103、它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。1374.2 4.2 贪心算法的基本要素贪心算法的基本要素2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 1384.2 4.2 贪心算法的基本要素贪心算法的基本要素3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求
104、解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。1394.2 4.2 贪心算法的基本要素贪心算法的基本要素0-10-1背包问题：背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。
105、1404.2 4.2 贪心算法的基本要素贪心算法的基本要素背包问题：背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背包，1in。 这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 1414.2 4.2 贪心算法的基本要素贪心算法的基本要素用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重
106、量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 1424.2 4.2 贪心算法的基本要素贪心算法的基本要素public static float knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for
107、(i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; opt+=di.v; c-=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。当然，）。当然，为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选
108、择性质质。1434.2 4.2 贪心算法的基本要素贪心算法的基本要素 对于0-10-1背包问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划动态规划算法算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。 1444.3 4.3 最优装载最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问
109、题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。1.1.算法描述算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。 1454.3 4.3 最优装载最优装载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+) di = new Element(wi,i); MergeSort.mergeSort(d); float opt=
110、0; for (int i = 0; i n; i+) xi = 0; for (int i = 0; i n & di.w = c; i+) xdi.i = 1; opt+=di.w; c -= di.w; return opt; 其中其中ElementElement类说明为类说明为参参见本书见本书P115P1151464.3 4.3 最优装载最优装载2.2.贪心选择性质贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3.3.最优子结构性质最优子结构性质最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loadingloading的正确性。算法l
111、oadingloading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlognO(nlogn) )。 1474.4 4.4 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。1.1.前缀码前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码前缀码。1484.4 4.4 哈
112、夫曼编码哈夫曼编码 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码最优前缀码的二叉树总是一棵完全二叉树完全二叉树，即树中任一结点都有2个儿子结点。平均码长平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码最优前缀码。 1494.4 4.4 哈夫曼编码哈夫曼编码2.2.构造哈夫曼编码构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 1504.4 4.4 哈夫曼编码哈夫曼编码 在书
113、上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以以f f为键值的优先队列为键值的优先队列Q Q用在贪心选择贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间计
114、算时间为O(nlogn) 。1514.4 4.4 哈夫曼编码哈夫曼编码3.3.哈夫曼算法的正确性哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。(1)贪心选择性质(2)最优子结构性质1524.5 4.5 单源最短路径单源最短路径给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源源。现在要计算从源到所有其他各顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源单源最短路径问题最短路径问题。1.1.算法基本思想算法基本思想Dijkstra算法是解单源最
115、短路径问题的贪心算法。1534.5 4.5 单源最短路径单源最短路径其基本思想基本思想是，设置顶点集合S并不断地作贪心选贪心选择择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。1544.5 4.5 单源最短路径单源最短
116、路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。1554.5 4.5 单源最短路径单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5 初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代过程： 1564.5 4.5 单源最短路径单源最短路径2.2.算法的正确性和计算复杂性算法的正确性和计算复杂性(1)贪心选择
117、性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。1574.6 4.6 最小生成树最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。例如例如，在设计通信网络
118、时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 1584.6 4.6 最小生成树最小生成树1.1.最小生成树性质最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v
119、)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MSTMST性质性质。 1594.6 4.6 最小生成树最小生成树2.Prim2.Prim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪贪心选择心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最最小生成树小生成树。 1604.6 4.6 最小生成树最小生成树利用最小生成树性质和数学归纳法
120、容易证明，上述算法中的边集合边集合T T始终始终包含包含G G的某棵最小生成树中的某棵最小生成树中的边的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。 例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下页图所示。1614.6 4.6 最小生成树最小生成树1624.6 4.6 最小生成树最小生成树在上述Prim算法中，还应当考虑如何有效地找出满如何有效地找出满足条件足条件i i S,jS,j V-SV-S，且权，且权cijcij最小的边最小的边(i,j)(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中
121、，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间计算时间为 1634.6 4.6 最小生成树最小生成树3.Kruskal3.Kruskal算法算法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支
122、T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 1644.6 4.6 最小生成树最小生成树例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。1654.6 4.6 最小生成树最小生成树关于集合的一些基本运算集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列优先队列执行removeMinremoveMin运算。可以用堆堆实现这个优先队列。 对一个由连通分支组成的集合不
123、断进行修改，需要用到抽象数据类型并查集并查集UnionFindUnionFind所支持的基本运算。当图的边数为e时，Kruskal算法所需的计算时间计算时间是 。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。1664.7 4.7 多机调度问题多机调度问题多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NPNP完全问题完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略贪心选择策略有时可以设计出较好的近似算法。 约定，每个作业均可在任何一台机器上加工处理，但未约
124、定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。完工前不允许中断处理。作业不能拆分成更小的子作业。1674.7 4.7 多机调度问题多机调度问题采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当 时，只要将机器i的0, ti时间区间分配给作业i即可，算法只需要O(1)时间。当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。1684.7 4.7 多机调度问题多机调度问题例如，例如，设7个独立作业1,2,3,4
125、,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedygreedy产生的作业调度如下图所示，所需的加工时间为17。 1694.8 4.8 贪心算法的理论基础贪心算法的理论基础借助于拟阵拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法确定何时使用贪心算法可以得到问题的整体最优解十分有用。1.1.拟阵拟阵拟阵M定义为满足下面3个条件的有序对(S,I)：(1)S是非空有限集。(2)I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集必为I的成员。(3)
126、I满足交换性质，即若AI,BI且|A|0，则称拟阵M为带权拟阵带权拟阵。依此权函数，S的任一子集A的权定义为 。2.2.关于带权拟阵的贪心算法关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题最大权独立子集问题。 1724.8 4.8 贪心算法的理论基础贪心算法的理论基础给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集最优子集也一定是极大独立子集。例如，例如，在最小生成树问题可以表示为确定带权拟阵 的最
127、优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。下面给出求带权拟阵最优子集带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。1734.8 4.8 贪心算法的理论基础贪心算法的理论基础Set greedygreedy (M,W)A=; 将S中元素依权值W（大者优先）组成优先队列； while (S!=) S.removeMax(x); if (AxI) A=Ax; return A1744.8 4.8 贪心算法的理论基础贪心算法的理论基础算法greedygreedy的计算时间复杂性为 。引理引理4.24.2( (拟阵的
128、贪心选择性质拟阵的贪心选择性质) )设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设x S是S中第一个使得x是独立子集的元素，则存在S的最优子集A使得x A。算法greedygreedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。1754.8 4.8 贪心算法的理论基础贪心算法的理论基础引理引理4.34.3：设M=(S,I)是拟阵。若S中元素x不是空集的可扩展元素，则x也不可能是S中任一独立子集A的可扩展元素。引理引理4.4(4.4(拟阵的最优
129、子结构性质拟阵的最优子结构性质) )设x是求带权拟阵M(S，I)的最优子集的贪心算法greedygreedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M=(S,I)的最优子集最优子集问题，其中：S=y|y S且x,y II=B|B S-x且Bx IM的权函数是M的权函数在S上的限制(称M为M关于元素x的收缩收缩)。1764.8 4.8 贪心算法的理论基础贪心算法的理论基础定理定理4.5(4.5(带权拟阵贪心算法的正确性带权拟阵贪心算法的正确性) )设M(S,I)是具有权函数W的带权拟阵，算法greedy返回M的最优子集。3.3.任务时间表问题任务时间表问题给定一个单位时间任务单位
130、时间任务的有限集S。关于S的一个时间表时间表用于描述S中单位时间任务的执行次序。时间表中第1个任务从时间0开始执行直至时间1结束，第2个任务从时间1开始执行至时间2结束，第n个任务从时间n-1开始执行直至时间n结束。1774.8 4.8 贪心算法的理论基础贪心算法的理论基础具有截止时间截止时间和误时惩罚误时惩罚的单位时间任务时间表问题可描述如下。(1) n个单位时间任务的集合S=1,2,n；(2) 任务i的截止时间 ,1in,1 n，即要求任务i在时间 之前结束；(3) 任务i的误时惩罚 ,1in,即任务i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚。任务时间表问题任务时间表问题要求确
131、定S的一个时间表（最优时间表）使得总误时惩罚达到最小。1784.8 4.8 贪心算法的理论基础贪心算法的理论基础这个问题看上去很复杂，然而借助于拟阵拟阵，可以用带权拟阵的贪心算法带权拟阵的贪心算法有效求解。对于一个给定的S的时间表，在截止时间之前完成的任务称为及时任务及时任务，在截止时间之后完成的任务称为误时任务误时任务。S的任一时间表可以调整成及时优先形式及时优先形式，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。类似地，还可将S的任一时间表调整成为规范形式规范形式，其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列。1794.8 4.8 贪心算法的理论
132、基础贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。任务时间表问题等价于等价于确定最优时间表中及时任及时任务子集务子集A A的问题。一旦确定了及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即S-A中各任务，由此产生S的一个规范的最优时间表。对时间t=1,2,n，设设 (A)是任务子集A中所有截止时间是t或更早的任务数。考察任务子集A的独立性。1804.8 4.8 贪心算法的理论基础贪心算法的理论基础引理引理4.64.6：对于S的任一任务子集A，下面的各命题是等价的。(1) 任务子集A是独立子集。(2) 对于t=1,2,n
133、， (A)t。(3) 若A中任务依其截止时间非减序排列，则A中所有任务都是及时的。任务时间表问题任务时间表问题要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下面的定理定理表明可用带权拟阵的贪心算法解任务时间表问题。1814.8 4.8 贪心算法的理论基础贪心算法的理论基础定理定理4.74.7：设S是带有截止时间的单位时间任务集，I是S的所有独立任务子集构成的集合。则有序对(S,I)是拟阵。由定理定理4.54.5可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立任务子集A，以A作为最优时间表中的及时任务子集，容易构造最优时间表。任务时间表问题的贪心算法的计算时
134、间复杂性计算时间复杂性是 。其中f(n)是用于检测任务子集A的独立性所需的时间。用引理4.6中性质(2)容易设计一个 时间算法来检测任务子集的独立性。因此，整个算法的计算时间计算时间为 。具体算法greedyJobgreedyJob可描述如P130。1824.8 4.8 贪心算法的理论基础贪心算法的理论基础用抽象数据类型并查集UnionFindUnionFind可对上述算法作进一步改进。如果不计预处理的时间，改进后的算法fasterJobfasterJob所需的计算时间计算时间为 。 183第第5章章 回溯法回溯法184回溯法回溯法有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束
135、条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。185问题的解空间问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：
136、对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间186生成问题状态的基本方法生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继
137、续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法187回溯法的基本思想回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用回溯法解题的一
138、个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。188递归回溯递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x);
139、else for (int i=0;in) output(x); else for (int i=t;i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; 193批处理作业调度批处理作业调度给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和
140、。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。tji机器1机器2作业121作业231作业323这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。194批处理作业调度批处理作业调度解空间：排列树private static void backtrack(int i) if (i n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f;
141、else for (int j = i; j f1)?f2i-1:f1)+mxj2; f+=f2i; if (f half)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; + + - + - + + - - - - +
142、- + + + - - + + - - + - - - +复杂度分析复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。197n后问题后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ198解向量：(x1, x2, , xn)显约束：xi=1,2, ,n隐约束： 1)不同
143、列：xi xj 2)不处于同一正、反对角线：|i-j| |xi-xj|n后问题后问题 private static boolean place (int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (place(t) backtrack(t+1); 1990-1背包问题背包问题解空间：子集树可行性约束函数：上界函数：private static double bound(int i) / 计算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品单位重量价值
144、递减序装入物品 while (i = n & wi = cleft) cleft -= wi; bound += pi; i+; / 装满背包 if (i n) / 到达叶结点 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 检查顶点 i 与当前团的连接 boolean ok = true; for (int j = 1; j bestn) / 进入右子树 xi = 0; backtrack(i + 1); 复杂度分析复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。12453202进一
145、步改进算法的建议进一步改进算法的建议选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。定义Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.,S1的解。从而得到一个更精确的上界函数，若cn+Sin) sum+; else for (int i=1;i=m;i+) xt=i; if (ok(t) backtrack(t+1); private static boolean ok(int k) / 检查颜色可用性 for (int j=1;j=n;j+) if (akj & (xj=xk) return
146、 false; return true; 复杂度分析复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是思考：图的思考：图的m着色问题与图的最着色问题与图的最大团问题有何关系，你能否利用大团问题有何关系，你能否利用这个关系改进最大团问题的上界这个关系改进最大团问题的上界？205旅行售货员问题旅行售货员问题解空间：排列树private static void backtrack(int i) if (i = n) if (axn - 1xn Float.MAX_VALUE
147、& axn1 Float.MAX_VALUE & (bestc = Float.MAX_VALUE | cc+axn - 1xn+axn1bestc) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc+axn - 1xn+axn1; else for (int j = i; j = n; j+) / 是否可进入xj子树? if (axi - 1xj Float.MAX_VALUE & (bestc = Float.MAX_VALUE | cc+axi - 1xjbestc) / 搜索子树 MyMath.swap(x, i, j); cc+=a
148、xi - 1xi; backtrack(i + 1); cc-=axi - 1xi; MyMath.swap(x, i, j); 复杂度分析复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。 206圆排列问题圆排列问题给定n个大小不等的圆c1,c2,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为20
149、7圆圆排列问题排列问题private static float center(int t) / 计算当前所选择圆的圆心横坐标 float temp=0; for (int j=1;jtemp) temp=valuex; return temp; private static void compute() / 计算当前圆排列的长度 float low=0, high=0; for (int i=1;i=n;i+) if (xi-rihigh) high=xi+ri; if (high-lown) compute(); else for (int j = t; j = n; j+) MyMath.
150、swap(r, t, j); float centerx=center(t); if (centerx+rt+r1min) /下界约束 xt=centerx; backtrack(t+1); MyMath.swap(r, t, j); 复杂度分析复杂度分析由于算法backtrack在最坏情况下可能需要计算O(n!)次当前圆排列长度，每次计算需O(n)计算时间，从而整个算法的计算时间复杂性为O(n+1)!) 上述算法尚有许多改进的余地。例如，象1,2,n-1,n和n,n-1, ,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。另一方面，如果所给的n个圆中有k
151、个圆有相同的半径，则这k个圆产生的k!个完全相同的圆排列，只计算一个就够了。 208连续邮资问题连续邮资问题假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。209连续邮资问题连续邮资问题解向量：用n元组x1:n表示n种不同的邮票面值，并约定它们从小到大排列。x1=1是惟一的选择。可行性约束函数：已选定x1:i-1，最大连续邮资区间是1:r
152、，接下来xi的可取值范围是xi-1+1:r+1。如何确定r的值？计算X1:i的最大连续邮资区间在本算法中被频繁使用到，因此势必要找到一个高效的方法。考虑到直接递归的求解复杂度太高，我们不妨尝试计算用不超过m张面值为x1:i的邮票贴出邮资k所需的最少邮票数yk。通过yk可以很快推出r的值。事实上，yk可以通过递推在O(n)时间内解决：for (int j=0; j= xi-2*(m-1);j+) if (yjm) for (int k=1;k=m-yj;k+) if (yj+kyj+xi-1*k) yj+xi-1*k=yj+k; while (yrmaxint) r+;210回溯法效率分析回溯法
153、效率分析通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：(1)产生xk的时间；(2)满足显约束的xk值的个数；(3)计算约束函数constraint的时间；(4)计算上界函数bound的时间；(5)满足约束函数和上界函数约束的所有xk的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。211重排原理重排原理对于许多问题而言，在搜索试探时选取xi的值顺序是任意的。在其他条件相当的前提下，让可取值最少的在其他条件相当的前提下，让可取值最少的xi优先优先。从图中关于同一问题的2棵
154、不同解空间树，可以体会到这种策略的潜力。图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。(a)(b)212第六章第六章 分支限界法分支限界法213第六章第六章 分支限界法分支限界法本章主要知识点本章主要知识点 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 装载问题 6.4 布线问题 6.5 01背包问题 6.6 最大团问题 6.7 旅行售货员问题 6.8 电路板排列问题 6.9 批处理作业调度2146.1 分支限界法的基本思想分支限界法
155、的基本思想1. 分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2156.1 分支限界法的基本思想分支限界法的基本思想2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在
156、这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 2166.1 分支限界法的基本思想分支限界法的基本思想3. 常见的两种分支限界法（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。2176.2 单源最短路径问题单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向
157、图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 2186.2 单源最短路径问题单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。2196.2 单源最短路径问题单源最短路径问题2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。
158、如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。2206.2 单源最短路径问题单源最短路径问题3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 2216.2 单源最短路径问题单源最短路径问题 whi
159、le (true) / 搜索问题的解空间 for (int j=1;j=n;j+) if(aenode.ij Float.MAX_VALUE & enode.length+aenode.ij distj) / 顶点i到顶点j可达，且满足控制约束 distj=enode.length+aenode.ij; pj=enode.i; HeapNode node = new HeapNode(j,distj); heap.put(node); / 加入活结点优先队列 if (heap.isEmpty() break; else enode = (HeapNode) heap.removeMin();
160、顶点顶点I I和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 2226.3 装载问题装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。 2236.3 装载问题装载问题2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点
161、是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。2246.3 装载问题装载问题2. 队列式分支限界法while (true) if (ew + wi = c) enQueue(ew + wi, i); / 检查左儿子结点 enQueue(e
162、w, i); /右儿子结点总是可行的 ew = (Integer) queue.remove().intValue(); / 取下一扩展结点 if (ew = -1) if (queue.isEmpty() return bestw; queue.put(new Integer(-1); / 同层结点尾部标志 ew = (Integer) queue.remove().intValue(); / 取下一扩展结点 i+; / 进入下一层 2256.3 装载问题装载问题3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相
163、应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。2266.3 装载问题装载问题3. 算法的改进/ 检查左儿子结点 int wt = ew + wi; if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0; j-) bestxj = (e.leftChild) ? 1 : 0; e = e.parent; 2296.3 装载问题装载问题5. 优先队列式分支限界法 解装载问题的优先队列式
164、分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 2306.4 布线问题布线问题算法的思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格
165、标记为1，即从起始方格a到这些方格的距离为1。 接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。2316.4 布线问题布线问题Position offset = new Position 4;offset0 = new Position(0, 1); / 右offset1 = new Position(1, 0); / 下offset2 = new Position(0, -1); / 左offset3 = new Position(
166、-1, 0); / 上 定义移动方向的定义移动方向的相对位移相对位移 for (int i = 0; i = size + 1; i+) grid0i = gridsize + 1i = 1; / 顶部和底部 gridi0 = gridisize + 1 = 1; / 左翼和右翼 设置边界的围墙设置边界的围墙2326.4 布线问题布线问题for (int i = 0; i numOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) /
167、 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; q.put(new Position(nbr.row, nbr.col); 找到目标位置后，可以通过回溯方法找到这条最短路径。2336.5 0-1背包问题背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首
168、先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2346.5 0-1背包问题背包问题上界函数while (i = n & wi = cleft) / n表示物品总数，cleft为剩余空间 cleft -= wi; /wi表示i所占空间 b += pi; /pi表示i的价值 i+; if (i = n) b += pi / wi * cleft; / 装填剩余容量装满背包return b; /b为上界函数2
169、356.5 0-1背包问题背包问题 while (i != n + 1) / 非叶结点 double wt = cw + wi; if (wt bestp) bestp = cp + pi; addLiveNode(up,cp + pi,cw + wi,i + 1, enode, true); up = bound(i + 1); if (up = bestp) /检查右儿子节点 addLiveNode(up,cp,cw,i + 1, enode, false); / 取下一个扩展节点（略）分支限界搜索过分支限界搜索过程程2366.6 最大团问题最大团问题1.问题描述 给定无向图G=(V，E)
170、。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 下图G中，子集1，2是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图1，2，5包含。1，2，5是G的最大团。1，4，5和2，3，5也是G的最大团。 2376.6 最大团问题最大团问题2. 上界函数 用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。 在此优先队列式分支限界法中
171、，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。 2386.6 最大团问题最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接 着 继 续 考 察 当 前 扩 展 结 点 的 右
172、儿 子 结 点 。 当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。2396.6 最大团问题最大团问题 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 2406.7 旅行售货员问题旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅
173、费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 2416.7 旅行售货员问题旅行售货员问题2. 算法描述 算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用m
174、inout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。 算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：2426.7 旅行售货员问题旅行售货员问题 1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n
175、-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。 2436.7 旅行售货员问题旅行售货员问题 算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致
176、费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。 算法结束时返回找到的最小费用，相应的最优解由数组v给出。 2446.8 电路板排列问题电路板排列问题算法描述 算法开始时，将排列树的根结点置为当前扩展结点。在do-while循环体内算法依次从活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。 首先考虑s=n-1的情形，当前扩展结点是排列树中的一个叶结点的父结点。x表示相应于该叶结点的电路板排列。计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解。 当sn-1时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每
177、一个儿子结点node，计算出其相应的密度node.cd。当node.cdbestd时，将该儿子结点N插入到活结点优先队列中。2456.8 电路板排列问题电路板排列问题算法描述do if (enode.s = n - 1) / 仅一个儿子结点 int ld = 0; / 最后一块电路板的密度 for (int j = 1; j = m; j+) ld += board enode.xnj; if (ld bestd) / 找到密度更小的电路板排列 x = enode.x; bestd = Math.max(ld, enode.cd); S=n-1S=n-1的情况，计算出的情况，计算出此时的密度和
178、此时的密度和bestdbestd进进行比较。行比较。2466.8 电路板排列问题电路板排列问题算法描述else / 产生当前扩展结点的所有儿子结点 for (int i = enode.s + 1; i = n; i+) HeapNode node = new HeapNode(0, new int m + 1, 0, new int n + 1); for (int j = 1; j = m; j+) / 新插入的电路板 node.nowj = enode.nowj + board enode.xij;2476.8 电路板排列问题电路板排列问题int ld = 0; / 新插入电路板的密度f
179、or (int j = 1; j 0 & totalj != node.nowj) ld+;node.cd = Math.max(ld, enode.cd);if (node.cd bestd)/ 可能产生更好的叶结点 node.s = enode.s + 1; for (int j = 1; j =r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。 这可以作为优先队列式分支限界法中的限界函数。 2506.9 批处理作业问题批处理作业问题3. 算法描述 算法的while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队
180、列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。 首先考虑enode.s=n的情形，当前扩展结点enode是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2 bestc时更新当前最优值bestc和相应的当前最优解bestx。 当enode.sn时，算法依次产生当前扩展结点enode的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。当bb bestc时，将该儿子结点插入到活结点优先队列中。而当bb bestc时，可将结点node舍去。 2516.9 批处理作业问题批处理作业问题 do i
181、f (enode.s = n ) / 叶结点 if (enode.sf2 bestc) bestc = enode.sf2; for (int i = 0; i n; i+) bestxi = enode.xi; 3. 算法描述 当当enodeenode.sf2.sf2bestcbestc时，时，更新当前最优值更新当前最优值bestebeste和和相应的最优解相应的最优解bestxbestx2526.9 批处理作业问题批处理作业问题3. 算法描述else / 产生当前扩展结点的儿子结点 for (int i = enode.s; i n; i+) MyMath.swap(enode.x, en
182、ode.s,i); int f= new int 3; int bb=bound(enode,f); if (bb bestc ) HeapNode node=new HeapNode(enode,f,bb,n); heap.put(node); MyMath.swap(enode.x, enode.s,i); / 完成结点扩展当当bbbbbestcbestc时，将儿时，将儿子结点插入到活结点子结点插入到活结点优先队列中优先队列中253第第7 7章章 概率算法概率算法254随机数随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都
183、是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,an满足其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。255数值概率算法数值概率算法 256用随机投点法计算用随机投点法计算 值值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的
184、概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而 。public static double darts(int n) / 用随机投点法计算值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/(double)n; 257计算定积分计算定积分设f(x)是0，1上的连续函数，且0f(x)1。需要计算的积分为 ,积分I等于图中的面积G。在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为假设向单位正方形
185、内随机地投入n个点(xi,yi)。如果有m个点落入G内，则随机点落入G内的概率258解非线性方程组解非线性方程组求解下面的非线性方程组其中，x1,x2,xn是实变量，fi是未知量x1,x2,xn的非线性实函数。要求确定上述方程组在指定求根范围内的一组解 在指定求根区域D内，选定一个随机点x0作为随机搜索的出发点。在算法的搜索过程中，假设第j步随机搜索得到的随机搜索点为xj。在第j+1步，计算出下一步的随机搜索增量xj。从当前点xj依xj得到第j+1步的随机搜索点。当x时，取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。259舍伍德舍伍德(Sherwood)算法算法设A是一个确定性
186、算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在xXn使得 的可能性。希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。260舍伍德舍伍德(Sherwood)算法算法复习学过的Sherwood算法：（1）线性时间选择算法（2）快速排序算法有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入
187、进行随机洗牌，同样可收到舍伍德算法的效果。例如，对于确定性选择算法，可以用下面的洗牌算法shuffle将数组a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。public static void shuffle(Comparable a, int n) / 随机洗牌算法 rnd = new Random(); for (int i=1;in;i+) int j=rnd.random(n-i+1)+i; MyMath.swap(a, i, j); 261跳跃表跳跃表舍伍德型算法的设计思想还可用于设计高效的数据结构。如果用有序链表来表示一个含有n个元素的有
188、序集S，则在最坏情况下，搜索S中一个元素需要(n)计算时间。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。 262跳跃表跳跃表在一般情况下，给定一个含有n个元素的有序链表，可以将它改造成一个完全跳跃表，使得每一个k级结点含有k+1个指针，分别跳过2k-1，2k-1
189、-1，20-1个中间结点。第i个k级结点安排在跳跃表的位置i2k处，i0。这样就可以在时间O(logn)内完成集合成员的搜索运算。在一个完全跳跃表中，最高级的结点是logn级结点。完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，影响后继元素搜索的效率。263跳跃表跳跃表为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。注意到在一个完全跳跃表中，50%的指针是0级指针；25%的指针是1级指针；(100/2k+1)%的指针是k级指针。
190、因此，在插入一个元素时，以概率1/2引入一个0级结点，以概率1/4引入一个1级结点，以概率1/2k+1引入一个k级结点。另一方面，一个i级结点指向下一个同级或更高级的结点，它所跳过的结点数不再准确地维持在2i-1。经过这样的修改，就可以在插入或删除一个元素时，通过对跳跃表的局部修改来维持其平衡性。 264跳跃表跳跃表注意到，在一个完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针。为了维持跳跃表的平衡性，可以事先确定一个实数0p1，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例约为p。为此目的，在插入一个新结点时，先将其结点级别初始化为0，然后用随机数生
191、成器反复地产生一个0，1间的随机实数q。如果q0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得： 266n后问题后问题对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。 在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的
192、若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。 stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.11267整数因子分解整数因子分解设n1是一个整数。关于整数n的因子分解问题是找出n的如下形式的惟一分解式：其中，p1p2pk是k个素数，m1,m2,mk是k个正整数。如果n是一个合数，则n必有一个非平凡因子x，1xn，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为整数n
193、的因子分割问题。private static int split(int n) int m = (int) Math.floor(Math.sqrt(double)n); for (int i=2; i=m; i+) if (n%i=0) return i; return 1; 事实上，算法split(n)是对范围在1x的所有整数进行了试除而得到范围在1x2的任一整数的因子分割。 268Pollard算法算法在开始时选取0n-1范围内的随机数，然后递归地由产生无穷序列对于i=2k，以及2k1) & (dn) System.out.println(d); if (i=k) y=x; k*=2;
194、对Pollard算法更深入的分析可知，执行算法的while循环约 次后，Pollard算法会输出n的一个因子p。由于n的最小素因子p ，故Pollard算法可在O(n1/4)时间内找到n的一个素因子。269蒙特卡罗蒙特卡罗(Monte Carlo)算法算法在实际应用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。设p是一个实数，且1/2pn/2时，称元素x是数组T的主元素。 public static boolean majority(intt, int
195、 n) / 判定主元素的蒙特卡罗算法 rnd = new Random(); int i=rnd.random(n)+1; int x=ti; / 随机选择数组元素 int k=0; for (int j=1;jn/2); / kn/2 时t含有主元素 public static boolean majorityMC(intt, int n, double e) / 重复 次调用算法majority int k= (int) Math.ceil(Math.log(1/e)/Math.log(2); for (int i=1;i0，算法majorityMC重复调用log(1/) 次算法major
196、ity。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/ )。272素数测试素数测试WilsonWilson定理定理定理定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。费尔马小定理费尔马小定理费尔马小定理费尔马小定理：如果p是一个素数，且0ap，则ap-1(mod p)。 二次探测定理二次探测定理二次探测定理二次探测定理：如果p是一个素数，且0xp，则方程x21(mod p)的解为x=1，p-1。private static int power(int a, int p, int n) / 计算
197、ap mod n，并实施对n的二次探测 int x, result; if (p=0) result=1; else x=power(a,p/2,n); / 递归计算 result=(x*x)%n; / 二次探测 if (result=1)&(x!=1)&(x!=n-1) composite=true; if (p%2)=1) / p是奇数 result=(result*a)%n; return result;public static boolean prime(int n) / 素数测试的蒙特卡罗算法 rnd = new Random(); int a, result; composite
198、=false; a=rnd.random(n-3)+2; result=power(a,n-1,n); if (composite|(result!=1) return false; else return true;算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。273第第8 8章章NPNP完全性理论完全性理论2748.1 计算模型计算模型8.1.1 随机存取机RAM8.1.2 随机存取存储程序机RASP8.1.3 RAM模型的变形与简化8.1.4 图灵机8.1.5 图灵机模型与RAM模型的关系8.1
199、.6 问题变换与计算复杂性归约2758.1.1 随机存取机随机存取机RAMRAM1. RAMRAM的结构的结构2768.1.1 随机存取机随机存取机RAMRAM2. RAMRAM程序程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把解释一：把RAMRAM程序看成是计算一个函数程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数f(xf(x1 1，x x2 2，x xn n)=y )=y 解释二：把解释二：把RAMRAM程序当作一个语
200、言接受器。程序当作一个语言接受器。将字符串S=a1a2an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。 2778.1.1 随机存取机随机存取机RAMRAM3. RAMRAM程序的耗费标准程序的耗费标准标准一：均匀耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。 标
201、准二：对数耗费标准标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则 2788.1.2 随机存取存储程序机随机存取存储程序机RASPRASP1. RASPRASP的结构的结构 RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。2. RASPRASP程序程序的复杂性的复杂性不管是在均匀耗费标准
202、下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。 2798.1.3 RAMRAM模型的变形与简化模型的变形与简化1. 实随机存取机实随机存取机 RRAMRRAM 在RRAM模型下，一个存储单元可以存放一个实数。下列的各运算为基本运算且每个运算只耗费单位时间。 (1)算术运算+，。(2)2个实数间的比较()。(3)间接寻址(整数地址)。(4)常见函数的计算，如三角函数，指数函数，对数函数等。优点：能够方便处理实数；适合
203、于用FORTRAN，PASCAL等高级语言写的算法。 2808.1.3 RAMRAM模型的变形与简化模型的变形与简化2. 直线式程序直线式程序对于许多问题，所设计的RAM程序中的转移指令仅用于重复一组指令，而且重复的次数与问题的输入规模n成比例。在这种情况下，可以用重复地写出相同指令组的方法来消除程序中的循环。由此，对每一个固定的n得到一个无循环的直线式程序。 经过对RAM模型的简化，得到直线式程序的指令系统如下：xy+zxy-zxy*zxy/zxi其中x，y和z是符号地址(或变量)，而i是常数。每条指令耗费一个单位时间。每条指令耗费一个单位时间。2818.1.3 RAMRAM模型的变形与简化
204、模型的变形与简化3. 位式计算位式计算直线式程序计算模型显然是基于均匀耗费标准的。在对数耗费标准下，使用另一个RAM的简化计算模型，称之为位式计算(Bitwise Computation)模型。 除了下列2点外，该计算模型与直线式程序计算模型基本相同：(1)假设所有变量取值0或1，即为位变量。(2)所用的运算是逻辑运算而不是算术运算。用代表与，代表或，代表异或，代表非。 在位式计算模型下，每个逻辑运算指令耗费一个单位时间。在位式计算模型下，每个逻辑运算指令耗费一个单位时间。 2828.1.3 RAMRAM模型的变形与简化模型的变形与简化4. 位向量运算位向量运算( (Bit Vector Op
205、erations)Bit Vector Operations) 若在直线式程序计算模型中，假设所有变量均为位向量，而且所用的运算均为位操作指令，则得到位向量运算计算模型。 例如，要表示一个有100个顶点的图中从顶点v到其余各顶点间有没有边相连，可以用100位的一个位向量表示。若顶点v到顶点vj之间有边相连，则该位向量的第j位为1，否则为0。 缺点：所需的机器字长要远大于其他模型。 2838.1.3 RAMRAM模型的变形与简化模型的变形与简化5. 判定树判定树 判定树是一棵二叉树。它的每个内结点表示一个形如xy的比较。指向该结点左儿子的边相应于xy，标号为。指向该结点右儿子的边相应于xy，标号
206、为。每一次比较耗费一个单位时间。下图是对a，b，c三个数进行排序的一棵判定树。 在判定树模型下，在判定树模型下，算法的时间复杂性算法的时间复杂性可用判定树的高度可用判定树的高度衡量。最大的比较衡量。最大的比较次数是从根到叶的次数是从根到叶的最长路径的长度。最长路径的长度。 2848.1.3 RAMRAM模型的变形与简化模型的变形与简化6. 代数计算树代数计算树ACTACT以x=(x1，x2，xn)为输入的一棵代数计算树T是一棵二叉树，且：(1)每个叶结点表示一个输出结果YES或NO。(2)每个单儿子内部结点(简单结点)v表示下列形式运算指令： op 或 op 或其中， 和 分别是结点v在树T中
207、的祖先结点v1和v2处得到的结果值，或是x的分量；op+，/；c是一个常数。(3)每个有2个儿子的内部结点(分支结点)v，表示下列形式的测试指令： 0或 0或 =0其中， 是结点v在树T中的祖先结点v1处得到的结果值，或是x的分量。 2858.1.3 RAMRAM模型的变形与简化模型的变形与简化7. 代数判定树代数判定树ADT(Algebraic Decision Tree)ADT(Algebraic Decision Tree)在代数计算树T中，若将所有的简单结点都压缩到其最近的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点处同时完成，则计算结果可看作是输入x的一个代数函数fv(x)
208、。由此引出另一个称为代数判定树的计算模型。 代数判定树T是一棵二叉树，且(1)每个叶结点表示输出结果YES或NO。(2)每个内部结点v表示一个形如fv(x1，x2，xn)0的比较。其中，x=( x1，x2，xn)是输入，fv是一个代数函数。 2868.1.4 图灵机图灵机1. 多带图灵机多带图灵机2878.1.4 图灵机图灵机1. 多带图灵机多带图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头，向左移动
209、一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。 k带图灵机可形式化地描述为一个7元组(Q，T，I，b，q0，qf)，其中: (1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是惟一的空白符，bT-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。 (7)是移动函数。它是从QTk的某一子集映射到Q (TL，R，S)k的函数。 2888.1.4 图灵机图灵机1. 多带图灵机多带图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。 图
210、灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。 与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。 2898.1.5 图灵机模型与图灵机模型与RAMRAM模型的关系模型的关系图灵机模型与RAM模型的关系是指同一问题在这2种不同计算模型下的复杂性之间的关系。 定理定理8-3 8-3 对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为 ，那么，算法A在RAM模型下的时间复杂性为 。定理定理8-4 8-4 对于问题P的任何长度为n的输入，设求解问题
211、P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为 ，那么，算法A在k带图灵机模型TM下的时间复杂性为 。 2908.1.6 问题变换与计算复杂性归约问题变换与计算复杂性归约具体地说，假设有2个问题A和B，将问题问题A A变换为问题变换为问题B B是指：(1)将问题A的输入变换为问题B的适当输入。(2)解出问题B。(3)把问题B的输出变换为问题A的正确解。若用O(n)时间能完成上述变换的第(1)步和第(3)步，则称问题A是(n)时间可变换到问题B，且简记为AA(n)(n)B B。其中的n通常为问题A的规模(大小)。当(n)为n的多项式时，称问题A可在多项式时间内变换
212、为问题B。特别地，当(n)为n的线性函数时，称问题A可线性地变换为问题B。 通过问题变换的技巧，可以将2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。2918.1.6 问题变换与计算复杂性归约问题变换与计算复杂性归约命题命题1(1(计算时间下界归约计算时间下界归约) )：若已知问题A的计算时间下界为T(n)，且问题A是(n)可变换到问题B，即A(n)B，则T(n)-O(n)为问题B的一个计算时间下界。命题命题2(2(计算时间上界归约计算时间上界归约) )：若已知问题B的计算时间上界为T(n)，且问题A是(n)可变换
213、到问题B，即A(n)B，则T(n)+O(n)是问题A的一个计算时间上界。 问题的变换与问题的计算复杂性归约的关系：在命题1和命题2中，当(n)=o(T(n)时，问题A的下界归约为问题B的下界，问题B的上界归约为问题A的上界。 2928.1.6 问题变换与计算复杂性归约问题变换与计算复杂性归约通过问题变换获得问题的计算时间下界的例子：(1)判别函数问题：给定n个实数 ，计算其判别函数 。 元素惟一性问题可以在O(1)时间内变换为判别函数问题。任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为0，即可得到元素惟一性问题的解。由命题1即知，元素惟一性问题的计算时间下界 也是
214、判别函数问题的一个计算时间下界。(2)最接近点对问题：给定平面上n个点，找出这n个点中距离最近的2个点。在元素惟一性问题中，将每一个实数 ，1in，变换为平面上的点( ，0)，1in，则元素惟一性问题可以在线性时间内变换为最接近点对问题。 2938.2 P类与类与NP类问题类问题8.2.1 非确定性图灵机8.2.2 P类与NP类语言8.2.3 多项式时间验证2948.2.1 非确定性图灵机非确定性图灵机 非确定性图灵机非确定性图灵机（ NDTMNDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数具有不确定性具有不
215、确定性，即对于QTk中的每一个值(q;x1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有惟一的一个子集子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。 在图灵机计算模型中，移动函数是单值的是单值的，即对于QTk中的每一个值，当它属于的定义域时，Q(TL，R，S)k中只有惟一的值与之对应，称这种图灵机为确定性图灵机确定性图灵机，简记为DTMDTM(Deterministic Turing Machine)。 2958.2.2 P P类与类与NPNP类语言类语言 P类和NP类语言的定义： P=L|L是一个能在多项式时间内多项式时间内
216、被一台DTMDTM所接受的语言 NP=L|L是一个能在多项式时间多项式时间内被一台NDTMNDTM所接受的语言由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故P P NP NP。 2968.2.2 P P类与类与NPNP类语言类语言 NPNP类语言举例类语言举例无向图的团问题无向图的团问题。 该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子完全子图图( (团团) )，即判定是否存在VV，|V|=k，且对于所有的u，vV，有(u，v)E。 若用邻接矩阵表示
217、图G，用二进制串表示整数k，则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言： CLIQUE=w#v|w，v0，1*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。 2978.2.2 P P类与类与NPNP类语言类语言 接受该语言CLIQUE的非确定性算法非确定性算法：用非确定性选择指令选出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否是团问题的一个解。算法分为3个阶段： 算法的第一阶段将输入串w#v分解，并计算出n= ，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可 在时间内完成。 在算法
218、的第二阶段中，非确定性地选择V的一个k元子集VV。 算法的第三阶段是确定性地检查V的团性质。若V是一个团则接受输入，否则拒绝输入。这显然可以在 时间内完成。因此，整个算法的时间复杂性为 。非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUENP。 2988.2.3 多项式时间验证多项式时间验证 VP=L|L*，为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X*，XL当且仅当存在Y*，|Y|p(|X|)且A(X，Y)=1。 多项式时间可验证语言类VP可定义为： 定理定理8-58-5：VP=NP。（证明见书本） 例如(哈密顿回路问题哈密顿回路问题)：一个无
219、向图G含有哈密顿回路吗? 无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE 定义该问题如下：HAM-CYCLE=G|G含有哈密顿回路 2998.3 NP完全问题完全问题8.3.1 多项式时间变换8.3.2 Cook定理3008.3.1 多项式时间变换多项式时间变换 定义：定义：语言L是NP完全的当且仅当 (1)LNP； (2)对于所有LNP有L p L。 如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NPNP难难的。所有NP完全语言构成的语言类称为NPNP完完全语言类全语言类，记为NPCNPC。 设 ， 是2个语言。所谓语言 能在多
220、项式时间内变换为语言 (简记为 p )是指存在映身f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵机； (2)对于所有x ，x ，当且仅当f(x) 。 3018.3.1 多项式时间变换多项式时间变换 定理定理8-68-6：设L是NP完全的，则 (1)LP当且仅当PNP； (2)若Lp ，且 NP，则 是NP完全的。 定理定理8-68-6的的(2)(2)可用可用来证明问题的来证明问题的NPNP完完全性。但前提是：全性。但前提是：要有第一个要有第一个NPNP完全完全问题问题L L。3028.3.2 CookCook定理定理 定理定理8-7(8-7(CookCook定理定理) )：布尔表
221、达式的可满足性问题SAT是NP完全的。 证明：SAT的一个实例是k个布尔变量 ， 的m个布尔表达式 ， 若存在各布尔变量 (1ik)的0，1赋值，使每个布尔表达式 (1im)都取值1，则称布尔表达式 是可满足的。 SATNP是很明显的。对于任给的布尔变量 ， 的0，1赋值，容易在多项式时间内验证相应的 的取值是否为1。因此，SATNP。 现在只要证明对任意的LNP有LpSAT即可。（详细证明见书本P307310）3038.4 一些典型的一些典型的NP完全问题完全问题部分NP完全问题树3048.4.1 合取范式的可满足性问题合取范式的可满足性问题（CNF-SATCNF-SAT） 要证明CNF-S
222、ATNPC，只要证明在Cook定理中定义的布尔表达式A，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：问题描述：给定一个合取范式，判定它是否可满足。 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不是合取范式。 3058.4.2 3 3元合取范式的可满足性问题元合取范式的可满足性问题（3-3-SATSAT）证明思路：证明思路： 3-SATNP是显而易见的。为了
223、证明3-SATNPC，只要证明CNF-SATp 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。 问题描述：问题描述：给定一个3元合取范式，判定它是否可满足。 3068.4.3 团问题团问题CLIQUECLIQUE 证明思路：证明思路： 已经知道CLIQUENP。通过3-SATpCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的。 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|=k，且对任意u，wV有(u，w)E。 3078.4.4 顶点覆盖问题顶点覆盖问题（VERTEX-COVERVE
224、RTEX-COVER） 证明思路：证明思路： 首先，VERTEX-COVERNP。因为对于给定的图G和正整数k以及一个“证书”V，验证|V|=k，然后对每条边(u，v)E，检查是否有uV或vV，显然可在多项式时间内完成。 其次，通过CLIQUEpVERTEX-COVER来证明顶点覆盖问题是NP难的。 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在VV，|V|=k，使得对于任意(u，v)E有uV或vV。如果存在这样的V，就称V为图G的一个大小为k顶点覆盖。 3088.4.5 子集和问题子集和问题（SUBSET-SUMSUBSET-SUM） 问题描述：问题描述：给定整
225、数集合S和一个整数t，判定是否存在S的一个子集SS，使得S中整数的和为t。例如，若S=1，4，16，64，256，1040，1041，1093，1284，1344且t=3754，则子集S=1，16，64，256，1040，1093，1284是一个解。 证明思路：证明思路： 首先，对于子集和问题的一个实例，给定一个“证书”S，要验证t= 是否成立，显然可在多项式时间内完成。因此，SUBSET-SUMNP； 其次，证明VERTEX-COVERpSUBSET-SUM。 3098.4.6 哈密顿回路问题哈密顿回路问题（HAM-CYCLEHAM-CYCLE） 证明思路：证明思路： 首先，已知哈密顿回路问
226、题是一个NP类问题。 其次，通过证明3-SATpHAM-CYCLE，得出：HAM-CYCLENPC。 问题描述：问题描述：给定无向图G=(V，E)，判定其是否含有一哈密顿回路。 3108.4.7 旅行售货员问题旅行售货员问题TSPTSP 首先，给定TSP的一个实例(G，c，k)，和一个由n个顶点组成的顶点序列。验证算法要验证这n个顶点组成的序列是图G的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过k。这个过程显然可在多项式时间内完成，即TSPNP。 其次，旅行售货员问题与哈密顿回路问题有着密切的联系。哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即HAM-
227、CYCLEpTSP。从而，旅行售货员问题是NP难的。 因此，TSPNPC。 问题描述：问题描述：给定一个无向完全图G=(V，E)及定义在VV上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。 311第第9章章 近似算法近似算法312第第9章章 近似算法近似算法 迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法近似算法。3139.1 近似算
228、法的性能近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比近似算法的性能比定义为= 。在通常情况下，该性能比是问题输入规模n的一个函数(n)，即 (n)。该近似算法的相对误差近似算法的相对误差定义为= 。若对问题的输入规模n，有一函数(n)使得 (n)，则称(n)为该近似算法的相对误差界近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)(n)-1(n)-1。 3149.2 顶点覆盖问题的近似算法顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集
229、V的一个子集VV，使得若(u,v)是G的一条边，则vV或uV。顶点覆盖V的大小是它所包含的顶点个数|V|。 VertexSet approxVertexCoverapproxVertexCover ( Graph g ) cset=； e1=g.e； while (e1 != ) 从e1中任取一条边(u,v)； cset=csetu,v； 从e1中删去与u和v相关联的所有边； return c CsetCset用来存储顶点用来存储顶点覆盖中的各顶点。初覆盖中的各顶点。初始为空，不断从边集始为空，不断从边集e1e1中选取一边中选取一边( (u,v)u,v)，将边的端点加入将边的端点加入csetc
230、set中，并将中，并将e1e1中已中已被被u u和和v v覆盖的边删去，覆盖的边删去，直至直至csetcset已覆盖所有已覆盖所有边。即边。即e1e1为空。为空。 3159.2 顶点覆盖问题的近似算法顶点覆盖问题的近似算法 图图( (a)a)(e)(e)说明说明了算法的运行过程了算法的运行过程及结果。及结果。( (e)e)表示表示算法产生的近似最算法产生的近似最优顶点覆盖优顶点覆盖csetcset，它由顶点它由顶点b,c,d,e,f,gb,c,d,e,f,g所组所组成。成。( (f)f)是图是图G G的一的一个最小顶点覆盖，个最小顶点覆盖，它只含有它只含有3 3个顶点：个顶点：b,db,d和和
231、e e。 算法approxVertexCoverapproxVertexCover的性能比为2。 3169.3 旅行售货员问题近似算法旅行售货员问题近似算法 问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。 比如，费用函数c往往具有三角不等式性质三角不等式性质，即对任意的3个顶点u,v,wV，有：c(u,w)c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。 旅行售货员问题的一些特殊性质特殊性质：3179.3.1 具有三角不等式性质的具
232、有三角不等式性质的旅行售货员问题旅行售货员问题 对于给定的无向图G，可以利用找图图G G的最小生成树的最小生成树的算法设计找近似最优的旅行售货员回路的算法。 void approxTSPapproxTSP (Graph g) (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回； 当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。 3189.3.1 具有三角不等式性质的具有三角不等式性质的旅行售货员问题举
233、例旅行售货员问题举例( (b)b)表示找到的最小生成表示找到的最小生成树树T T；( (c)c)表示对表示对T T作前序作前序遍历的次序；遍历的次序；(d)(d)表示表示L L产产生的哈密顿回路生的哈密顿回路H H；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路。行售货员回路。 3199.3.2 一般一般的的旅行售货员问题旅行售货员问题 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NPP=NP。换句话说，若PNP，则对任意常数1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。 3209.4 集合覆盖问题
234、的近似算法集合覆盖问题的近似算法 问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。 集合覆盖问题的一个实例X,F由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X= 。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X= ，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得 |C*|=min|C|CF且C覆盖X 3219.4 集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题举例：用用1212个黑点表示集个黑点表示集合合X X。F=
235、S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如图所示。如图所示。容易看出，对于这容易看出，对于这个例子，最小集合个例子，最小集合覆盖为：覆盖为：C=S3,S4,S5,C=S3,S4,S5,。 3229.4 集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题近似算法贪心算法 算法的循环体最多算法的循环体最多执行执行min|X|min|X|，|F|F|次。次。而循环体内的计算显然而循环体内的计算显然可在可在O(|X|F|)O(|X|F|)时间内完时间内完成。因此，算法的计算成。因此，算法的计算时间为时间为O(|X|F|min|X|O(|X|F|min|X|，
236、|F|)|F|)。由此即知，该由此即知，该算法是一个多项式时间算法是一个多项式时间算法。算法。 Set greedySetCovergreedySetCover (X,F) U=X； C=； while (U !=) 选择F中使|SU|最大的子集S； U=U-S； C=CS； return C； 3239.5 子集合问题的近似算法子集合问题的近似算法 问题描述：设子集和问题的一个实例为S,t。其中，S=x1，x2，xn是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 。3249.5.1 子集合问题的指数时间算法子集合问题的指数时间算法int exactSubse
237、tSumexactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1；i=n；i+) Li=mergeLists(Li-1,Li-1+Si)； 删去Li中超过t的元素； return max(Ln)；算法以集合算法以集合S=xS=x1 1，x x2 2，x xn n 和目标值和目标值t t作为输入。算法中作为输入。算法中用到将用到将2 2个有序表个有序表L1L1和和L2L2合并成为一个新合并成为一个新的有序表的算法的有序表的算法mergeListsmergeLists(L1,L2)(L1,L2)。 3259.5.2 子集合问题的完全多项式子集合问题的完全
238、多项式时间近似格式时间近似格式 基于算法exactSubsetSum，通过对表Li作适当的修整建立一个子集和问题的完全多项式时间近似格式完全多项式时间近似格式。 在对表Li进行修整时，用到一个修整参数，01。用参数修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-)yzy。可以将z看作是被删去元素y在修整后的新表L1中的代表。 举例：举例：若=0.1，且L=10,11,12,15,20,21,22,23,24,29，则用对L进行修整后得到L1=10，12，15，20，23，29。其中被删去的数11由10来代表，21和22由20来代
239、表，24由23来代表。 3269.5.2 子集合问题的完全多项式子集合问题的完全多项式时间近似格式时间近似格式对有序表L修整算法List trimtrim(L,) int m=|L|； L1=L1； int last=L1； for (int i=2；i=m；i+) if (last(1-)*Li) 将Li加入表L1的尾部； last=Li； return L1； 子集和问题近似格式int approxSubsetSum approxSubsetSum(S,t,) n=|S|； L0=0； for (int i=1；i=n；i+) Li=Merge-Lists(Li-1,Li-1+Si)； L
240、i=Trim(Li,/n)； 删去Li中超过t的元素； return max(Ln)； 327第第1010章章 算法优化策略算法优化策略328算法设计策略的比较与选择算法设计策略的比较与选择 329最大子段和问题最大子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,an,求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为。依此定义，所求的最优值为:例如: A=(-2，11，-4，13，-5，-2)最大子段和为330简单算法简单算法public static int maxSum() int n=a.length-1; int sum=0; for (int
241、i=1;i=n;i+) int thissum=0; for (int j=i;j=n;j+) for (int k=i;ksum) sum=thissum; besti=i; bestj=j; return sum; thissum+=aj; 注意到 ，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间。331分治算法分治算法如果将所给的序列a1:n分为长度相等的2段a1:n/2和an/2+1:n，分别求出这2段的最大子段和，则a1:n的最大子段和有3种情况。(1)a1:n的最大子段和与a1:n/2最大子段和相同；(2)a1:n的最大子段和与an/2+1:n最大子段
242、和相同；(3)a1:n的最大子段和为 ，且1in/2，n/2+1jn。对于情形(3)。容易看出，an/2与an/2+1在最优子序列中。因此，可以在a1:n/2中计算出 ，并在an/2+1:n中计算出 。则s1s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。复杂度分析复杂度分析T(n)=O(nlogn)332动态规划算法动态规划算法记 ，1 j n，则所求的最大子段和为当bj-10时bj=bj-1+aj，否则bj=aj。由此可得计算bj的动态规划递归式bj=maxbj-1+aj，aj， 1 j n算法显然需要O(n)计算时间和O(n)空间。public static int
243、 maxSum() int n=a.length-1; int sum=0, b=0; for (int i=1;i0) b+=ai; else b=ai; if (bsum)sum=b; return sum; 333最大子矩阵和问题最大子矩阵和问题记 最大子矩阵和问题的最优值为由于其中， 设 ，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。 由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)。334最大最大m子段和问题子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,an,以及一个正整数m，要求确定
244、序列的m个不相交子段，使这m个子段的总和达到最大。设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段含aj(1 i m，i j n)。则所求的最优值显然为与最大子段和问题类似地，计算b(i，j)的递归式为初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。 优化：注意到在上述算法中，计算bij时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。 335动态规划加速原理动态规划加速原理 四边形不
245、等式336货物储运问题货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法337四边形不等式四边形不等式货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于 ,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i
246、,j)满足 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即338四边形不等式四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而 s(i,j) s(i,j+1) s(i+1,j+1)，i j改进后算法speedDynamicProgramming所需的计算时间为 339问题的算法特征问题的算法特征340贪心策略贪心策略采用每次合并集装箱数最少的相邻2堆货物的贪心策略，并不能得到最优解。适当放松相邻性约束，引入相
247、容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。最小相容结点对ai和aj 是满足下面条件的结点对：（1）结点ai和aj 之间没有方形结点；（2）在所有满足条件（1）的结点中ai+aj的值最小；（3）在所有满足条件（1）和（2）的结点中下标 i 最小；（4）在所有满足条件（1）（2）和（3）的结点中下标 j 最小。相应的最小相容合并树，如图所示。341相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优
248、合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。中所处的层序相同。中所处的层序相同。中所处的层序相同。 根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。342算算 法法1. 组合阶段: 将给定的n个数作为方形结点依序从左到右排列，a1，a2，an。反复删除序列中最小相容结点对ai和aj，(ib(i)。设区间I(k)( ki )是区间集S(i)中的一个区间
249、，1 i n。如果对于S(i)的任意扩展S(i)T，当区间JT且在S(i)T中有从I(1)到J的路时，在S(i)T中从I(1)到J的任一最短路都不含区间I(k)，则称区间I(k)是S(i)中的无效区间。若S(i)中的区间I(k)不是无效区间则称其为S(i)中的有效区间。345带权区间最短路问题带权区间最短路问题性质性质1：区间I(k)是S(i)中的有效区间，则对任意kji，区间I(k)是S(j)中的有效区间。另一方面，若区间I(k)是S(i)中的无效区间，则对任意ji，区间I(k)是S(j)中的无效区间。性质性质2：集合S(i)中所有有效区间的并覆盖从a(1)到b(j)的线段，其中b(j)是S
250、(i)的最右有效区间的右端点。性质性质3：区间I(i)是集合S(i)中的有效区间当且仅当在S(i)中有一条从I(1)到I(i)的路。 性质性质4：当ik且dist(i,i)dist(k,i)时，I(k)是S(i)中的无效区间。 性质性质5：设I(j(1)，I(j(2)，I(j(k)是S(i)中的有效区间，且j(1)j(2)k），且dist(i,i)k且dist(i,i)1)不包含S(k-1)中任一有效区间I(j)的右端点b(j)，则对任意ik，I(k)是S(i)中的无效区间。 346带权区间图的最短路算法带权区间图的最短路算法算法算法shortestIntervalPaths步骤步骤1：dis
251、t(1,1)w(1)；步骤步骤2：for (i=2;i=n;i+)(2.1): j=min k | a(i)b(k);1ki ;if (j不存在) dist(i,i)+;else dist(i,i)dist(j,i-1)+w(i);(2.2): for (ki)if (dist(i,i)dist(k,i-1) dist(k,i)+;else dist(k,i)dist(k,i-1);步骤步骤3：for (i=2;i=n;i+) if (dist(i,n)=+) j=min k | (dist(k,n)+)&(a(i)b(k) ;dist(i,n)=dist(j,n)+w(i);上述算法的关键是
252、有效地实现步骤(2.1)和(2.2) 347实现方案实现方案1 1用一棵平衡搜索树（2-3树）存储当前区间集S(i)中的有效区间。以区间的右端点的值为序。如图所示。(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，在最坏情况下需要时间O(logn)。(2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间O(logn)。综上，算法shortestIntervalPaths用平衡搜索树的实现方案，在最坏情况下的计算时间复杂性为O(nlogn)。348实现方案实现方案2 2采用并查集结构。用整数k表示区间I(k),1kn。初始时每个元素k
253、构成一个单元素集，即集合k是k，1kn。(1)每个当前有效区间I(k)在集合k中。 (2)对每个集合S(i)，设L(S(i)=I(k)|I(k)是S(i)的无效区间，且I(k)与S(i)的任一有效区间均不相交 , L(S(i)中所有区间均位于S(i)的所有有效区间并的右侧。 (3)用一个栈AS存放当前有效区间I(i(1)，I(i(2)，I(i(k)。I(i(k)是栈顶元素。该栈称为当前有效区间栈。(4)对于1kn，记prev(I(k)=minj|a(k)ai由aj+ak, kji所构成。 private static void backtrack(int step) / 解最短加法链问题的标准
254、回溯法 int i,j,k; if (astep=n) / 找到一条加法链 if (step=1;i-) if (2*aiastep) for (j=i;j=1;j-) k=ai+aj; astep+1=k; if (kastep)&(k2maj。由于加倍是加法链中元素增大的最快的方式，即ai2ai-1，所以从aj到ai至少需要m+1步。如果预期在状态空间树T的第d层找到关于n的一条加法链，则以状态空间树第i层结点ai为根的子树中，可在第d层找到一条加法链的必要条件是2d-iain。当 时，状态空间树中以结点ai为根的子树中不可能在第d层之前找到最短加法链。 设在求正整数n的最短加法链的逐步深
255、化迭代搜索算法中，当前搜索深度为d。且正整数可表示为n=2t(2k+1)，k0，则在状态空间树的第i层结点ai处的一个剪枝条件是354最短加法链长的上界最短加法链长的上界与加法链问题密切相关的幂树给出了l(n)的更精确的上界。 假设已定义了幂树T的第k层结点，则T的第k+1层结点可定义如下。依从左到右顺序取第k层结点ak，定义其按从左到右顺序排列的儿子结点为ak+aj，0jk。其中a0,a1,ak，是从T的根到结点ak的路径。且ak+aj在T中未出现过。含正整数n的部分幂树T容易在线性时间内用迭代搜索方式构造出来。355优化算法优化算法 综合前面的讨论，对构造最短加法链的标准回溯法作如下改进。(1)采用逐步深化迭代搜索策略；(2)利用l(n)的下界lb(n)对迭代深度作精确估计；(3)采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜索进程；(4)用幂树构造l(n)的精确上界ub(n)。 当lb(n)=ub(n)时，幂树给出的加法链已是最短加法链。 当lb(n)ub(n)时，用改进后的逐步深化迭代搜索算法，从深度d=lb(n)开始搜索。 356
