数学建模常用技巧.ppt

数学建模-常用技巧,常用技巧,计算复杂性分析 算法设计 精确算法 近似算法 算法计算量估计、算法优劣比较,比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。,例1 （整理问题）给定n个实数a1, a2, an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1, b2, bn，b1 b2 bn。,（算法1） 取出a1, a2, an中的最小者，令其为b1。从a1, a2, an中去除b1，在余下的n1个数中选出最小者，令其为b2，直至得到b1, b2, bn。 容易看出，为了排出b1, b2, bn，算进行了 n(n-1)/2 次比较。,（算法2） 步0 b1a1 步1 设已有b1,bk (1kn)，将按两分法比较的方式把ak+1排入其中：若b1biak+1bi+1bk，令（b1, b2,bk , bk+1）（b1, bi, ak+1, bi+1, , bk）。若k+1n，令k k+1，返回步1。,计算复杂性,我们来分析一下算法2的计算量：,排出b1不必作比较，排出b2只需作一次比较，一般，在排ak+1时，设2r1k2r，则只需作r次比较即可将ak+1安排在它应排的位置上。例如在排a8时，k=7，先和b4比，若a8b4，可再和b6比（若a8b4则和b2比），易见，只要比3次即可排入a8，由于rlog2k+1，算法的比较次数不超过,令 ， ，设计算机每秒可作C次比较，则算法1与算法2整理a1, a2, an所用的时间分别为 若n=100万，C=100万次/秒，则t15.8天，而t220秒。可见在较大规模的整理问题时，算法2明显优于算法1。,现设一台每小时能作M次运算的计算机，并设求解某一问题已有了两个不同的算法。算法A对规模为n的实例约需作n2次运算而算法B则约需作2n次运算。于是，运用算法A在一小时内可解一个规模为 的实例，而算法B则只能解一个规模为log2M的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作100万次运算，则算法A一小时大约可解一个规模为n=60000的实例，而算法B在一小时内只能解一个规模 的实例且n每增加1，算法B求解时所化的时间就将增加1倍。例如算法B求解一个n=50的实例将连续运算357年多。,现设计算速度提高了 100倍，这对计算机来讲已是一个相当大的改进。此时算法A可解问题的规模增大了10倍，而算法B可解问题的规模只增加了log21007。前者可解问题的规模成倍成倍地增加而后者则几乎没有什么改变，今天无法求解的问题将来也很少有希望解决。,由于这一原因，人们对算法作了如下的分类：,（多项式算法）设A是求解某一问题D的一个算法，对D的一个规模为n的实例，用fA(D,n)表示用算法A求解这一实例所作的初等运算的次数。若存在一个多项式P(n)和一个正整数N，当nN时总有 fA(D,n)P(n)（不论求解D的怎样的实例，只要其规模为n），则称算法A为求解问题D的一个多项式时间算法，简称多项式算法。,（指数算法）设B是求解某一问题D的一个算法，f B(D,n)为用算法B求解D的一个规模为n的实例时所用的初等运算次数，若存在一个常数k0，对任意正整数N，总可找到一个大于N的正整数n及D的一个规模为n的实例，对这一实例有fB(D,n)=O (2kn)，则称B为求解问题D的一个指数算法。,多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。,下面的表1列出了在规模大约为n时各类算法的计算量，而表2则反映了当计算机速度提高10倍、100倍时，各类算法在1小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）,表1 几个多项式和指数时间复杂性函数增长情况,表2 1小时内可解的问题实例的规模,由上可知4n2与2n2都是O(n2)，nlogn+3n是O(nlogn)，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。 下面介绍六个最初的NP难问题,（1）（3满足问题，简记3SAT问题） 每一个句子都是一个三项式的SAT问题，称为3SAT问题。 例如， 就是3SAT的一个实例。,命题逻辑中合取范式(CN F) 的可满足性问题(SA T ) 是当代理论计算机科学的核心问题, 是一典型的N P 完全问题.,考虑CN F：A = C1 C i Cn (1) 子句C i 具有如下形式：Pi,1Pi,2Pi,ki Pri,1 Pri,2 Pri,kri ,其中Pi,1, Pi,2, , Pi,ki, Pri,1, Pri,2, , Pri,kri是两两不同的文字, Pi,j为命题变元集P1, P2, , Pm 中的一个变元, 文字Pi 表示变元Pi 的非,m 表示命题变元的个数, n 表示子句的个.,一个SA T 问题是指: 对于给定的CN F 是否存在一组关于命题变元的真值指派使得A 为真.,下面介绍六个最初的NP难问题,（1）（3满足问题，简记3SAT问题） 每一个句子都是一个三项式的SAT问题，称为3SAT问题。 例如， 就是3SAT的一个实例。,下面介绍六个最初的NP难问题,如果A 为真, 则CN F 的每个子句中必有一个命题变元为1 (真) , 将每个子句中的每个命题变元取反, 则CN F 的每个子句中必有一个命题变元为0(假) , 然后将看成加, 将看成乘, 将变元P i 看成实参数x i, 则SA T 问题就可以转换为一个求相应实 函数最小值的优化问题. 令T 表示这种转换, 它可递归地定义为,T : A Rm R , T (C1C iCn) = T (C1) + + T (C i) + + T (Cn), T (C i) = T (Pi, 1P i, 2P i, k i Pri, 1Pri, 2 Pri, k ri )= T (P i, 1) T (P i, 2) T (P i, k i ) T (Pri, 1) T (Pri, 2) T (Pri, k ri ) , i= 1, , n. T (P i) = 1- x i , T (Pi) = x i, x i0, 1 , i= 1, ,m , T (T ) = 1, T (F ) = 0.,（1）（3满足问题，简记3SAT问题） 每一个句子都是一个三项式的SAT问题，称为3SAT问题。 例如， 就是3SAT的一个实例。,下面介绍六个最初的NP难问题,例如, T (P1 P2) (P1P2) ) = T (P1P2) + T (P1P2)= T (P1) T (P2) + T (P1) T (Pv2) = (1- x1) x2+ x1x2, 用E (x1, x2, , xm ) 表示T (A ) 在点( v(P 1 ) , , v(Pm ) ) 的值, 则有下面定理. 定理1. 赋值v 为使A 可满足的充要条件是E(x1,x2,x m) 达到最小值0.,于是一个SA T 问题可以转化为优化模型求解: minE(x1,x2,x m) ST:xi=0,或1,2）（三维匹配问题3DM）X、Y、Z是三个不相交的集合，| X | = | Y | = | Z | =q，。 问：M中是否包含一个匹配M，使得 （等价问题是求最大三维匹配）。,注：这里给出的是标准形式，一般可不必要求| X | = | Y | = | Z |，表示笛卡尔乘积。,三维匹配问题是二维匹配（2DM）问题的推广，2DM是P问题而3DM是NP完全的。一个匹配是指M的一个子集合(xi, yi, zi)，xiX，yiY，ziZ，且当下标不同时，它们分别取三个集合中的不同元素。3DM可作如下形象的解释：记一单身男人集合为X，一单身女人集合为Y，此外还有一个住房集合Z。其间存在一相容关系（例如有些人之间不愿组成家庭，或不愿住某一住房），这样就给出了一个集合 ，M是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住房。,下面介绍六个最初的NP难问题,（3）（划分问题） 给定一正整集合A=a1, a2, , an，问是否存在A的一个子集A,使得 ，即是否可将A中的数分成总和相等的两部分。,（4）（顶点复盖问题VC）给定一个图G=（V，E）及一个正整数K| V |，问G中是否有不超过K个顶点的复盖。 （一个顶点的子集称为G的一个复盖，若它至少包含G中任一边的两个端点之一）。,下面介绍六个最初的NP难问题,找出所有满足xi=0或1，f=ai*xi= （A）/2的解,练习：用MATLAB或LINGO实现划分问题,（5）（团问题,控制集问题） 给定图G=（V，E）及一正整数K| V |，问是否存在图G中的一个团V，| V| K。（G的一个顶点的子集V称为G的一个团，若V中任意两点间都有E中的边相连）。,问题4,5的应用之一: 系统监控模型,设图G = (V, E), KV如果图G的每条边都至少有一个顶点在K中,则称K是G的一个点覆盖. 若G的一个点覆盖中任意去掉一个点后不再是点覆盖, 则称此点覆盖是G的一个极小点覆盖. 顶点数最少的点覆盖, 称为G的最小点覆盖.,例如, 右图中,v0, v2, v3, v5, v6等都是极小点覆盖. v0, v1, v3, v5,v0, v2, v4, v6都是最小点覆盖.,最大独立点集,定义2 设图G = (V, E ),I V如果I中任意两个顶点在G中都不相邻, 则称I是G的一个独立点集. 若G的一个独立点集中,任意添加一个点后不再是独立点集,则称此独立点集是G的一个极大独立点集. 顶点数最多的独立点集,称为G的最大独立点集.,例如, 右图中,v1, v4等都是极大独立点集. v1, v3, v5,v2, v2, v6是最大独立点集.,最小控制集,定义3 设图G = (V, E ), D V如果vV, 要么vD, 要么v与D的某个点相邻, 则称D是G的一个控制集. 若G 的一个控制集中任意去掉一个点后不再是控制集,则称此控制集是G的一个极小控制集. 顶点数最少的控制集,称为G的最小控制集.,例如, 右图中,v1, v3, v5是极小控制集, v0是最小控制集.,系统监控问题之二,假设下图代表一指挥系统,顶点v1, v2, , v7表示被指挥的单位,边表示可以直接下达命令的通信线路. 欲在某些单位建立指挥站,以便可以通过指挥站直接给各单位下达命令,问至少需要建立几个指挥站? 这就是要求最小控制集问题.,v1, v3,v3, v5等都是最小控制集,所以至少需要在2个单位建立指挥站.,到目前为止, 还没有找到求最小控制集的有效算法.一种启发式近似算法.,最小点覆盖、最大独立点集和最小控制集的关系,定理1 设无向图G = (V, E )中无孤立点(不与任何边关联的点),若D是G中极大独立点集,则D是G中极小控制集. 定理2 设无向图G = (V, E )中无孤立点,KV,则K是G的点覆盖当且仅当Kc =VK是G的独立点集. 推论 设无向图G = (V, E )中无孤立点,KV,则K是G的最小(极小)点覆盖当且仅当Kc =VK是G的最大(极大)独立点集.,若图G中的一个顶点和一条边相互关联，则称它们相互覆盖 覆盖图G的所有边的一个顶点子集，称为图G的一个顶点覆盖 类似，覆盖图G的所有顶点的一个边子集称为图G的一个边覆盖 G的所有顶点覆盖中顶点最少的数目称为图G的顶点覆盖数，或者简称为点覆盖记为0 一个图G的边覆盖、最大边覆盖以及边覆盖数并用来表示一个图G的边覆盖数。 分别用和来表示图G的独立数和匹配数。,可知，关于一个阶数为P的非平凡的连通图的覆盖数与独立数具有如下关系：P 由此结果容易看出，求一个图G的最小覆盖数等价于求这个图的最大独立集而图的最小覆盖问题、图的最小团问题以及图的最大独立集问题两两等价,设G(V,E)是一无向图，其中V是图中顶点集合，E是边的集合V表示图中顶点的个数E表示图中的边数 顶点覆盖问题是找一V的子集S,找子集S，满足（i,j) E,i和j至少有一个属于S,即求解下列规划模型 ： MIN CX xiS, ST： (i=1.p)(j=i+1.P)aij(1-xi)(1-xj)=0 C=1,1;X=x1,x2,xp;(aij)图的邻接矩阵 Xi=1(vi S)否则为0；,（6）（哈密顿圈问题HC）,包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨; 闭的Hamilton轨叫做Hamilton圈或 圈； 含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。,判断某图是否为哈密顿图至今还是一个难题. 总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法. 1. 观察出哈密顿回路.,（6）（哈密顿圈问题HC）,1. 观察出哈密顿回路. 下图(周游世界问题)是哈密顿图 易知a b c d e f g h i j k l m n p q r s t a 为图中的一条 哈密顿回路.,（6）（哈密顿圈问题HC）,设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj) n1 () 则G 中存在哈密顿通路.,设G为n (n3) 阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有 d(vi)+d(vj) n （） 则G中存在哈密顿回路，从而G为哈密顿图.,2满足条件（）的图是哈密顿图. 例 完全图Kn (n3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n1) n（n3）， 所以Kn为哈密顿图. 3哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.,例2. （婚姻问题）在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为A、B、C，三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她们的喜欢程度而定,（见下表）： X Y Z A 3 5 26 B 27 10 28 C 1 4 7 问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。,婚姻问题-P问题,例2. 显然是指派问题的实例，但它也可以看成是两分图赋权匹配问题的实例。,用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到左图。左图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。,定义3. (匹配) 图G的一个匹配是指边集E的一个子集M，M中的任意两条边 均不具有公共的顶点。,容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的 匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。 以上举的是一个P问题，下面来看一个NP难问题,用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到左图。左图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。,定义3. (匹配) 图G的一个匹配是指边集E的一个子集M，M中的任意两条边 均不具有公共的顶点。,容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的 匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。 以上举的是一个P问题，下面来看一个NP难问题,例3 （装箱问题Binpacking）有一批待装箱的物品J=p1,pn，pj的长度为l(pj)。现有一批容量为C的箱子（足够数量），要求找到一种装箱方法，使得所用的箱子数最少。,例3是一个一维的装箱问题。例如，我们有一批具有相同长度的钢材，如果想取出几根已知长度的钢料生产某种设备，当然会希望少用几根原始钢材以减少浪费。此时，我们就遇到了一个一维的Binpacking问题。当我们想从购买来的三夹板上锯出n块已知长、宽的板来制作家具时，遇到的是二维Binpacking问题。而当我们真正想把一批已知长、宽、高的物体装入具有相同尺寸的箱子时，又遇到了三维的。下面的定理 告诉我们，即使是一维的 Binpacking问题也是NP完全的，故二维和三维的 Binpacking问题更不可能是P问题（它们也是NP完全的）。,定理1. （一维）Binpacking问题是NP完全的。,证明：易见，划分问题可转化为Binpacking问题。事实上， 取 ，J=c1,cn可划分为两个相等的集合的充要条件是 它们可装入两只容量为C的箱中。,装箱问题-NP问题,存在两种不同类型的Bin-packing问题。 第一类不允许整理，必须按给定的顺序装箱，称为on-line问题； 第二类允许先对物品加以整理，然后再装箱，称为off-line问题。,（一）on-line排序问题的近似算法,1. NF（Next Fit）算法,步1 将P1装入B1中。,步2 装Pi, (i =2, , n)。设Bj是具有最大足码的非空箱，若Pi可继续装入Bj则将其装入，否则将Pi装入Bj + 1中，即装入下一空箱中（前面的箱子将不再使用）。,记NF算法使用的箱子数为NF（L），则： NF(L) 2OPT(L)，且2是紧的，即不能被减小。,2. FF（First Fit）算法,步1 将P1装入B1中。,步2 装Pi, i =2, , n。找出最小的j使Pi可装入Bj中，将Pi装入其中，在装 箱结束前，每一箱子的剩余空间均有可能被继续利用。,定理2 设FF(L)为用FF算法将L中的物品装箱所用的箱数，则有 FF(L) 1.7OPT(L) + 1，且1.7是紧的，即不能被减小，（证明有较大难度， 从略）。,3. BF（Best Fit）算法,步1 装P1装入B1中。,步2 装Pi, i =2, , n。在能够装下Pi的箱中找出已装得最多（即剩余空间 最小）的一只Bj，将Pi装入Bj。 定理3 设BF(L)为用BF算法将L中物品装箱所用的箱数，则有BF（L） 1.7OPT(L) + 1，且1.7是紧的，（证明从略）。,谢谢！,