数学建模常用技巧幻灯片.ppt

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