算法设计与分析(王晓东).ppt
356页
中国计算机学会中国计算机学会“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 算法复杂性分析本章主要知识点：4 1.1 算法与程序算法与程序•输 入：有零个或多个外部量作为算法的输入 •输 出：算法产生至少一个量作为输出 •确定性：组成算法的每条指令清晰、无歧义 •有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限是算法用某种程序设计语言的具体实现 程序可以不满足算法的性质(4)即有限性 是满足下述性质的指令序列算法：程序：5 1.从机器语言到高级语言的抽象1.2 表达算法的抽象机制表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。
1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；6 2.抽象数据类型1.2 表达算法的抽象机制表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析 7 在本书中，采用Java语言描述算法1.1.JavaJava程序结构程序结构 1.3 描述算法描述算法以下，对JavaJava语言的若干重要特性作简要概述。
（1）Java程序的两种类型：应用程序和appletapplet区别：应用程序的主方法为main，其可在命令行中用命令语句 java 应用程序名 来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行2）包：java程序和类可以包(packages)的形式组织管理 （3）import语句：在java程序中可用import语句加载所需的包例如，import java.io.*;语句加载java.io包 8 1.3 描述算法描述算法2.2.JavaJava数据类型数据类型数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）如:int k;对非基本数据类型：语句 String s; 并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立 s = new StringString(“Welcome”);StringString s = new StringString(“Welcome”);9 1.3 描述算法描述算法表格表格1-1 1-1 JavaJava基本数据类型基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1[true,false]byte08[-128,127]char\u000016[\u0000,\uFFFF]double0.064±4.9*10-324 ~ ±1.8*10308float0.032±1.4*10-45 ~ ±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]10 1.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的自然对数tan(x)x的正切11 1.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; } 12 1.3 描述算法描述算法4.4.异常异常 Java的异常提供了一种处理错误的方法。
当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理 通常用trytry块来定义异常处理每个异常处理由一个catchcatch语句组成 public static void main(String [] args) { try { f ( ); } catch (exception1) { 异常处理; } catch (exception2) { 异常处理; } … finally { finally块; } } 13 1.3 描述算法描述算法5.5.JavaJava的类的类(4)访问修饰访问修饰公有(public) 私有(private)保护(protected) Java的类一般由4个部分组成：(1)类名类名(2)数据成员数据成员(3)方法方法14 1.3 描述算法描述算法6.6.通用方法通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值 public static void swap(int [] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void swap(object [] a, int i, int j) { object temp = a[i]; a[i] = a[j]; a[j] = temp; } 该方法只适用于该方法只适用于整型数组整型数组该方法具有通用性，适用该方法具有通用性，适用于于ObjectObject类型及其所有子类型及其所有子类类 以上方法修改如下：以上方法修改如下：15 1.3描述算法描述算法6.6.通用方法通用方法 （（1 1））ComputableComputable界面界面 public static Computable sum(Computable [] a, int n) { if (a.length == 0) return null; Computable sum = (Computable) a[0].zero(); for (int i = 0; i < n; i++) sum.increment(a[i]); return sum;}利用此界面使利用此界面使方法方法sumsum通用化通用化 16 1.3 描述算法描述算法6.6.通用方法通用方法 （（2 2））java.lang.Comparable java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。
例如java.lang.CpareTo(y)返回x-y的符号，当x
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 通常，让A隐含在复杂性函数名当中） 19 1.4 算法复杂性分析算法复杂性分析最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性： 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率20 1.4 算法复杂性分析算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Ω、θ、o 设f(N)和g(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) 21 1.4 算法复杂性分析算法复杂性分析 Ω Ω的定义的定义：如果存在正的常数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章章 递归与分治策略递归与分治策略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(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 算法总体思想算法总体思想•将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解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) 分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之分而治之凡治众如治寡，分数是也。
凡治众如治寡，分数是也孙子兵法孙子兵法27 2.1 2.1 递归的概念递归的概念•直接或间接地调用自身的算法称为递归算法递归算法用函数自身给出定义的函数称为递归函数递归函数•由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解这自然导致递归过程的产生•分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法下面来看几个实例28 2.1 2.1 递归的概念递归的概念例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果29 2.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) return 1; return fibonacci(n-1)+fibonacci(n-2); }30 31 2.1 2.1 递归的概念递归的概念例例3 3 Ackerman函数函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数双递归函数。
AckermanAckerman函数A(nA(n，，m)m)定义如下：32 2.1 2.1 递归的概念递归的概念例例3 3 Ackerman函数函数前2例中的函数都可以找到相应的非递归方式定义：但本例中的但本例中的AckermanAckerman函数却无法找到非递归的定义函数却无法找到非递归的定义33 2.1 2.1 递归的概念递归的概念例例3 3 AckermanAckerman函数函数•A(n，m)的自变量m的每一个值都定义了一个单变量函数：•M=0时，A(n,0)=n+2•M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n•M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n •M=3时，类似的可以推出•M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数34 2.1 2.1 递归的概念递归的概念例例3 3 AckermanAckerman函数函数•定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。
•定义其拟逆函数α(n)为：α(n)=min{k｜A(k)≥n}即α(n)是使n≤A(k)成立的最小的k值•α(n)在复杂度分析中常遇到对于通常所见到的正整数n，有α(n)≤4α(n)≤4但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大35 2.1 2.1 递归的概念递归的概念例例4 4 排列问题排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}集合X中元素的全排列记为perm(X)ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成 36 2.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1正整数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+137 (2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n因此，q(1,m)=11) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤n-1 的划分组成3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成2.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。
可以建立q(n,m)的如下递归关系38 2.1 2.1 递归的概念递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)可以建立q(n,m)的如下递归关系正整数n的划分数p(n)=q(n,n) 39 40 2.1 2.1 递归的概念递归的概念例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上41 在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题当n=1时，问题比较简单此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。
当n＞1时，需要利用塔座c作为辅助塔座此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做由此可以设计出解Hanoi塔问题的递归算法如下2.1 2.1 递归的概念递归的概念例例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，，，，移动规则不变，求移动步数最移动规则不变，求移动步数最移动规则不变，求移动步数最移动规则不变，求移动步数最小的方案。
小的方案小的方案小的方案42 递归小结递归小结优点：优点：结构清晰，可读性强，而且容易用数学归结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便调试程序带来很大方便缺点：缺点：递归算法的运行效率较低，无论是耗费的递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法计算时间还是占用的存储空间都比非递归算法要多43 递归小结递归小结解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消除递归调用，使其转化为非递归算法化为非递归算法1.1.采用一个用户定义的栈来模拟系统的递归调用采用一个用户定义的栈来模拟系统的递归调用工作栈该方法通用性强，但本质上还是递归，工作栈该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化只不过人工做了本来由编译器做的事情，优化效果不明显效果不明显2.2.用递推来实现递归函数用递推来实现递归函数3.3.通过通过CooperCooper变换、变换、反演变换能反演变换能将一些递归转化将一些递归转化为尾递归，从而迭代求出结果为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限但其适用范围有限44 分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：•该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；•该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质•利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；•该问题所分解出的各个子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题题之间不包含公共的子问题 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。
这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好45 分治法的基本步骤分治法的基本步骤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个子问题的处理方法是行之有效的这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好46 分治法的复杂性分析分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。
设分解阀值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)的增长速度通常假定T(n)是单调上升的，从而当mi≤n
这就说明了此问题满足分治法的第二个和第三个适用条件 分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件给定已按升序排好序的给定已按升序排好序的n个元素个元素a[0:n-1]，，现要在这现要在这n个元素中找个元素中找出一特定元素出一特定元素x分析：分析：ü该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；ü该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;ü分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；ü分解出的各个子问题是相互独立的分解出的各个子问题是相互独立的 48 二分搜索技术二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a[0:n-1]，，现要在这现要在这n个元素中找个元素中找出一特定元素出一特定元素x据此容易设计出二分搜索算法二分搜索算法：public static int binarySearch(int [] a, int x, int n) { // 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x // 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left <= right) { int middle = (left + right)/2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; } return -1; // 未找到x }算法复杂度分析：算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。
因此，在最坏情况下，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 = 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复杂度分析复杂度分析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 Transform)的产生该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决Ø是否能找到线性时间的算法？？？目前为止还没有结果。
52 StrassenStrassen矩阵乘法矩阵乘法A和B的乘积矩阵C中的元素C[i,j]定义为: 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)53 StrassenStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进54 StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进55 StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法: O(n2.81)u更快的方法??ØHopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。
或许应当研究３×３或５×５矩阵的更好算法Ø在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性目前最好的计算时间上界是 O(n2.376)Ø是否能找到O(n2)的算法？？？目前为止还没有结果56 棋盘覆盖棋盘覆盖在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖57 棋盘棋盘覆盖覆盖当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题递归地使用这种分割，直至棋盘简化为棋盘1×1 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, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; // 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} }复杂度分析复杂度分析T(n)=O(4k) 渐进意义下的最优算法59 合并排序合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
public static void mergeSort(Comparable a[], int left, int right) { if (left 的逆序对数62 快速排序快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少private static void qSort(int p, int r) { if (p {6, 7, 5, 2, 5, 8}{5, 2, 5} 6 {7, 8}64 private static int randomizedPartition (int p, int r) { int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); }快速排序快速排序 快速排序算法的性能取决于划分的对称性通过修改算法partition，可以设计出采用随机选择策略的快速排序算法在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)&稳定性：不稳定稳定性：不稳定65 线性时间选择线性时间选择给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素private static Comparable randomizedSelect(int p,int r,int k) { if (p==r) return a[p]; int i=randomizedpartition(p,r), j=i-p+1; if (k<=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); }在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。 66 线性时间选择线性时间选择如果能性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下在最坏情况下用O(n)时间完成选择任务例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 由此可得T(n)=O(n)67 l将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个小于基准x同理，基准x也至少比3(n-5)/10个元素小而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。 68 private static Comparable select (int p, int r, int k) { if (r-p<5) { //用某个简单排序算法对数组a[p:r]排序; bubbleSort(p,r); return a[p+k-1]; } //将a[p+5*i]至a[p+5*i+4]的第3小元素 //与a[p+i]交换位置; //找中位数的中位数，r-p-4即上面所说的n-5 for ( int i = 0; i<=(r-p-4)/5; i++ ) { int s=p+5*i, t=s+4; for (int j=0;j<3;j++) bubble(s,t-j); 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/4=19n/20=εn，0<ε<1这是使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|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2Ø能否性时间内找到能否性时间内找到p3,q3？？70 最接近点对问题最接近点对问题u如果S的最接近点对是{p3,q3}，即|p3-q3| u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点由图可以看出，如果如果(m-d,m]中有中有S中的点，则此点就是中的点，则此点就是S1中最大点中最大点u因此，我们用线性时间就能找到区间(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=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2Ø能否性时间内找到能否性时间内找到p,q？？72 最接近点对问题最接近点对问题u考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d满足这个条件的满足这个条件的P2中的中的点一定落在一个点一定落在一个d×2d的矩形的矩形R中中u由d的意义可知，P2中任何2个S中的点的距离都不小于d。 由此可以推出矩形矩形R中最多只有中最多只有6个个S中的点中的点u因此，在分治法的合并步骤中最多只需要检查最多只需要检查6×n/2=3n个个候选者候选者能否性时间内找到能否性时间内找到p3,q3？？证明证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点设u，v是位于同一小矩形中的2个点，则distance(u,v) 按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单这时只要让这2个选手进行比赛就可以了123456782143658734127856432187655678123465872143785634128765432176 循环赛日程表循环赛日程表设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单这时只要让这2个选手进行比赛就可以了123456782143658734127856432187655678123465872143785634128765432177 第第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)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 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 动态规划基本步骤动态规划基本步骤•找出最优解的性质，并刻划其结构特征。 •递归地定义最优值•以自底向上的方式计算出最优值•根据计算最优值时得到的信息，构造最优解83 完全加括号的矩阵连乘积完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000, 10500, 36000, 87500, 34500u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式84 矩阵连乘问题矩阵连乘问题n给定n个矩阵 ， 其中 与 是可乘的， 考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序这种计算次序可以用加括号的方式来确定n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积85 矩阵连乘问题矩阵连乘问题 给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。 如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序 算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：86 矩阵连乘问题矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为A[i:j] ，这里i≤j 考察计算A[i:j]的最优计算次序设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征88 建立递归关系建立递归关系n设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] n当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,nn当i 循环体内的计算量为O(1)，而3重循环的总次数为O(n3)因此算法的计算时间上界为O(n3)算法所占用的空间显然为O(n2)91 动态规划算法的基本要素动态规划算法的基本要素一、最优子结构一、最优子结构•矩阵连乘计算次序问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质最优子结构性质•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾 •利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解最优子结构是问题能用动态规划算法求解的前提注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）92 二、重叠子问题二、重叠子问题•递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次这种性质称为子问题的重叠性质子问题的重叠性质•动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果 •通常不同的子问题个数随问题的大小呈多项式增长。 因此用动态规划算法只需要多项式时间，从而获得较高的解题效率 93 三、备忘录方法三、备忘录方法•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解m0private static int lookupChain(int i, int j) { if (m[i][j] > 0) return m[i][j]; if (i == j) return 0; int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j]; if (t < u) { u = t; s[i][j] = k;} } m[i][j] = u; return u; }94 最长公共子序列最长公共子序列•若给定序列X={x1,x2,…,xm}，则另一序列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=yn，且zk-1是xm-1和yn-1的最长公共子序列2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列因此，最长公共子序列问题具有最优子结最优子结构性质构性质 96 子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系用c[i][j]记录序列和的最长公共子序列的长度其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列故此时C[i][j]=0其他情况下，由最优子结构性质可建立递归关系如下：97 计算最优值计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: c[i][0]=0; c[0][i]=0;4: for (int i = 1; i <= m; i++)5: for (int j = 1; j <= n; j++) 6: if (x[i]==y[j]) 7: c[i][j]=c[i-1][j-1]+1;8: b[i][j]=1;9: else if (c[i-1][j]>=c[i][j-1]) 10: c[i][j]=c[i-1][j];11: b[i][j]=2;12: else 13: c[i][j]=c[i][j-1];14: b[i][j]=3;构造最长公共子序列构造最长公共子序列Algorithm lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ lcs(i-1,j-1,x,b); System.out.print(x[i]); } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); }98 算法的改进算法的改进•在算法lcsLength和lcs中，可进一步将数组b省去。 事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的•如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少事实上，在计算c[i][j]时，只用到数组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}•多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T•给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 100 三角剖分的结构及其相关问题三角剖分的结构及其相关问题•一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示•凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示 •矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi三角剖分中的一条弦vivj，i 为方便起见，设退化的多边形{vi-1,vi}具有权值0据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]•t[i][j]的值可以利用最优子结构性质递归地计算当j-i≥1时，凸子多边形至少有3个顶点由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置由此，t[i][j]可递归地定义为：103 多边形游戏多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”所有边依次用整数从1到n编号游戏第1步，将一条边删除随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点最后，所有边都被删除，游戏结束游戏的得分就是所剩顶点上的整数值问题:对于给定的多边形，计算最高得分。 104 最优子结构性质最优子结构性质•在所给多边形中，从顶点i(1≤i≤n)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为v[i]，op[i+1]，…，v[i+j-1]•如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1)，则可在op[i+s]处将链分割为2个子链p(i，s)和p(i+s，j-s)•设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值依此定义有a≤m1≤b，c≤m2≤d(1)当op[i+s]='+'时，显然有a+c≤m≤b+d(2)当op[i+s]='*'时，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd} •换句话说，主链的最大值和最小值可由子链的最大值和最小值得到 105 图像压缩图像压缩图像的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。 设 则第i个象素段Si为设 ，则hib[i]8因此需要用3位表示b[i],如果限制1l[i]255，则需要用8位表示l[i]因此，第i个象素段所需的存储空间为l[i]*b[i]+11位按此格式存储象素序列{p1,p2,…,pn}，需要 位的存储空间 图像压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段，使得依此分段所需的存储空间最少每个分段的长度不超过256位106 图像压缩图像压缩设l[i]，b[i]，是{p1,p2,…,pn}的最优分段显而易见，l[1]，b[1]是{p1,…,pl[1]}的最优分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最优分段即图像压缩问题满足最优子结构性质设s[i]，1≤i≤n，是象素序列{p1,…,pn}的最优分段所需的存储位数由最优子结构性质易知：其中算法复杂度分析：算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算因此整个算法所需的计算时间为O(n)。 107 电路布线电路布线在一块电路板的上、下2端分别有n个接线柱根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示其中π(i)是{1,2,…,n}的一个排列导线(i,π(i))称为该电路板上的第i条连线对于任何1≤i 在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集 2.3 若 ，则对任意(t,π(t)) ∈MNS(i,j)有 t •设全部作业的集合为N={1，2，…，n}SN是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的定义知T’T(S,b(1))若T’>T(S,b(1))，设’是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度则(1)， ’(2)，…， ’(n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)) 设是作业集S在机器M2的等待时间为t时的任一最优调度若(1)=i, (2)=j则由动态规划递归式可得:T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)其中，如果作业i和j满足min{bi,aj}≥min{bj,ai}，则称作业i和j满足JohnsonJohnson不等式不等式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法则当且仅当对任意i 算法复杂度分析：算法复杂度分析：算法的主要计算时间花在对作业集的排序因此，在最坏情况下算法所需的计算时间为O(nlogn)所需的空间为O(n)114 0-1背包问题背包问题给定n种物品和一背包物品i的重量是wi，其价值为vi，背包的容量为C问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题115 0-1背包问题背包问题设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下算法复杂度分析：算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间当背包容量c很大时，算法需要的计算时间较多例如，当c>2n时，算法需要Ω(n2n)计算时间 116 算法改进算法改进由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数跳跃点是这一类函数的描述特征在一般情况下，函数m(i,j)由其全部跳跃点惟一确定如图所示对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。 表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+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)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)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中易知，(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]因此，容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]} •另一方面，设(a，b)和(c，d)是p[i+1]q[i+1]中的2个跳跃点，则当ca且d 除受控跳跃点外，p[i+1]q[i+1]中的其他跳跃点均为p[i]中的跳跃点•由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]119 典型典型例子例子（（二）二）n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}初始时p[6]={(0,0)}，(w5,v5)=(4,6)因此，q[6]=p[6](w5,v5)={(4,6)}p[5]={(0,0),(4,6)}q[5]=p[5](w4,v4)={(5,4),(9,10)}从跳跃点集p[5]与q[5]的并集p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4](6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3](2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2](2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。 120 算法复杂度分析算法复杂度分析上述算法的主要计算量在于计算跳跃点集p[i](1≤i≤n)由于q[i+1]=p[i+1](wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值因此，p[i]中跳跃点个数不超过2n-i+1由此可见，算法计算跳跃点集p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})121 最优二叉搜索树最优二叉搜索树•什么是二叉搜索树？（1）若它的左子树不空，则左子树上所有 节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有 节点的值均大于它的根节点的值；（3 它的左、右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和 是等数量级的122 二叉查找树的期望耗费二叉查找树的期望耗费•查找成功与不成功的概率•二查找树的期望耗费•有 个节点的二叉树的个数为：•穷举搜索法的时间复杂度为指数级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章章 贪心算法贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择当然，希望贪心算法得到的最终结果也是整体最优的虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解如单源最短路经问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似127 第第4章章 贪心算法贪心算法本章主要知识点：•4.1 活动安排问题•4.2 贪心算法的基本要素•4.3 最优装载•4.4 哈夫曼编码•4.5 单源最短路径•4.6 最小生成树•4.7 多机调度问题•4.8 贪心算法的理论基础128 4.1 4.1 活动安排问题活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。 该问题要求高效地安排一系列争用某一公共资源的活动贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源129 4.1 4.1 活动安排问题活动安排问题 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si 直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间也就是说，该算法的贪心选择的意义是使剩余的可安排时使剩余的可安排时间段极大化间段极大化，以便安排尽可能多的相容活动 算法greedySelectorgreedySelector的效率极高当输入的活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源如果所给出的活动未按非减序排列，可以用O(nlognO(nlogn) )的时间重排 132 4.1 4.1 活动安排问题活动安排问题 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314133 4.1 4.1 活动安排问题活动安排问题 算法算法greedySelectorgreedySelector 的的计算过程计算过程如左图所示图中每行相应于算法的一次迭代阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动134 4.1 4.1 活动安排问题活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解整体最优解但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大这个结论可以用数学归纳法证明135 4.2 4.2 贪心算法的基本要素贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质贪心选择性质和最最优子结构性质优子结构性质 136 4.2 4.2 贪心算法的基本要素贪心算法的基本要素1.1.贪心选择性质贪心选择性质 所谓贪心选择性质贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别 动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解137 4.2 4.2 贪心算法的基本要素贪心算法的基本要素2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质最优子结构性质问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征 138 4.2 4.2 贪心算法的基本要素贪心算法的基本要素3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点但是，对于具有最优子结构最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题组合优化问题，并以此说明贪心算法与动态规划算法的主要差别139 4.2 4.2 贪心算法的基本要素贪心算法的基本要素•0-10-1背包问题：背包问题： 给定n种物品和一个背包物品i的重量是Wi，其价值为Vi，背包的容量为C应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。 不能将物品装入背包或不装入背包不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i140 4.2 4.2 贪心算法的基本要素贪心算法的基本要素•背包问题：背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背包，1≤i≤n 这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解 141 4.2 4.2 贪心算法的基本要素贪心算法的基本要素用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包依此策略一直地进行下去，直到背包装满为止 具体算法可描述如下页： 142 4.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++) d[i] = new Element(w[i],v[i],i);• MergeSort.mergeSort(d);• int i;• float opt=0;• for (i=0;i 因此，算法的计序因此，算法的计算时间上界为算时间上界为O O（（nlognnlogn）当然，）当然，为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质143 4.2 4.2 贪心算法的基本要素贪心算法的基本要素 对于0-10-1背包问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择由此就导出许多互相重叠的子问题这正是该问题可用动态规划动态规划算法算法求解的另一重要特征 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题 144 4.3 4.3 最优装载最优装载 有一批集装箱要装上一艘载重量为c的轮船其中集装箱i的重量为Wi最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船1.1.算法描述算法描述最优装载问题可用贪心算法求解采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解具体算法描述如下页。 145 4.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++)• d[i] = new Element(w[i],i);• MergeSort.mergeSort(d);• float opt=0;• for (int i = 0; i < n; i++) x[i] = 0;• for (int i = 0; i < n && d[i].w <= c; i++) {• x[d[i].i] = 1;• opt+=d[i].w;• c -= d[i].w;• }• return opt;• }其中其中ElementElement类说明为类说明为参参见本书见本书P115P115146 4.3 4.3 最优装载最优装载2.2.贪心选择性质贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3.3.最优子结构性质最优子结构性质最优装载问题具有最优子结构性质由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loadingloading的正确性算法loadingloading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlognO(nlogn) ) 147 4.4 4.4 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法其压缩率通常在20%～90%之间哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长1.1.前缀码前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀这种编码称为前缀码前缀码148 4.4 4.4 哈夫曼编码哈夫曼编码 编码的前缀性质可以使译码方法非常简单 表示最优前缀码最优前缀码的二叉树总是一棵完全二叉树完全二叉树，即树中任一结点都有2个儿子结点平均码长平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码最优前缀码。 149 4.4 4.4 哈夫曼编码哈夫曼编码2.2.构造哈夫曼编码构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T 150 4.4 4.4 哈夫曼编码哈夫曼编码 在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)以以f f为键值的优先队列为键值的优先队列Q Q用在贪心选择贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T算法huffmanTree用最小堆实现优先队列Q初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间因此，关于n个字符的哈夫曼算法的计算时间计算时间为O(nlogn) 151 4.4 4.4 哈夫曼编码哈夫曼编码3.3.哈夫曼算法的正确性哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。 1)贪心选择性质(2)最优子结构性质152 4.5 4.5 单源最短路径单源最短路径给定带权有向图G =(V,E)，其中每条边的权是非负实数另外，还给定V中的一个顶点，称为源源现在要计算从源到所有其他各顶点的最短路长度最短路长度这里路的长度是指路上各边权之和这个问题通常称为单源单源最短路径问题最短路径问题1.1.算法基本思想算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法153 4.5 4.5 单源最短路径单源最短路径其基本思想基本思想是，设置顶点集合S并不断地作贪心选贪心选择择来扩充这个集合一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知初始时，S中仅含有源设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度154 4.5 4.5 单源最短路径单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。 155 4.5 4.5 单源最短路径单源最短路径迭代迭代S Su udist[2dist[2] ]dist[3dist[3] ]dist[4dist[4] ]dist[5dist[5] ]初始初始{1}-10maxint301001 1{1,2}21060301002 2{1,2,4}4105030903 3{1,2,4,3}3105030604 4{1,2,4,3,5}510503060Dijkstra算法的迭代过程： 156 4.5 4.5 单源最短路径单源最短路径2.2.算法的正确性和计算复杂性算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间这个循环需要执行n-1次，所以完成循环需要 时间算法的其余部分所需要时间不超过 157 4.6 4.6 最小生成树最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络E中每条边(v,w)的权为c[v][w]如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树生成树上各边权的总和称为该生成树的耗费耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树网络的最小生成树在实际中有广泛应用例如例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案 158 4.6 4.6 最小生成树最小生成树1.1.最小生成树性质最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法本节介绍的构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边这个性质有时也称为MSTMST性质性质 159 4.6 4.6 最小生成树最小生成树2.Prim2.Prim算法算法 设G=(V,E)是连通带权图，V={1,2,…,n}构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪贪心选择心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。 这个过程一直进行到S=V时为止在这个过程中选取到的所有边恰好构成G的一棵最最小生成树小生成树 160 4.6 4.6 最小生成树最小生成树利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合边集合T T始终始终包含包含G G的某棵最小生成树中的某棵最小生成树中的边的边因此，在算法结束时，T中的所有边构成G的一棵最小生成树 例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下页图所示161 4.6 4.6 最小生成树最小生成树162 4.6 4.6 最小生成树最小生成树在上述Prim算法中，还应当考虑如何有效地找出满如何有效地找出满足条件足条件i i S,jS,j V-SV-S，且权，且权c[i][j]c[i][j]最小的边最小的边(i,j)(i,j)实现这个目的的较简单的办法是设置2个数组closest和lowcost在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，最后将j添加到S中，并对closest和lowcost作必要的修改用这个办法实现的Prim算法所需的计算时间计算时间为 163 4.6 4.6 最小生成树最小生成树3.Kruskal3.Kruskal算法算法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立的连通分支。 将所有的边按权从小到大排序然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边这个过程一直进行到只剩下一个连通分支时为止 164 4.6 4.6 最小生成树最小生成树例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示165 4.6 4.6 最小生成树最小生成树关于集合的一些基本运算集合的一些基本运算可用于实现Kruskal算法 按权的递增顺序查看等价于对优先队列优先队列执行removeMinremoveMin运算可以用堆堆实现这个优先队列 对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集并查集UnionFindUnionFind所支持的基本运算当图的边数为e时，Kruskal算法所需的计算时间计算时间是 当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。 166 4.7 4.7 多机调度问题多机调度问题多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成这个问题是NPNP完全问题完全问题，到目前为止还没有有效的解法对于这一类问题,用贪心选择策略贪心选择策略有时可以设计出较好的近似算法 约定，每个作业均可在任何一台机器上加工处理，但未约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理作业不能拆分成更小的子作业完工前不允许中断处理作业不能拆分成更小的子作业167 4.7 4.7 多机调度问题多机调度问题采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法按此策略，当 时，只要将机器i的[0, ti]时间区间分配给作业i即可，算法只需要O(1)时间当 时，首先将n个作业依其所需的处理时间从大到小排序然后依此顺序将作业分配给空闲的处理机算法所需的计算时间为O(nlogn)168 4.7 4.7 多机调度问题多机调度问题例如，例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。 各作业所需的处理时间分别为{2,14,4,16,6,5,3}按算法greedygreedy产生的作业调度如下图所示，所需的加工时间为17 169 4.8 4.8 贪心算法的理论基础贪心算法的理论基础借助于拟阵拟阵工具，可建立关于贪心算法的较一般的理论这个理论对确定何时使用贪心算法确定何时使用贪心算法可以得到问题的整体最优解十分有用1.1.拟阵拟阵拟阵M定义为满足下面3个条件的有序对(S,I)：(1)S是非空有限集2)I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集空集必为I的成员3)I满足交换性质，即若AI,BI且|A|<|B|，则存在某一元素xB-A，使得A∪{x}I170 4.8 4.8 贪心算法的理论基础贪心算法的理论基础例如，例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵拟阵的另一个例子是无向图G=(V,E)的图拟阵 给定拟阵M=(S,I)，对于I中的独立子集A I，若S有一元素x A，使得将x加入A后仍保持独立性，即A∪{x} I,则称x为A的可扩展元素可扩展元素。 当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集极大独立子集171 4.8 4.8 贪心算法的理论基础贪心算法的理论基础下面的关于极大独立子集极大独立子集的性质是很有用的定理定理4.14.1：：拟阵拟阵M M中所有极大独立子集大小相同中所有极大独立子集大小相同这个定理可以用反证法证明若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x S，有W(x)>0，则称拟阵M为带权拟阵带权拟阵依此权函数，S的任一子集A的权定义为 2.2.关于带权拟阵的贪心算法关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题最大权独立子集问题 172 4.8 4.8 贪心算法的理论基础贪心算法的理论基础给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大这种使W(A)最大的独立子集A称为拟阵M的最优子集最优子集由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集最优子集也一定是极大独立子集例如，例如，在最小生成树问题可以表示为确定带权拟阵 的最优子集问题求带权拟阵的最优子集A的算法可用于解最小生成树问题。 下面给出求带权拟阵最优子集带权拟阵最优子集的贪心算法该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A173 4.8 4.8 贪心算法的理论基础贪心算法的理论基础•Set greedygreedy (M,W)•{A=;• 将S中元素依权值W（大者优先）组成优先队列；• while (S!=) {• S.removeMax(x);• if (A∪{x}I) A=A∪{x};• }• return A•}174 4.8 4.8 贪心算法的理论基础贪心算法的理论基础算法greedygreedy的计算时间复杂性为 引理引理4.24.2( (拟阵的贪心选择性质拟阵的贪心选择性质) )设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列又设x S是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得x A算法greedygreedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素此时可能已经舍弃了S中部分元素可以证明这些被舍弃的元素不可能用于构造最优子集。 175 4.8 4.8 贪心算法的理论基础贪心算法的理论基础引理引理4.34.3：：设M=(S,I)是拟阵若S中元素x不是空集的可扩展元素，则x也不可能是S中任一独立子集A的可扩展元素引理引理4.4(4.4(拟阵的最优子结构性质拟阵的最优子结构性质) )设x是求带权拟阵M＝(S，I)的最优子集的贪心算法greedygreedy所选择的S中的第一个元素那么，原问题可简化为求带权拟阵M’=(S’,I’)的最优子集最优子集问题，其中：S’={y|y S且{x,y} I}I’={B|B S-{x}且B∪{x} I}M’的权函数是M的权函数在S’上的限制(称M’为M关于元素x的收缩收缩)176 4.8 4.8 贪心算法的理论基础贪心算法的理论基础定理定理4.5(4.5(带权拟阵贪心算法的正确性带权拟阵贪心算法的正确性) )设M＝(S,I)是具有权函数W的带权拟阵，算法greedy返回M的最优子集3.3.任务时间表问题任务时间表问题给定一个单位时间任务单位时间任务的有限集S关于S的一个时间表时间表用于描述S中单位时间任务的执行次序时间表中第1个任务从时间0开始执行直至时间1结束，第2个任务从时间1开始执行至时间2结束，…，第n个任务从时间n-1开始执行直至时间n结束。 177 4.8 4.8 贪心算法的理论基础贪心算法的理论基础具有截止时间截止时间和误时惩罚误时惩罚的单位时间任务时间表问题可描述如下1) n个单位时间任务的集合S={1,2,…,n}；(2) 任务i的截止时间 ,1≤i≤n,1≤ ≤n，即要求任务i在时间 之前结束；(3) 任务i的误时惩罚 ,1≤i≤n,即任务i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚任务时间表问题任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小178 4.8 4.8 贪心算法的理论基础贪心算法的理论基础这个问题看上去很复杂，然而借助于拟阵拟阵，可以用带权拟阵的贪心算法带权拟阵的贪心算法有效求解对于一个给定的S的时间表，在截止时间之前完成的任务称为及时任务及时任务，在截止时间之后完成的任务称为误时任务误时任务S的任一时间表可以调整成及时优先形式及时优先形式，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质类似地，还可将S的任一时间表调整成为规范形式规范形式，其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列179 4.8 4.8 贪心算法的理论基础贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。 任务时间表问题等价于等价于确定最优时间表中及时任及时任务子集务子集A A的问题一旦确定了及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即S-A中各任务，由此产生S的一个规范的最优时间表对时间t=1,2,…,n，设设 (A)是任务子集A中所有截止时间是t或更早的任务数考察任务子集A的独立性180 4.8 4.8 贪心算法的理论基础贪心算法的理论基础引理引理4.64.6：：对于S的任一任务子集A，下面的各命题是等价的1) 任务子集A是独立子集2) 对于t=1,2,…,n， (A)≤t3) 若A中任务依其截止时间非减序排列，则A中所有任务都是及时的任务时间表问题任务时间表问题要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大下面的定理定理表明可用带权拟阵的贪心算法解任务时间表问题181 4.8 4.8 贪心算法的理论基础贪心算法的理论基础定理定理4.74.7：：设S是带有截止时间的单位时间任务集，I是S的所有独立任务子集构成的集合则有序对(S,I)是拟阵由定理定理4.54.5可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立任务子集A，以A作为最优时间表中的及时任务子集，容易构造最优时间表。 任务时间表问题的贪心算法的计算时间复杂性计算时间复杂性是 其中f(n)是用于检测任务子集A的独立性所需的时间用引理4.6中性质(2)容易设计一个 时间算法来检测任务子集的独立性因此，整个算法的计算时间计算时间为 具体算法greedyJobgreedyJob可描述如P130182 4.8 4.8 贪心算法的理论基础贪心算法的理论基础用抽象数据类型并查集UnionFindUnionFind可对上述算法作进一步改进如果不计预处理的时间，改进后的算法fasterJobfasterJob所需的计算时间计算时间为 183 第第5章章 回溯法回溯法184 回溯法回溯法•有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法•回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法这种方法适用于解一些组合数相当大的问题•回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 185 问题的解空间问题的解空间•问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式•显约束：对分量xi的取值限定•隐约束：为满足问题的解而对不同分量之间施加的约束•解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）n=3时的0-1背包问题用完全二叉树表示的解空间186 生成问题状态的基本方法生成问题状态的基本方法•扩展结点:一个正在产生儿子的结点称为扩展结点•活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点•死结点:一个所有儿子已经产生的结点称做死结点•深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）•宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点•回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。 具有限界函数的深度优先生成法称为回溯法187 回溯法的基本思想回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间在任何时刻，算法只保存从根结点到当前扩展结点的路径如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间188 递归回溯递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法void backtrack (int t){ if (t>n) output(x); else for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); }}189 迭代回溯迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。 void iterativeBacktrack (){ int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } else t--; }}190 子集树与排列树子集树与排列树遍历子集树需O(2n)计算时间 遍历排列树需要O(n!)计算时间 void backtrack (int t){ if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); }}void backtrack (int t){ if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); }} 191 装载问题装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。 如果有，找出一种装载方案容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近由此可知，装载问题等价于以下特殊的0-1背包问题用回溯法设计解装载问题的O(2n)计算时间算法在某些情况下该算法优于动态规划算法192 装载问题装载问题•解空间：子集树•可行性约束函数(选择当前元素)：•上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r当前最优载重量bestwprivate static void backtrack (int i) {// 搜索第i层结点 if (i > n) // 到达叶结点 更新最优解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }193 批处理作业调度批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。 每个作业必须先由机器1处理，然后由机器2处理作业Ji需要机器j的处理时间为tji对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和批处理作业调度问题要求对于给定的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，其完成时间和为18194 批处理作业调度批处理作业调度•解空间：排列树private static void backtrack(int i) { if (i > n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; } else for (int j = i; j <= n; j++) { f1+=m[x[j]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2]; f+=f2[i]; if (f < bestf) { MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j); } f1-=m[x[j]][1]; f-=f2[i]; } }public class FlowShop static int n, // 作业数 f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间195 符号三角形问题符号三角形问题+ + - + - + ++ - - - - +- + + + - - + + - - + - - - +下图是由14个“+”和14个“-”组成的符号三角形。 2个同号下面都是“+”，2个异号下面都是“-”在一般情况下，符号三角形的第一行有n个符号符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同196 符号三角形问题符号三角形问题•解向量：用n元组x[1:n]表示符号三角形的第一行 •可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 •无解的判断：n*(n+1)/2为奇数 private static void backtrack (int t) { if ((count>half)||(t*(t-1)/2-count>half)) return; if (t>n) sum++; else for (int i=0;i<2;i++) { p[1][t]=i; count+=i; for (int j=2;j<=t;j++) { p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1]; } backtrack(t+1); for (int j=2;j<=t;j++) count-=p[j][t-j+1]; count-=i; } }+ + - + - + ++ - - - - +- + + + - - + + - - + - - - +复杂度分析复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。 197 n后问题后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上1 2 3 4 5 6 7 812345678198 •解向量：(x1, x2, … , xn)•显约束：xi=1,2, … ,n•隐约束： 1)不同列：xi xj 2)不处于同一正、反对角线：|i-j| |xi-xj|n后问题后问题 private static boolean place (int k) { for (int j=1;j 如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中G的最大团是指G中所含顶点数最多的团如果UV且对任意u，vU有(u，v)E，则称U是G的空子图G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中G的最大独立集是G中所含顶点数最多的独立集对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)E1当且仅当(u，v)EU U是是G G的最大团当且仅当的最大团当且仅当U U是是G G的最大独立集的最大独立集1245312453201 最大最大团团问题问题•解空间：子集树•可行性约束函数：顶点i到已选入的顶点集中每一个顶点都有边相连 •上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团 private static void backtrack(int i) { if (i > n) {// 到达叶结点 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return; } // 检查顶点 i 与当前团的连接 boolean ok = true; for (int j = 1; j < i; j++) if (x[j] == 1 && !a[i][j]) {// i与j不相连 ok = false; break; } if (ok) {// 进入左子树 x[i] = 1; cn++; backtrack(i + 1); cn--; } if (cn + n - i > bestn) {// 进入右子树 x[i] = 0; backtrack(i + 1); } }}复杂度分析复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。 12453202 进一步改进算法的建议进一步改进算法的建议•选择合适的搜索顺序，可以使得上界函数更有效的发挥作用例如在搜索之前可以将顶点按度从小到大排序这在某种意义上相当于给回溯法加入了启发性•定义Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,...,S1的解从而得到一个更精确的上界函数，若cn+Si<=max则剪枝同时注意到：从Si+1到Si，如果找到一个更大的团，那么vi必然属于找到的团，此时有Si=Si+1+1，否则Si=Si+1因此只要max的值被更新过，就可以确定已经找到最大值，不必再往下搜索了203 图的图的m着色问题着色问题给定无向连通图G和m种不同的颜色用这些颜色为图G的各顶点着色，每个顶点着一种颜色是否有一种着色法使G中每条边的2个顶点着不同颜色这个问题是图的m可着色判定问题若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数求一个图的色数m的问题称为图的m可着色优化问题204 •解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i] •可行性约束函数：顶点i与已着色的相邻顶点颜色不重复图的图的m着色问题着色问题private static void backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=m;i++) { x[t]=i; if (ok(t)) backtrack(t+1); } } private static boolean ok(int k) {// 检查颜色可用性 for (int j=1;j<=n;j++) if (a[k][j] && (x[j]==x[k])) return false; return true; }}复杂度分析复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。 因此，回溯法总的时间耗费是思考：图的思考：图的m着色问题与图的最着色问题与图的最大团问题有何关系，你能否利用大团问题有何关系，你能否利用这个关系改进最大团问题的上界这个关系改进最大团问题的上界？？205 旅行售货员问题旅行售货员问题•解空间：排列树private static void backtrack(int i) { if (i == n) { if (a[x[n - 1]][x[n]] < Float.MAX_VALUE && a[x[n]][1] < Float.MAX_VALUE && (bestc == Float.MAX_VALUE || cc+a[x[n - 1]][x[n]]+a[x[n]][1] 206 圆排列问题圆排列问题给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示其最小长度为207 圆圆排列问题排列问题private static float center(int t) {// 计算当前所选择圆的圆心横坐标 float temp=0; for (int j=1;j 例如，象1,2,…,n-1,n和n,n-1, …,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量另一方面，如果所给的n个圆中有k个圆有相同的半径，则这k个圆产生的k!个完全相同的圆排列，只计算一个就够了 208 连续邮资问题连续邮资问题假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70209 连续邮资问题连续邮资问题•解向量：用n元组x[1:n]表示n种不同的邮票面值，并约定它们从小到大排列x[1]=1是惟一的选择•可行性约束函数：已选定x[1:i-1]，最大连续邮资区间是[1:r]，接下来x[i]的可取值范围是[x[i-1]+1:r+1]如何确定r的值？计算X[1:i]的最大连续邮资区间在本算法中被频繁使用到，因此势必要找到一个高效的方法考虑到直接递归的求解复杂度太高，我们不妨尝试计算用不超过m张面值为x[1:i]的邮票贴出邮资k所需的最少邮票数y[k]。 通过y[k]可以很快推出r的值事实上，y[k]可以通过递推在O(n)时间内解决：for (int j=0; j<= x[i-2]*(m-1);j++) if (y[j] 从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力图(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 0－1背包问题• 6.6 最大团问题• 6.7 旅行售货员问题• 6.8 电路板排列问题• 6.9 批处理作业调度214 6.1 分支限界法的基本思想分支限界法的基本思想1. 分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 215 6.1 分支限界法的基本思想分支限界法的基本思想2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树 在分支限界法中，每一个活结点只有一次机会成为扩展结点活结点一旦成为扩展结点，就一次性产生其所有儿子结点在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程这个过程一直持续到找到所需的解或活结点表为空时为止 216 6.1 分支限界法的基本思想分支限界法的基本思想3. 常见的两种分支限界法（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点217 6.2 单源最短路径问题单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权要求图G的从源顶点s到目标顶点t之间的最短路径 218 6.2 单源最短路径问题单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。 其中，每一个结点旁边的数字表示该结点所对应的当前路长219 6.2 单源最短路径问题单源最短路径问题2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表其优先级是结点所对应的当前路长 算法从图G的源顶点s和空优先队列开始结点s被扩展后，它的儿子结点被依次插入堆中此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中这个结点的扩展过程一直继续到活结点优先队列为空时为止220 6.2 单源最短路径问题单源最短路径问题3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树 在算法中，利用结点间的控制关系进行剪枝从源顶点s出发，2条不同路径到达图G的同一顶点由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去 221 6.2 单源最短路径问题单源最短路径问题 while (true) { // 搜索问题的解空间 for (int j=1;j<=n;j++) if(a[enode.i][j] < Float.MAX_VALUE && enode.length+a[enode.i][j] < dist[j]) { // 顶点i到顶点j可达，且满足控制约束 dist[j]=enode.length+a[enode.i][j]; p[j]=enode.i; HeapNode node = new HeapNode(j,dist[j]); heap.put(node); // 加入活结点优先队列 } if (heap.isEmpty()) break; else enode = (HeapNode) heap.removeMin(); }顶点顶点I I和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 222 6.3 装载问题装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。 如果有，找出一种装载方案 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船 223 6.3 装载问题装载问题2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点如果是则将其加入到活结点队列中然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)2个儿子结点都产生后，当前扩展结点被舍弃 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空当取出的元素是-1时，再判断当前队列是否为空如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点224 6.3 装载问题装载问题2. 队列式分支限界法while (true) { if (ew + w[i] <= c) enQueue(ew + w[i], i); // 检查左儿子结点 enQueue(ew, 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++; // 进入下一层 } }225 6.3 装载问题装载问题3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。 设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值226 6.3 装载问题装载问题3. 算法的改进// 检查左儿子结点 int wt = ew + w[i]; if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) queue.put(new Integer(wt)); }提前更新提前更新bestw bestw // 检查右儿子结点 if (ew + r > bestw && i < n) // 可能含最优解 queue.put(new Integer(ew)); ew=((Integer)queue.remove()) .intValue(); // 取下一扩展结点 右儿子剪枝右儿子剪枝 227 6.3 装载问题装载问题4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。 为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志 private static class QNode { QNode parent; // 父结点 boolean leftChild; // 左儿子标志 int weight; // 结点所相应的载重量228 6.3 装载问题装载问题找到最优值后，可以根据parent回溯到根节点，找到最优解// 构造当前最优解 for (int j = n; j > 0; j--) { bestx[j] = (e.leftChild) ? 1 : 0; e = e.parent; }229 6.3 装载问题装载问题5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和 优先队列中优先级最大的活结点成为下一个扩展结点以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。 子集树中叶结点所相应的载重量与其优先级相同 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解此时可终止算法 230 6.4 布线问题布线问题算法的思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1 接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止即加入剪枝的广度优先搜索231 6.4 布线问题布线问题Position [] offset = new Position [4];offset[0] = new Position(0, 1); // 右offset[1] = new Position(1, 0); // 下offset[2] = new Position(0, -1); // 左offset[3] = new Position(-1, 0); // 上 定义移动方向的定义移动方向的相对位移相对位移 for (int i = 0; i <= size + 1; i++) { grid[0][i] = grid[size + 1][i] = 1; // 顶部和底部 grid[i][0] = grid[i][size + 1] = 1; // 左翼和右翼 }设置边界的围墙设置边界的围墙232 6.4 布线问题布线问题for (int i = 0; i < numOfNbrs; i++){ nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 该方格未标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; q.put(new Position(nbr.row, nbr.col)); } }找到目标位置后，可以通过回溯方法找到这条最短路径。 233 6.5 0-1背包问题背包问题•算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和 算法首先检查当前扩展结点的左儿子结点的可行性如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列当扩展到叶节点时为问题的最优值234 6.5 0-1背包问题背包问题上界函数while (i <= n && w[i] <= cleft) // n表示物品总数，cleft为剩余空间 { cleft -= w[i]; //w[i]表示i所占空间 b += p[i]; //p[i]表示i的价值 i++; }if (i <= n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包return b; //b为上界函数235 6.5 0-1背包问题背包问题 while (i != n + 1) {// 非叶结点 double wt = cw + w[i]; if (wt <= c) {// 左儿子结点为可行结点 if (cp + p[i] > bestp) bestp = cp + p[i]; addLiveNode(up,cp + p[i],cw + w[i],i + 1, enode, true); } up = bound(i + 1); if (up >= bestp) //检查右儿子节点 addLiveNode(up,cp,cw,i + 1, enode, false); // 取下一个扩展节点（略）}分支限界搜索过分支限界搜索过程程236 6.6 最大团问题最大团问题1.问题描述 给定无向图G=(V，E)。 如果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的最大团 237 6.6 最大团问题最大团问题2. 上界函数 用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值 在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素 238 6.6 最大团问题最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0 算法在扩展内部结点时，首先考察其左儿子结点在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。 当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点 接 着 继 续 考 察 当 前 扩 展 结 点 的 右 儿 子 结 点 当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中239 6.6 最大团问题最大团问题 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点 对于子集树中的叶结点，有upperSize＝cliqueSize此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解 240 6.7 旅行售货员问题旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小 路线是一个带权图图中各边的费用（权）为正数图的一条周游路线是包括V中的每个顶点在内的一条回路。 周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线旅行售货员问题要在图G中找出费用最小的周游路线 241 6.7 旅行售货员问题旅行售货员问题2. 算法描述 算法开始时创建一个最小堆，用于表示活结点优先队列堆中每个结点的子树费用的下界lcost值是优先队列的优先级接着算法计算出图中每个顶点的最小费用出边并用minout记录如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束如果每个顶点都有出边，则根据计算出的minout作算法初始化 算法的while循环体完成对排列树内部结点的扩展对于当前扩展结点，算法分2种情况进行处理：242 6.7 旅行售货员问题旅行售货员问题 1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点 2、当s 对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost当lcost 计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解 当s 行比较246 6.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.now[j] = enode.now[j] + board [enode.x[i]][j];247 6.8 电路板排列问题电路板排列问题int ld = 0; // 新插入电路板的密度for (int j = 1; j <= m; j++)if (node.now[j] > 0 && total[j] != node.now[j]) ld++;node.cd = Math.max(ld, enode.cd);if (node.cd < bestd){// 可能产生更好的叶结点 node.s = enode.s + 1; for (int j = 1; j <= n; j++) node.x[j] = enode.x[j]; node.x[node.s] = enode.x[i]; node.x[i] = enode.x[node.s]; heap.put(node); } } } 算法描述计算出每一个儿子结点的计算出每一个儿子结点的密度与密度与bestdbestd进行比较大进行比较大于于bestdbestd时加入队列时加入队列248 6.9 批处理作业问题批处理作业问题1. 问题的描述 给定n个作业的集合J={J1,J2,…,Jn}。 每一个作业Ji都有2项任务要分别在2台机器上完成每一个作业必须先由机器1处理，然后再由机器2处理作业Ji需要机器j的处理时间为tji，i=1,2,…,n；j=1,2对于一个确定的作业调度，设是Fji是作业i在机器j上完成处理的时间则所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小249 6.9 批处理作业问题批处理作业问题2. 限界函数在结点E处相应子树中叶结点完成时间和的下界是：注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值同理如果选择Pk使t2pk依非减序排列，则S2取得极小值 这可以作为优先队列式分支限界法中的限界函数 250 6.9 批处理作业问题批处理作业问题3. 算法描述 算法的while循环完成对排列树内部结点的有序扩展在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展 首先考虑enode.s=n的情形，当前扩展结点enode是排列树中的叶结点enode.sf2是相应于该叶结点的完成时间和。 当enode.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx 当enode.s 在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数线性同余法是产生伪随机数的最常用的方法由线性同余法产生的随机序列a0,a1,…,an满足其中b0，c0，dmd称为该随机序列的种子如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能这是随机性理论研究的内容，已超出本书讨论的范围从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数255 数值概率算法数值概率算法 256 用随机投点法计算用随机投点法计算 值值设有一半径为r的圆及其外切四边形向该正方形随机地投掷n个点设落入圆内的点数为k由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 所以当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在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为假设向单位正方形内随机地投入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是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得 的可能性希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有这就是舍伍德算法设计的基本思想。 当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能260 舍伍德舍伍德(Sherwood)算法算法复习学过的Sherwood算法：（1）线性时间选择算法（2）快速排序算法有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果例如，对于确定性选择算法，可以用下面的洗牌算法shuffle将数组a中元素随机排列，然后用确定性选择算法求解这样做所收到的效果与舍伍德型算法的效果是一样的public static void shuffle(Comparable []a, int n) {// 随机洗牌算法 rnd = new Random(); for (int i=1;i •提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度这种增加了向前附加指针的有序链表称为跳跃表•应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算 262 跳跃表跳跃表在一般情况下，给定一个含有n个元素的有序链表，可以将它改造成一个完全跳跃表，使得每一个k级结点含有k+1个指针，分别跳过2k-1，2k-1-1，…，20-1个中间结点第i个k级结点安排在跳跃表的位置i2k处，i0这样就可以在时间O(logn)内完成集合成员的搜索运算在一个完全跳跃表中，最高级的结点是logn级结点完全跳跃表与完全二叉搜索树的情形非常类似它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，影响后继元素搜索的效率263 跳跃表跳跃表为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。 注意到在一个完全跳跃表中，50%的指针是0级指针；25%的指针是1级指针；…；(100/2k+1)%的指针是k级指针因此，在插入一个元素时，以概率1/2引入一个0级结点，以概率1/4引入一个1级结点，…，以概率1/2k+1引入一个k级结点另一方面，一个i级结点指向下一个同级或更高级的结点，它所跳过的结点数不再准确地维持在2i-1经过这样的修改，就可以在插入或删除一个元素时，通过对跳跃表的局部修改来维持其平衡性 264 跳跃表跳跃表注意到，在一个完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针为了维持跳跃表的平衡性，可以事先确定一个实数0 为了避免这种情况，用 作为新结点级别的上界其中n是当前跳跃表中结点个数当前跳跃表中任一结点的级别不超过 265 拉斯维加斯拉斯维加斯( Las Vegas )算法算法拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解public static void obstinate(Object x, Object y) {// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y boolean success= false; while (!success) success=lv(x,y); }设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得： 266 n后问题后问题对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的由此容易想到下面的拉斯维加斯算法。 在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大 stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.11267 整数因子分解整数因子分解设n>1是一个整数关于整数n的因子分解问题是找出n的如下形式的惟一分解式：其中，p1 268 Pollard算法算法在开始时选取0～n-1范围内的随机数，然后递归地由产生无穷序列对于i=2k，以及2k 由于n的最小素因子p ，故Pollard算法可在O(n1/4)时间内找到n的一个素因子269 蒙特卡罗蒙特卡罗(Monte Carlo)算法算法•在实际应用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确•设p是一个实数，且1/2 称上述算法MC(x)是偏y0的算法重复调用一个一致的，p正确偏y0蒙特卡罗算法k次，可得到一个O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏y0蒙特卡罗算法 271 主元素问题主元素问题设T[1:n]是一个含有n个元素的数组当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素 public static boolean majority(int[]t, int n) {// 判定主元素的蒙特卡罗算法 rnd = new Random(); int i=rnd.random(n)+1; int x=t[i]; // 随机选择数组元素 int k=0; for (int j=1;j<=n;j++) if (t[j]==x) k++; return (k>n/2); // k>n/2 时t含有主元素 }public static boolean majorityMC(int[]t, int n, double e) {// 重复é ù次调用算法majority int k= (int) Math.ceil(Math.log(1/e)/Math.log(2)); for (int i=1;i<=k;i++) if (majority(t,n)) return true; return false; }对于任何给定的>0，算法majorityMC重复调用log(1/) 次算法majority。 它是一个偏真蒙特卡罗算法，且其错误概率小于算法majorityMC所需的计算时间显然是O(nlog(1/ ))272 素数测试素数测试WilsonWilson定理定理定理定理：：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)费尔马小定理费尔马小定理费尔马小定理费尔马小定理：：如果p是一个素数，且0 通过多次重复调用错误概率不超过(1/4)k这是一个很保守的估计，实际使用的效果要好得多273 第第8 8章章NPNP完全性理论完全性理论274 8.1 计算模型计算模型•8.1.1 随机存取机RAM•8.1.2 随机存取存储程序机RASP•8.1.3 RAM模型的变形与简化•8.1.4 图灵机•8.1.5 图灵机模型与RAM模型的关系•8.1.6 问题变换与计算复杂性归约275 8.1.1 随机存取机随机存取机RAMRAM1. RAMRAM的结构的结构276 8.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程序当作一个语言接受器程序当作一个语言接受器。 将字符串S=a1a2…an放在输入带上在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an然后在第n+1个方格中放入0，作为输入串的结束标志符如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S 277 8.1.1 随机存取机随机存取机RAMRAM3. RAMRAM程序的耗费标准程序的耗费标准标准一：均匀耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量 标准二：对数耗费标准标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数因此若设l(i)是整数i所占的二进制位数，则 278 8.1.2 随机存取存储程序机随机存取存储程序机RASPRASP1. RASPRASP的结构的结构 RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的每条RASP指令占据2个连续的寄存器。 第一个寄存器存放操作码的编码，第二个寄存器存放地址RASP指令用整数进行编码2. RASPRASP程序程序的复杂性的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成其中k是一个常数因子空间复杂性的情况也是类似的 279 8.1.3 RAMRAM模型的变形与简化模型的变形与简化1. 实随机存取机实随机存取机 RRAMRRAM 在RRAM模型下，一个存储单元可以存放一个实数下列的各运算为基本运算且每个运算只耗费单位时间 (1)算术运算+，－，×，／2)2个实数间的比较(<，≤，=，≠，≥，>)3)间接寻址(整数地址)4)常见函数的计算，如三角函数，指数函数，对数函数等优点：能够方便处理实数；适合于用FORTRAN，PASCAL等高级语言写的算法 280 8.1.3 RAMRAM模型的变形与简化模型的变形与简化2. 直线式程序直线式程序对于许多问题，所设计的RAM程序中的转移指令仅用于重复一组指令，而且重复的次数与问题的输入规模n成比例。 在这种情况下，可以用重复地写出相同指令组的方法来消除程序中的循环由此，对每一个固定的n得到一个无循环的直线式程序 经过对RAM模型的简化，得到直线式程序的指令系统如下：x←y+zx←y-zx←y*zx←y/zx←i其中x，y和z是符号地址(或变量)，而i是常数每条指令耗费一个单位时间每条指令耗费一个单位时间281 8.1.3 RAMRAM模型的变形与简化模型的变形与简化3. 位式计算位式计算直线式程序计算模型显然是基于均匀耗费标准的在对数耗费标准下，使用另一个RAM的简化计算模型，称之为位式计算(Bitwise Computation)模型 除了下列2点外，该计算模型与直线式程序计算模型基本相同：(1)假设所有变量取值0或1，即为位变量2)所用的运算是逻辑运算而不是算术运算用∧代表与，∨代表或，代表异或，代表非 在位式计算模型下，每个逻辑运算指令耗费一个单位时间在位式计算模型下，每个逻辑运算指令耗费一个单位时间 282 8.1.3 RAMRAM模型的变形与简化模型的变形与简化4. 位向量运算位向量运算( (Bit Vector Operations)Bit Vector Operations) 若在直线式程序计算模型中，假设所有变量均为位向量，而且所用的运算均为位操作指令，则得到位向量运算计算模型。 例如，要表示一个有100个顶点的图中从顶点v到其余各顶点间有没有边相连，可以用100位的一个位向量表示若顶点v到顶点vj之间有边相连，则该位向量的第j位为1，否则为0 缺点：所需的机器字长要远大于其他模型 283 8.1.3 RAMRAM模型的变形与简化模型的变形与简化5. 判定树判定树 判定树是一棵二叉树它的每个内结点表示一个形如x∶y的比较指向该结点左儿子的边相应于x≤y，标号为≤指向该结点右儿子的边相应于x>y，标号为>每一次比较耗费一个单位时间下图是对a，b，c三个数进行排序的一棵判定树 在判定树模型下，在判定树模型下，算法的时间复杂性算法的时间复杂性可用判定树的高度可用判定树的高度衡量最大的比较衡量最大的比较次数是从根到叶的次数是从根到叶的最长路径的长度最长路径的长度 284 8.1.3 RAMRAM模型的变形与简化模型的变形与简化6. 代数计算树代数计算树ACTACT以x=(x1，x2，…，xn)为输入的一棵代数计算树T是一棵二叉树，且：(1)每个叶结点表示一个输出结果YES或NO2)每个单儿子内部结点(简单结点)v表示下列形式运算指令： op 或 op 或其中， 和 分别是结点v在树T中的祖先结点v1和v2处得到的结果值，或是x的分量；op∈{+，－，×，/}；c是一个常数。 3)每个有2个儿子的内部结点(分支结点)v，表示下列形式的测试指令： >0或 ≥0或 =0其中， 是结点v在树T中的祖先结点v1处得到的结果值，或是x的分量 285 8.1.3 RAMRAM模型的变形与简化模型的变形与简化7. 代数判定树代数判定树ADT(Algebraic Decision Tree)ADT(Algebraic Decision Tree)在代数计算树T中，若将所有的简单结点都压缩到其最近的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点处同时完成，则计算结果可看作是输入x的一个代数函数fv(x)由此引出另一个称为代数判定树的计算模型 代数判定树T是一棵二叉树，且(1)每个叶结点表示输出结果YES或NO2)每个内部结点v表示一个形如fv(x1，x2，…，xn)∶0的比较其中，x=( x1，x2，…，xn)是输入，fv是一个代数函数 286 8.1.4 图灵机图灵机1. 多带图灵机多带图灵机287 8.1.4 图灵机图灵机1. 多带图灵机多带图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态 (2)清除当前读写头下的方格中原有带符号并写上新的带符号 (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S) k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中: (1)Q是有限个状态的集合2)T是有限个带符号的集合3)I是输入符号的集合，IT4)b是惟一的空白符，b∈T-I5)q0是初始状态6)qf是终止(或接受)状态 (7)δ是移动函数它是从QTk的某一子集映射到Q (T{L，R，S})k的函数 288 8.1.4 图灵机图灵机1. 多带图灵机多带图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和如果某个读写头无限地向右移动而不停机，S(n)也无定义 与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置 289 8.1.5 图灵机模型与图灵机模型与RAMRAM模型的关系模型的关系图灵机模型与RAM模型的关系是指同一问题在这2种不同计算模型下的复杂性之间的关系。 定理定理8-3 8-3 对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为 ，那么，算法A在RAM模型下的时间复杂性为 定理定理8-4 8-4 对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为 ，那么，算法A在k带图灵机模型TM下的时间复杂性为 290 8.1.6 问题变换与计算复杂性归约问题变换与计算复杂性归约具体地说，假设有2个问题A和B，将问题问题A A变换为问题变换为问题B B是指：(1)将问题A的输入变换为问题B的适当输入2)解出问题B3)把问题B的输出变换为问题A的正确解若用O(τ(n))时间能完成上述变换的第(1)步和第(3)步，则称问题A是τ(n)时间可变换到问题B，且简记为A∝A∝τ(n)τ(n)B B其中的n通常为问题A的规模(大小)当τ(n)为n的多项式时，称问题A可在多项式时间内变换为问题B特别地，当τ(n)为n的线性函数时，称问题A可线性地变换为问题B 通过问题变换的技巧，可以将2个不同问题的计算复杂性联系在一起。 这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约291 8.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)可变换到问题B，即A∝τ(n)B，则T(n)+O(τ(n))是问题A的一个计算时间上界 问题的变换与问题的计算复杂性归约的关系：在命题1和命题2中，当τ(n)=o(T(n))时，问题A的下界归约为问题B的下界，问题B的上界归约为问题A的上界 292 8.1.6 问题变换与计算复杂性归约问题变换与计算复杂性归约通过问题变换获得问题的计算时间下界的例子：(1)判别函数问题：给定n个实数 ，计算其判别函数 元素惟一性问题可以在O(1)时间内变换为判别函数问题任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为0，即可得到元素惟一性问题的解。 由命题1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时间下界2)最接近点对问题：给定平面上n个点，找出这n个点中距离最近的2个点在元素惟一性问题中，将每一个实数 ，1≤i≤n，变换为平面上的点( ，0)，1≤i≤n，则元素惟一性问题可以性时间内变换为最接近点对问题 293 8.2 P类与类与NP类问题类问题•8.2.1 非确定性图灵机•8.2.2 P类与NP类语言•8.2.3 多项式时间验证294 8.2.1 非确定性图灵机非确定性图灵机 非确定性图灵机非确定性图灵机（（ NDTMNDTM ））：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，δ，b，q0，qf)与确定性图灵机不同的是非确定性图灵机允许移动函数δδ具有不确定性具有不确定性，即对于QTk中的每一个值(q;x1,x2,…,xk)，当它属于δ的定义域时，Q(T{L，R，S})k中有惟一的一个子集子集δ(q;x1,x2,…,xk)与之对应可以在δ(q;x1,x2,…,xk)中随意选定一个值作为它的函数值 在图灵机计算模型中，移动函数δδ是单值的是单值的，即对于QTk中的每一个值，当它属于δ的定义域时，Q(T{L，R，S})k中只有惟一的值与之对应，称这种图灵机为确定性图灵机确定性图灵机，简记为DTMDTM(Deterministic Turing Machine)。 295 8.2.2 P P类与类与NPNP类语言类语言 P类和NP类语言的定义： P={L|L是一个能在多项式时间内多项式时间内被一台DTMDTM所接受的语言} NP={L|L是一个能在多项式时间多项式时间内被一台NDTMNDTM所接受的语言}由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受故P P NP NP 296 8.2.2 P P类与类与NPNP类语言类语言 NPNP类语言举例类语言举例————无向图的团问题无向图的团问题 该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k要求判定图G是否包含一个k顶点的完全子完全子图图( (团团) )，即判定是否存在V’V，|V’|=k，且对于所有的u，v∈V’，有(u，v)∈E 若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为 的二进位串表示因此，团问题可表示为语言： CLIQUE={w#v|w，v∈{0，1}*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。 } 297 8.2.2 P P类与类与NPNP类语言类语言 接受该语言CLIQUE的非确定性算法非确定性算法：用非确定性选择指令选出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否是团问题的一个解算法分为3个阶段： 算法的第一阶段将输入串w#v分解，并计算出n= ，以及用v表示的整数k若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入显而易见，第一阶段可 在时间内完成 在算法的第二阶段中，非确定性地选择V的一个k元子集V’V 算法的第三阶段是确定性地检查V’的团性质若V’是一个团则接受输入，否则拒绝输入这显然可以在 时间内完成因此，整个算法的时间复杂性为 非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUE∈NP 298 8.2.3 多项式时间验证多项式时间验证 VP={L|L∈∑*，∑为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X∈∑*，X∈L当且仅当存在Y∈∑*，|Y|≤p(|X|)且A(X，Y)=1} 多项式时间可验证语言类VP可定义为： 定理定理8-58-5：：VP=NP。 证明见书本） 例如(哈密顿回路问题哈密顿回路问题)：一个无向图G含有哈密顿回路吗? 无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路可用语言HAM-CYCLE 定义该问题如下：HAM-CYCLE={G|G含有哈密顿回路} 299 8.3 NP完全问题完全问题•8.3.1 多项式时间变换•8.3.2 Cook定理300 8.3.1 多项式时间变换多项式时间变换 定义：定义：语言L是NP完全的当且仅当 (1)L∈NP； (2)对于所有L’∈NP有L’ ∝p L 如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NPNP难难的所有NP完全语言构成的语言类称为NPNP完完全语言类全语言类，记为NPCNPC 设 ， 是2个语言所谓语言 能在多项式时间内变换为语言 (简记为 ∝p )是指存在映身f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵机； (2)对于所有x∈ ，x∈ ，当且仅当f(x)∈ 301 8.3.1 多项式时间变换多项式时间变换 定理定理8-68-6：设L是NP完全的，则 (1)L∈P当且仅当P＝NP； (2)若L∝p ，且 ∈NP，则 是NP完全的。 定理定理8-68-6的的(2)(2)可用可用来证明问题的来证明问题的NPNP完完全性但前提是：全性但前提是：要有第一个要有第一个NPNP完全完全问题问题L L302 8.3.2 CookCook定理定理 定理定理8-7(8-7(CookCook定理定理) )：：布尔表达式的可满足性问题SAT是NP完全的 证明：SAT的一个实例是k个布尔变量 ，…， 的m个布尔表达式 ，…， 若存在各布尔变量 (1≤i≤k)的0，1赋值，使每个布尔表达式 (1≤i≤m)都取值1，则称布尔表达式 …是可满足的 SAT∈NP是很明显的对于任给的布尔变量 ，…， 的0，1赋值，容易在多项式时间内验证相应的 … 的取值是否为1因此，SAT∈NP 现在只要证明对任意的L∈NP有L∝pSAT即可详细证明见书本P307～310）303 8.4 一些典型的一些典型的NP完全问题完全问题部分NP完全问题树304 8.4.1 合取范式的可满足性问题合取范式的可满足性问题（（CNF-SATCNF-SAT）） 要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：问题描述：给定一个合取范式α，判定它是否可满足 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)这里的因子是变量 或 例如： 就是一个合取范式，而 就不是合取范式 305 8.4.2 3 3元合取范式的可满足性问题元合取范式的可满足性问题（（3-3-SATSAT））证明思路：证明思路： 3-SAT∈NP是显而易见的为了证明3-SAT∈NPC，只要证明CNF-SAT∝p 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT 问题描述：问题描述：给定一个3元合取范式α，判定它是否可满足 306 8.4.3 团问题团问题CLIQUECLIQUE 证明思路：证明思路： 已经知道CLIQUE∈NP通过3-SAT∝pCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V’V，|V’|=k，且对任意u，w∈V’有(u，w)∈E。 307 8.4.4 顶点覆盖问题顶点覆盖问题（（VERTEX-COVERVERTEX-COVER）） 证明思路：证明思路： 首先，VERTEX-COVER∈NP因为对于给定的图G和正整数k以及一个“证书”V’，验证|V’|=k，然后对每条边(u，v)∈E，检查是否有u∈V’或v∈V’，显然可在多项式时间内完成 其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NP难的 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在V’V，|V’|=k，使得对于任意(u，v)∈E有u∈V’或v∈V’如果存在这样的V’，就称V’为图G的一个大小为k顶点覆盖 308 8.4.5 子集和问题子集和问题（（SUBSET-SUMSUBSET-SUM）） 问题描述：问题描述：给定整数集合S和一个整数t，判定是否存在S的一个子集S’S，使得S’中整数的和为t例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，则子集S’={1，16，64，256，1040，1093，1284}是一个解。 证明思路：证明思路： 首先，对于子集和问题的一个实例 即HAM-CYCLE∝pTSP从而，旅行售货员问题是NP难的 因此，TSP∈NPC 问题描述：问题描述：给定一个无向完全图G=(V，E)及定义在VV上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k 311 第第9章章 近似算法近似算法312 第第9章章 近似算法近似算法 迄今为止，所有的NP完全问题都还没有多项式时间算法对于这类问题，通常可采取以下几种解题策略1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法近似算法313 9.1 近似算法的性能近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比近似算法的性能比定义为= 在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即 ≤ρ(n)该近似算法的相对误差近似算法的相对误差定义为= 若对问题的输入规模n，有一函数ε(n)使得 ≤ε(n)，则称ε(n)为该近似算法的相对误差界近似算法的相对误差界。 近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系：εε(n)(n)≤ρ≤ρ(n)-1(n)-1 314 9.2 顶点覆盖问题的近似算法顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或u∈V’顶点覆盖V’的大小是它所包含的顶点个数|V’| VertexSet approxVertexCoverapproxVertexCover ( Graph g ){ cset=； e1=g.e； while (e1 != ) { 从e1中任取一条边(u,v)； cset=cset∪{u,v}； 从e1中删去与u和v相关联的所有边； } return c} CsetCset用来存储顶点用来存储顶点覆盖中的各顶点初覆盖中的各顶点初始为空，不断从边集始为空，不断从边集e1e1中选取一边中选取一边( (u,v)u,v)，，将边的端点加入将边的端点加入csetcset中，并将中，并将e1e1中已中已被被u u和和v v覆盖的边删去，覆盖的边删去，直至直至csetcset已覆盖所有已覆盖所有边。 即边即e1e1为空 315 9.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和和e e 算法approxVertexCoverapproxVertexCover的性能比为2 316 9.3 旅行售货员问题近似算法旅行售货员问题近似算法 问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)要找出G的最小费用哈密顿回路 比如，费用函数c往往具有三角不等式性质三角不等式性质，即对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质 旅行售货员问题的一些特殊性质特殊性质：317 9.3.1 具有三角不等式性质的具有三角不等式性质的旅行售货员问题旅行售货员问题 对于给定的无向图G，可以利用找图图G G的最小生成树的最小生成树的算法设计找近似最优的旅行售货员回路的算法。 void approxTSPapproxTSP (Graph g){ (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；} 当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍 318 9.3.1 具有三角不等式性质的具有三角不等式性质的旅行售货员问题举例旅行售货员问题举例( (b)b)表示找到的最小生成表示找到的最小生成树树T T；；( (c)c)表示对表示对T T作前序作前序遍历的次序；遍历的次序；(d)(d)表示表示L L产产生的哈密顿回路生的哈密顿回路H H；；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路行售货员回路 319 9.3.2 一般一般的的旅行售货员问题旅行售货员问题 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NPP=NP。 换句话说，若P≠NP，则对任意常数ρ>1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法 320 9.4 集合覆盖问题的近似算法集合覆盖问题的近似算法 问题描述：给定一个完全无向图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} 321 9.4 集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题举例：用用1212个黑点表示集个黑点表示集合合X XF={S1,S2,S3,S4,SF={S1,S2,S3,S4,S5,S6,}5,S6,}，，如图所示如图所示容易看出，对于这容易看出，对于这个例子，最小集合个例子，最小集合覆盖为：覆盖为：C={S3,S4,S5,}C={S3,S4,S5,}。 322 9.4 集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题近似算法——贪心算法 算法的循环体最多算法的循环体最多执行执行min{|X|min{|X|，，|F|}|F|}次而循环体内的计算显然而循环体内的计算显然可在可在O(|X||F|)O(|X||F|)时间内完时间内完成因此，算法的计算成因此，算法的计算时间为时间为O(|X||F|min{|X|O(|X||F|min{|X|，，|F|})|F|})由此即知，该由此即知，该算法是一个多项式时间算法是一个多项式时间算法 Set greedySetCovergreedySetCover (X,F){ U=X； C=； while (U !=) { 选择F中使|S∩U|最大的子集S； U=U-S； C=C∪{S}； } return C； } 323 9.5 子集合问题的近似算法子集合问题的近似算法 问题描述：设子集和问题的一个实例为〈S,t〉其中，S={x1，x2，…，xn}是一个正整数的集合，t是一个正整数。 子集和问题判定是否存在S的一个子集S1，使得 324 9.5.1 子集合问题的指数时间算法子集合问题的指数时间算法int exactSubsetSumexactSubsetSum (S,t){ int n=|S|； L[0]={0}； for (int i=1；i<=n；i++) { L[i]=mergeLists(L[i-1],L[i-1]+S[i])； 删去L[i]中超过t的元素； } return max(L[n])；}算法以集合算法以集合S={xS={x1 1，，x x2 2，，……，，x xn n} }和目标值和目标值t t作为输入算法中作为输入算法中用到将用到将2 2个有序表个有序表L1L1和和L2L2合并成为一个新合并成为一个新的有序表的算法的有序表的算法mergeListsmergeLists(L1,L2)(L1,L2) 325 9.5.2 子集合问题的完全多项式子集合问题的完全多项式时间近似格式时间近似格式 基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式完全多项式时间近似格式。 在对表L[i]进行修整时，用到一个修整参数δ，0＜δ＜1用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y可以将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来代表，24由23来代表 326 9.5.2 子集合问题的完全多项式子集合问题的完全多项式时间近似格式时间近似格式对有序表L修整算法List trimtrim(L,δ){ int m=|L|； L1=〈L[1]〉； int last=L[1]； for (int i=2；i<=m；i++) { if (last<(1-δ)*L[i]) { 将L[i]加入表L1的尾部； last=L[i]； } return L1；} 子集和问题近似格式int approxSubsetSum approxSubsetSum(S,t,ε){ n=|S|； L[0]=〈0〉； for (int i=1；i<=n；i++) { L[i]=Merge-Lists(L[i-1],L[i-1]+S[i])； L[i]=Trim(L[i],ε/n)； 删去L[i]中超过t的元素； } return max(L[n])；} 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 i=1;i<=n;i++) { int thissum=0; for (int j=i;j<=n;j++) { for (int k=i;k<=j;k++) thissum+=a[k]; if (thissum>sum) { sum=thissum; besti=i; bestj=j; } } return sum; } thissum+=a[j]; 注意到 ，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间331 分治算法分治算法如果将所给的序列a[1:n]分为长度相等的2段a[1:n/2]和a[n/2+1:n]，分别求出这2段的最大子段和，则a[1:n]的最大子段和有3种情况。 1)a[1:n]的最大子段和与a[1:n/2]最大子段和相同；(2)a[1:n]的最大子段和与a[n/2+1:n]最大子段和相同；(3)a[1:n]的最大子段和为 ，且1≤i≤n/2，n/2+1≤j≤n对于情形(3)容易看出，a[n/2]与a[n/2+1]在最优子序列中因此，可以在a[1:n/2]中计算出 ，并在a[n/2+1:n]中计算出 则s1＋s2即为出现情形(3)时的最优值据此可设计出求最大子段和的分治算法复杂度分析复杂度分析T(n)=O(nlogn)332 动态规划算法动态规划算法记 ，1 j n，则所求的最大子段和为当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]由此可得计算b[j]的动态规划递归式b[j]=max{b[j-1]+a[j]，a[j]}， 1 j n算法显然需要O(n)计算时间和O(n)空间public static int maxSum() { int n=a.length-1; int sum=0, b=0; for (int i=1;i<=n;i++) { if (b>0) b+=a[i]; else b=a[i]; if (b>sum)sum=b; } return sum; }333 最大子矩阵和问题最大子矩阵和问题记 最大子矩阵和问题的最优值为由于其中， 设 ，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。 由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)334 最大最大m子段和问题子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和达到最大设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j](1 i m，i j n)则所求的最优值显然为与最大子段和问题类似地，计算b(i，j)的递归式为初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m) 优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1行和第i行的值因而算法中只要存储数组b的当前行，不必存储整个数组另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来计算第i行的值时不必重新计算，节省了计算时间和空间 335 动态规划加速原理动态规划加速原理 四边形不等式336 货物储运问题货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱货物储运公司要将集装箱有次序地集中成一堆规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最优值为m[1，n]由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法337 四边形不等式四边形不等式货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形对于 ,当函数w(i,j)满足时称w满足四边形不等式当函数w(i,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堆货物的贪心策略，并不能得到最优解。 •适当放松相邻性约束，引入相容结点对概念如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示•最小相容结点对a[i]和a[j] 是满足下面条件的结点对：（1）结点a[i]和a[j] 之间没有方形结点；（2）在所有满足条件（1）的结点中a[i]+a[j]的值最小；（3）在所有满足条件（1）和（2）的结点中下标 i 最小；（4）在所有满足条件（1）（2）和（3）的结点中下标 j 最小•相应的最小相容合并树，如图所示341 相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同中所处的层序相同中所处的层序相同中所处的层序相同 根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。 342 算算 法法1. 组合阶段: 将给定的n个数作为方形结点依序从左到右排列，a[1]，a[2]，…，a[n]反复删除序列中最小相容结点对a[i]和a[j]，(i 在所有从I到J的路中，路长最短的路称为从I到J的最短路带权区间图的单源最短路问题要求计算从S中一个特定的源区间到S中所有其他区间之间的最短路区间集S(i)的扩展定义为：S(i)T，其中T是满足下面条件的另一区间集T中任意区间I=[a,b]均有b>b(i)设区间I(k)( ki )是区间集S(i)中的一个区间，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)中的无效区间，则对任意j>i，区间I(k)是S(j)中的无效区间性质性质2：：集合S(i)中所有有效区间的并覆盖从a(1)到b(j)的线段，其中b(j)是S(i)的最右有效区间的右端点性质性质3：：区间I(i)是集合S(i)中的有效区间当且仅当在S(i)中有一条从I(1)到I(i)的路。 性质性质4：：当i>k且dist(i,i) 以区间的右端点的值为序如图所示2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，在最坏情况下需要时间O(logn)2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点在最坏情况下，每删除一个结点需要时间O(logn)综上，算法shortestIntervalPaths用平衡搜索树的实现方案，在最坏情况下的计算时间复杂性为O(nlogn)348 实现方案实现方案2 2采用并查集结构用整数k表示区间I(k),1kn初始时每个元素k构成一个单元素集，即集合k是{k}，1kn1)每个当前有效区间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))=min{j|a(k) 5)对于当前区间集S(i)，用一维数组dist记录dist(j,i)的值6)用dist[k]=-1标记区间I(k)为无效区间在最坏情况下，算法需要 计算时间, 其中 是单变量Ackerman函数的逆函数 349 优化搜索策略优化搜索策略 350 最短加法链问题最短加法链问题给定一个正整数和一个实数，如何用最少的乘法次数计算出xn例如，可以用6次乘法逐步计算x23如下：x,x2,x3,x5,x10,x20,x23 可以证明计算最少需要6次乘法计算的幂序列中各幂次1，2，3，5，10，20，23组成了一个关于整数23的加法链在一般情况下，计算xn的幂序列中各幂次组成正整数的一个加法链上述最优求幂问题相应于正整数的最短加法链问题，即求n的一个加法链使其长度达到最小正整数的最短加法链长度记为l(n)351 回溯法回溯法问题的状态空间树如图所示其中第i层结点ai的儿子结点ai+1>ai由aj+ak, kji所构成 private static void backtrack(int step) {// 解最短加法链问题的标准回溯法 int i,j,k; if (a[step]==n) // 找到一条加法链 { if (step 用标准的回溯法只能对较小的构造出最短加法链352 迭代搜索法迭代搜索法•深度优先搜索: 算法所搜索到的第一个加法链不一定是最短加法链•广度优先搜索: 算法找到的第一个加法链就是最短加法链，但这种方法的空间开销太大•迭代搜索算法: 既能保证算法找到的第一个加法链就是最短加法链，又不需要太大的空间开销其基本思想是控制回溯法的搜索深度d，从d=1开始搜索，每次搜索后使d增1，加深搜索深度，直到找到一条加法链为止private static void iterativeDeepening() {// 逐步深化的迭代搜索算法 best=n+1; found=false; lb=2; // 初始迭代搜索深度 while (!found){ a[1]=1; backtrack(1); lb++; // 加深搜索深度 } }对于正整数，记(n)=logn，v(n)=n的2进制表示中1的个数迄今为止所知道的l(n)的最好下界是l(n)≥lb(n)= (n)+logv(n)利用这个下界，可以从深度lb(n)开始搜索，大大加快了算法的搜索进程。 353 剪枝函数剪枝函数•设ai和aj是加法链中的两个元素，且ai>2maj由于加倍是加法链中元素增大的最快的方式，即ai2ai-1，所以从aj到ai至少需要m+1步如果预期在状态空间树T的第d层找到关于n的一条加法链，则以状态空间树第i层结点ai为根的子树中，可在第d层找到一条加法链的必要条件是2d-iai≥n•当 时，状态空间树中以结点ai为根的子树中不可能在第d层之前找到最短加法链 •设在求正整数n的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为d且正整数可表示为n=2t(2k+1)，k>0，则在状态空间树的第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)
