数学建模常用技巧.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个单位建立指挥站.,到目前为