大连海事大学-刘巍-高等运筹第九讲.ppt

高等运筹学,大连海事大学 刘巍,目录,第一篇 运筹学发展历史 第二篇 运筹学中的数学规划 第三篇 运筹学中的组合优化 第四篇 运筹学中的随机优化 第五篇 运筹学中的博弈论 第六篇 运筹学中管理科学 第七篇 运筹学中智能计算 第八篇 运筹学发展势态,第九讲内容,第十四章 组合数学及相关问题,第十四章 组合数学及相关问题,1 组合数学 2 近似算法 3 组合多面体 4 生物分子网络,1 组合数学,组合数学是近几十年来发展最为迅速的一个数学分支，它与分析、代数、数论、概率论等基础数学的多个学科有密切联系，组合结构已经成为许多数学理论不可或缺的组成部分。离散结构在信息科学、物理学、生物学和化学等众多领域中大量出现，为组合数学的发展提供了强大的动力。,近年来，组合数学的思想和方法在数据结构和算法分析中都有重要的应用;利用符号计算中的算法，数学软件正在为越来越多的数学领域服务。组合设计为现代移动通信以及光纤通信中的编码技术提供了基础;它还应用于身份认证、密钥分享、数字签名等密码系统的设计中。此外，利用组合数学为处理基因序列比对和物种关系分析中的大量数据提供了一个有效的途径。组合数学在信息时代将有着非常广阔的应用研究前景。,两个传说,在我国古老的易经中有这样一句话：“河出图，洛出书，圣人则之。”后来，人们根据这句话传出许多神话。,传说在伏羲氏时代，黄河里跃出一匹龙马，龙马背上驮了一幅图，上面有黑白点55个，用直线连成10数（如图），后人称之为“河图”。,又传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个 大乌龟，甲上背有9种花点的图案，9种花点数正巧是19这9个数，各数位置的排列也相当奇妙，横行、纵列以及两对角线上各自的数字之和都为15（如图），后人称之为“洛书”。,河图、洛书两图中黑点组成的数都是偶数（古代称阴数），白点表示的数是奇数（古代称阳数）。其中把“洛书”用数字表达就是下面的数表，其任意横、竖、斜各条直线上的三个数之和均相等（等于15），这就是我们今天所说的 “幻方”。,幻方可以看作是一个 3阶方阵，其元素是1 到9的正整数，每行、 每列以及两条对角线 的和都是15。,5,1,9,3,7,2,4,8,6,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。,1.1 加法法则与乘法法则. 加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。,一、排列组合, 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。, 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。, 乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。,集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。,例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3 = 15 个。,例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。,例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是4 4 = 16， 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相互相容性。,例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外. 故有999916560个. 含1的有：99996560=3439个,另: 全部4位数有104 个,不含1的四位数有94个,含1的4位数为两个的差: 10494 = 3439个,2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。,不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个,不含0小于10000的正整数有 9+92+93+94=(951)/(91)=7380个,含0小于10000的正整数有 99997380=2619个,1.2排列与组合,定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。,若取出r个元素而不考虑次序，则称从n个不同元中取r个元的组合。其组合的个数记为C(n,r),规定：,从n个不同元中取n个的排列称为n的全排列,我们有下列排列与组合的计数公式：,特别地，对于全排列有P(n, n)=n!。,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。 故有P(n,r)=n(n-1) (n-r+1) 有时也用nr记P(n,r),若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。,故有 C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!,1.3模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与1,n元一一对应的关系. 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难,于是可设法构造一易于计数的B，使得A与B一一对应。,二、容斥原理,例 求1，20中2或3的倍数的个数。,解 2的倍数是：2,4,6,8,10,12,14,16,18,20. (10个) 3的倍数是：3，6，9，12，15， 18。 (6个) 但答案不是10+6=16 个，因为6，12，18在两类中重复计数，应减去。 故答案是：16-3=13,容斥原理研究有限集合的交或并的计数。,DeMorgan定理 :,DeMogan定理的推广：,设：,容斥原理：,最简单的计数问题是求有限集合A和B的并的元素数目。显然有,例：一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？,解：令，M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；所以有,即学校学生数为336人。,一般地，我们可得定理：,定理：设A1,A2, ,Am均为有限集，m2,则,，其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：,容斥原理指的就是这两个式子。,例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。,解：设A为ace作为一个元素出现的排列集， B为 df作为一个元素出现的排列集， 则AB 为同时出现ace、df的排列数。,根据容斥原理，不出现ace和df的排列数为：,=6!- (5!+4!)+3!=582,例2 求从1到500的整数中能被3或5除尽的数的个数。,解： 令 A为从1到500的整数中被3除尽的数的集合， B为被5除尽的数的集合,则,例3 求由a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目。,解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是：3n。,a，b，c至少出现一次的n位符号串集合即为,三 、鸽巢原理,我们可能经常会遇到这样的情况：在一桌酒席上，十来个本来不相识的人坐在一起，经过不太久的交流，马上会有人找到自己的“知音”，他们可能是校友、同行、同乡、同姓、同年龄、同属相或者是朋友的朋友、朋友的同乡、同乡的朋友等。这种情况几乎在每次酒席中都会发生，以致让人感觉到这世界真是太小。难道这都是巧合吗？,聚会认友,我们经常会参加各种聚会。如果我说：在任何一种聚会中，一定有两个人，他们在场的朋友数是一样多的。你一定会很吃惊。但是，我们可以用鸽巢原理来说明，这是千真万确的。,聚会的朋友,在任何6个人中，一定可以找到3个人，他们或者互相都认识，或者互相都不认识。,六个人的聚会,3.1 鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有 一个巢内有至少有两个鸽子。”,例 367人中至少有人的生日相同。 例 10双手套中任取11只，其中至少有两只是完整配对的。 例 参加一会议的人中至少有人认识的别的参加者的人数相等。,例 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是 另一个的倍数。,证 设n+1个数是 a1 , a2 , , an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。 组成序列 r1 , r2, , , rn+1。这n+1个数仍在1 , 2n中，且都是奇数。而1 , 2n中只有n个奇数 . 故必有 ri = rj = r , 则 ai = 2i r, aj = 2j r .若ij ，则 ai 是 aj 的倍数。,例 设 a1 , a2 , , am是正整数序列，则至 少存在k和 l , 1k l m，使得和 ak + ak+1 + + al 是m的倍数。,证设Sh = ai , Sh rh mod m 0rhm-1 h = 1 , 2 , , m . 若存在 l , Sl0 mod m 则 命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即 Sk Sh，不妨设 h k则 ShSk = ak+1 + ak+2 + + ah 0 mod m,i=1,h,例 设 a1 , a2 , a3为任意个整数，b1b2b3 为a1 , a2 , a3的任一排列，则 a1b1 , a2b2 , a3b3中至少有一个是偶数,证 由鸽巢原理， a1 , a2 , a3必有两个同奇 偶设这个数被除的余数为 xxy，于 是b1 , b2 , b3中被除的余数有个x，一个 y这样a1b1 , a2b2 , a3b3被除的余 数必有一个为,3.2 鸽巢原理之二,鸽巢原理二 m1 , m2 , , mn都是正整数，并有m1 + m2 + +mnn + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢中至少有mi个鸽子，i = 1 , 2 , , n,上一小节的鸽巢原理一是这一原理的特殊情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的鸽子数mi1 则鸽子总数 m1 + m2 + +mnn ，与假设相矛盾,推论 n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子,例 证明每个长为n2+1的实数序列中，一定存在长为n+1的递增或递减子序列（不一定是严格递、减）。,推论 若n个整数的平均数大于r-1，则至少有一个整数大于等于r。,证明：设,为任取的实数序列。若此序列中不存在长为n+1 的递增子序列,则一定存在长为n+1的递减序列.,令mi为以ai为首项的最长递增子序列的长度，i=1,2,n2+1。,因为n2+1=n(n+1)-1+1,由鸽笼原理的推论可知。,若有某个min+1，则结论成立。若不然，必有mi n+1，从而有mi n。,例 设A= a1a2a20是10个0和10个1 组成的 进制数B=b1b2b20是任意的进制数 C = b1b2b20 b1b2b20 = C1C2C40，则 存在某个i ，1 i 20，使得 CiCi+1Ci+19与a1a2a20至少有10位对应相等,A,B,C,第 i 格,第 i +19格,1 2 19 20 1 2 19 20,1 2 19 20 1 19 20,证 在C = C1C2C40中，当 i 遍历1 , 2 , , 20时，每一个bj历遍 a1 , a2 , , a20因A中 有10个0和10个1，每一个bj都有10位次对应 相等从而当 i历遍1 , , 20时，共有 10 20=200位次对应相等故对每个 i平均 有200 /20 = 10位相等，因而对某个 i 至少 有10位对应相等,四、母函数与递推关系,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,4.1 母函数,定义：给定序列(a0,a1,an,)，记为an.函数 f(x)= a0+a1x+anxn+ 称为该序列的普通母函数，简称母函数。,例 常数列(1,1,)的母函数为 f(x)= 1+x+xn+=1/(1-x) 数列C(n,i),i=0,1,2,n的母函数为,这里的母函数只是“形式幂级数”，运算均按收敛 幂级数进行。,母函数的组合意义：考察,其中： x前的系数为a,b,c的所有可重1-组合， x2前的系数为a,b,c的所有可重2-组合， 一般地： xn前的系数为a,b,c的所有可重n-组合，,在前式中取a=b=c=1,则xn前的系数为a,b,c的所有可重n-组合数F(3,n).,所以，构造某组合问题的组合数an的母函数f(x)的基本方法为： 用一个乘积因子(1+x+x2+)来代表一个所选元素，若该元素可重复n次，则因子中应出现xn。,例 设有2个红球，3个白球，1个黑球和1个黄球. 求从这些球中取出5个的不同方案数。,解：设从所给球中取出i个的不同方案数为ai,则 由题设可得ai的母函数为,例 求用1元和2元的钞票支付n元的不同方式数。,解：设所求不同方式数为an,则由题设可得an的 母函数为,于是,定义：给定序列(a0, a1,an,)，记为an.函数 称为该序列的指数型母函数,简称指数母函数。,例 常数列(1,1,)的母函数为,例 从 n 个不同元素中取 r 个的排列数P(n，r)指数母函数为：,例 n 个不同元素的可重 r-排列数 nr (r = 0, 1, 2, )的指数母函数为,例 求用1,2,3,4,5五个数字组成的n位数的个数，要求1出现的次数为偶数，2 出现的次数为奇数，并且3至少出现一次。,解：设所求n位数的个数为an ，则由题设可得an的指数母函数为：,从而有,所以,4.2 递推关系,定义：设(a0,a1,an,)是一个序列，把该序列中 an 与它前面几个ai(0in)关联起来的方程称为递推关系。序列中的一些已知条件称为初始条件。,例如,利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：,例一. Hanoi Tower（河内塔）问题：N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。,算法：,N=2时,第一步先把最上面的一个圆盘套在B上,第二步把下面的一个圆盘移到C上,最后把B上的圆盘移到C上,到此转移完毕,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,算法复杂度为：,H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(*)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。,4.3 递推关系的求解方法,（1）迭代法,例如前面的Hanoi Tower（河内塔）问题：,我们有,（2）母函数法,例如前面的Hanoi Tower（河内塔）问题：,由递推关系，我们有,我们设an的母函数为,由递推关系可得,故有,解得,所以,（3）常系数线性递关系的解法,若 f (n) = 0 则称序列an为k阶常系数线性齐次 递推关系。,称： xk+b1xk-1+.+bk-1x+bk = 0 为k阶常系数线性递推关系的特征方程。,齐次常系数线性递关系的解法,若递推关系的特征多项式有k个相异实根x1, x2, xk，则递推关系的通解为：,其中c1, c2, ck为任意常数。,若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解。,例 求解：,解：此递推关系的特征方程为,其特征根为,故其通解为,由初始条件可得 F0 = 0，将F0 = 0， F1 = 1代入得,解得,所以,若特征根出现一对共轭复根x1=a+bi , x2= a-bi 时，则递推关系的通解可表示为：,若对递推关系再给出一组k个初始值，还可以由 通解求出满足初始条件的唯一解。,其中,例：求下列n阶行列式dn的值。,解：根据行列式性质，有,此递推关系的特征方程为,其特征根为,故其通解为,由初始条件 d1 = 1，d2 = 0得,解得,所以,若特征根出现k重根。不妨设a1是k的重根。则递推关系的解对应于a1的项为 其中A0, A1, . , Ak 是k个待定常数,例：求下列n阶行列式dn的值。,解：,根据行列式性质，有,此递推关系的特征方程为,其特征根为,故其通解为,由初始条件 d1 = 2，d2 = 3得,解得,所以,非齐次常系数线性递关系的解法,定理：递增推关系（*）的通解为,f(n)是n的t次多项式的形式。,若1 不是(*)的特征方程的根,则(*)有特解形式为,若1 是(*)的特征方程的m重根，则(*)有特解形 式为,例 求和式,解：设,从则可得,其对应的齐次递推关系为,其特征方程为,其对应的齐次递推关系的通解为,因为1 是特征方程式的1 重根，f(n)是n的三次多 项式。所以有下列形式的特解：,代入题上的递推关系得,于是可得方程组,从而解得,所以原递推关系的通解为,代入初始条件a1=1得,解得 C = 0 ,故有,f(n)是 b n 的形式( b 为常数)。,若b 不是(*)的特征方程的根，则(*)有特解形式 为,若b 是(*)的特征方程的m重根，则(*)有特解形 式为,例 求解下列递推关系,其对应的齐次递推关系的通解为,解：其对应的齐次递推关系为,其特征方程为,因为2 是特征方程式的1 重根，所以有下列形式 的特解：,代入题上的递推关系，求解得,所以原递推关系的通解为,代入初始条件a0 = 0， a1 = 1得,从而解得,所以原递推关系的解为,2 近似算法,近似算法是求解组合优化问题的一类多项式时间算法，它们尽管不能确保对问题的每一个实例都可以求得最优解，但是可以保证求得的解的目标值与最优解的目标值相差不多。自20世纪60年代末格雷厄姆在研究排序问题时提出第一个近似算法以后，特别是70年代初库克首次证明了存在NP一完全问题以来，为各种各样的组合优化问题设计近似算法就一直是组合优化领域的一个重要研究方向。,主要包括三个方面: 设计近似比越来越小的近似算法; 设计运行时间越来越短的近似算法; 证明近似比的下界或者不可近似性。,已有的大量研究主要都集中在第一个方面，人们先后提出了对偶、半定规划、随机算法、平面划分和次模函数等技巧。第二方面的工作主要是针对存在多项式时间近似方案的NP一难问题，而第三方面的工作主要是利用20世纪90年代阿罗拉等人提出的概率可验证系统。这一方向中有很多问题有待解决。,所有已知的解决NP-难问题算法都有指数型运行时间。但是，如果我们要找一个“好”解而非最优解，有时候多项式算法是存在的。 给定一个最小化问题和一个近似算法，我们按照如下方法评价算法：首先给出最优解的一个下界，然后把算法的运行结果与这个下界进行比较。对于最大化问题，先给出一个上界然后把算法的运行结果与这个上界比较。,迄今为止，所有的NP完全问题都还没有多项式时间算法。 对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解,旅行售货员问题近似算法,问题描述：给定一个完全无向图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就具有三角不等式性质。,对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。 void approxTSP (Graph g) (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序