数学建模离散优化模型与算法设计.ppt

数学建模离散优化模型及算法设计,第9章：某些P问题及其算法,之前,我们介绍了与计算复杂性有关的一些基本概念.人们发现,在离散问题中存在着两个互不相交的类：P类与NP完全类（若PNP）。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，P问题可以看成是一类具有良好性质而又较容易求解的问题，而NP完全问题则是固有地难解的。,在8.4中看到，有着广泛应用背景的线性规划问题是一个P问题。这样，作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是P问题。虽然从平均的角度讲，人们似乎更常遇到NP完全问题，但P仍不失为一个十分重要的问题类。一方面，很多P问题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些经常遇到的P问题并给出求解它们的有效算法。,一、拟阵问题及贪婪算法,在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有的P问题都具有的。,例 9.1（最小生成树问题MST）给定一连通图G=（V，E），有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有最小总权的生成树。,此问题的标准形式为给定一完全图G，其每边赋有一权数，求此完全图的最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗树。树用(U，T)表示，U为树的顶点，T为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明，对于一个连通图G，G 的任一生成树必有V-1条边。,求解最小生成树的算法主要依据下面的定理：,定理 9.1 设（V1，T1），（Vk,Tk）为连通图G中的森林，V1 U V2U Vk=V。k,若仅有一个顶点在Vi中的具有最小权的边为（,u），则必有一棵G的最小生成树包含边（,u）。,根据定1可以作了如下算法：任选一点，令 若V1=V，停；否则，找出仅有一个顶点在V1中的边里具有最小权的边（,u），设，将u加入V1（,u）加入T。重复上述步骤，直到V1=V。,证明：设G的一棵最小生成树（V，T）不含（,u）。将（,u）加入T，由于（V，T）是生成树，T U（,u）中含有过（,u）的唯一的圈。不妨设，则，此圈中的点不全由Vi中的点组成,因此必存在圈中的另一边。删去边 得到一新的生成树（V，T1），T1=，须其总权不超过（V，T）的权,即（V，T）是包含边（,u）的最小生成树。,例9.2 求图9.1中图G的最小生成树。,解：不妨从顶点开始寻找。标号1，先加入（因为边权最小），标号2。再加入 标号3。，每次加入一条一顶点已标号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找到的最小生成树已用又线标在图9.2中。,容易看出算法的计算量为O(V)2，所以此算法是有效算法，若G具有O（）条边，其中n=V，计算量的界还是不能改进的，因为每条边至少应被检查一次。,由例9.2可以看出，算法执行的每一步均加入一条可以加入的（即不生成圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被称为贪婪算法。,例9.3(入树问题)给出一个有向图G=（V，A），对A中的每一条孤e，给出一个权C（e），求A的一个具有最大权（或最小权）的子集B，要求B中任意两条孤都没有公共的终点。,考察下面的入树问题实例：,例9.4 给出有向图G=（V，A）（图9.3），孤上标出的数字为该边的权，求此图具有最大权的入树。,解：由于入树不能包含具有公共终点的孤，故对每一顶点 只能选取一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的入孤，可用计算量为O（VE）的贪婪法求解，具有最大权的入树为。,类似地，出树问题也可以用贪婪法求解。,例9.5(矩阵拟阵问题)给出一个矩阵Amxn，记其n个列向量为e1,，en。设对每一列向量en已指定一权C（en）求 的一个线性无关的子集，它具有最大的权和。,易见，这一问题也可以用贪婪法求解。集合 的线性无关的子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用线性代数知识加以证明（见习题1）。,例9.6 求矩阵A的列向量具有最大权和的独立子集,C(ei)8 4 7 5 2 6 4,解：采用贪婪法，先取权最大的列e1，同时对A作高斯消去，逐次加入线性无关的向量：,A的列向量中具有最大权的独立子集为。,定义9.1(拟阵)设E是一个有限集，为E的部分子集构成的封闭系统（即若，则必有）。若M=（E，）上的离散优化问题的每一实例均可用贪婪算法求出最优解，则称M为一拟阵。（注：被称为独立系统）。,现以矩阵拟阵为例，对定义9.1作一说明。对矩阵拟阵的每一实例，E=e1,en为矩阵列向量的集合，为E的线性无关子集构成的系统，称为独立系统，其元素被称为独立子集。由于E的任一线性无关子集的子集也是E的线性无关子集，故独立系统是封闭的。又由于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称为矩阵拟阵。例9.1被称为图拟阵，例9.3被称为划分拟阵。,拟阵问题（或称拟阵结构）有一个明显而又本质的特性，其任一极大独立子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向量的所有线性无关极大组均具有相同的向量个数，这就导出了基即矩阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为|V|-1。对于划分拟阵，孤集被划分成个|V|个子集，每一子集由指向同一顶点的孤组成。显然，任一极大独立集应在每一子集中取一条孤，故其基数为顶点个数。,我们不加证明地引入下面的定理，虽然其证明并不十分困难。,定理9.2 E为一有限集合，为E的部分子集构成的封闭独立系统。以下两个条件均为M=(E,y)构成拟阵（即其上的优化问题可用贪婪法求解）的充分必要条件：,（条件2）若I、I均为A的两个极大独立集，则|I|=|I|。,（条件1）若I、I|I|I|，则必可找到一个元素e，使得（注：|表示元素个数）,二、两分图匹配问题与增广路算法,在上一小节中我们已经看到，有些P问题可以用极为简单的贪婪法求解。但对绝大多数的P问题来说，这一结果并不成立，只能根据其本身的结构，去寻找求解它的独特算法。下面，我们将介绍几个这样的P问题。,例9.7（婚姻问题）在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为A、B、C，三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她们的喜欢程度而定：,问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。,例9.7显然是指派问题的实例，但它也可以看成是两分图赋权匹配问题的实例。,用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到图9.4。图9.4是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。,定义9.2(匹配)图G的一个匹配是指边集E的一个子集M，M中的任意两条边均不具有公共的顶点。,容易看出，酋长要解的问题是在两分图图9.4中找出一个具有最大权和的匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。,由于两分图最大权匹配问题等价于指派问题，所以它是一个P问题。对于这一P问题，我们是否也能象前面一样用贪婪法求解呢？如果用贪婪法求解例9.7，则有C嫁y（28头），去除C、y及相应边（一夫一妻）；再将B嫁x（5头），去除B、x及相应边；最后，A只能嫁Z（1头）。共得财礼34头牛。事实上，酋长的女儿只有六种嫁法（3！），比较所有方案，发现C嫁x、A嫁y、B嫁z最好（y几乎差不多同样喜欢C和A，而z则明显喜欢C而不太喜欢A），可得财礼57头牛。虽然后一算法不是多项式时间的，对待嫁者数量稍大的问题无法求得结果，但对本例，它至少表明用贪婪法没有求得最优解，因而两分图最大权匹配问题不是拟阵问题（或者讲不具有拟阵结构），从而，一般赋权图上的最大权匹配问题更不是拟阵问题。J.Edmonds将最大权匹配问题表示成为一个特殊的线性规划并由此导出了用他的名字命名的O（n4）算法，由于他的算法较复杂,本书不准备作详细介绍,有兴趣的读者可查阅C.H.Papadimitriou“组合最优化，算法和复杂性”一书第十一章。至于两分图赋权匹配问题，由于它与指派问题的等价性，完全可以用计算量O（n3）的匈牙利方法求解，也可以化为后面的网络流问题求解。,如果所有边的权均为1，则最大权匹配化成最大匹配问题（即求边数最多的匹配）。对于这一较为简单的子问题，存在着增广路算法。,定义9.3 设M是图G的一个匹配，M中的边称为匹配边，其端点称为一对配偶（其它边称为未匹配边或自由边）。V中已有配偶的点称为已盖点，否则称为未盖点。,定义9.4 依次取未匹配边、匹配边的路称为交错路。,由未盖点到未盖点的交错路称为增广路。易见，增广路中未匹配边的数目比匹配边的数目多一条，且交换增广路中的未匹配边与匹配边可以得到一个多一条边的匹配。,例9.8 在图9.5（a）中，用双线划出的边组成该图的一个极大匹配。由未盖点 出发，可作出增广路，从而可得到一个增加一条匹配边的更大匹配，如图9.5（b）所示。此时，图中虽然仍存在未盖点，但 均已成为已盖点，故（b）中的匹配已是最大匹配。本例再次表明两分图匹配问题不是拟阵问题（即使是不加权的），因为其极大独立集中的无素个数可以不同。,定理9.3 M是图G中的最大匹配当且仅当G中不存在关于M的增广路。,证明：必要性显然，现证充分性。若存在G中的更大匹配M，合并M、M得到一个图G，易见G每一顶点的次至多为2（注：G可能不连通）。G可包括偶数边的圈，圈中M与M中的边的数量相等。由于|M|M|，G中至少含一条路，其中M中的边多于M中的边，不难看出，这条路是G的关于M的增广路。,现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此算法稍加改动，还可以用于非两分图的情况。,三、网络流问题,网络流问题是又一类具有广泛应用前景的P问题，本节将介绍一些有关网络流问题的基本理论与算法。,1、最大流问题（MFP）,边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间的最大通话量；当网络是城市的街道时，我们又可能会去求两地间的最大交通流，即单位时间内允许通过的车辆数等等。,建模：给定一有向图G=（V，A），A的每一条孤（边）（i,j）上已赋一表示边容量的非负整数C（i,j）。并已指定V中的两个顶点 s、t，分别称它们为发点和收点。,设网络中已存在一个流（不一定是最大流），记孤（i,j）上的流量为（i,j），记s发出的总流量（即t收到的总流量）为，根据平衡条件，可得如下的约束条件，有,其中是 指A中以顶点i为起点的孤集，是指A中以 i为终点的孤集,(.1)式表示s发出流为，t收入的流为，其余各点只起中转作用，既不增加也不消耗流量。根据边容量限止，还应有,而我们的愿望是使总流量尽可能地大。即在（9.1）、(9.2)式约束下使达到最大，易见，这是一个线性规划问题的子问题，故 类。,对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简化问题，我们先引入一些符号。,记、为的两个不相交的子集，s，用（，）表示发点在，收点在的边集，记，并定义如下的切割概念：,定义9.5（切割）设是的顶点集合的一个真子集，为关于的补集。若、满足 且 则称和 为的一个切割。,根据切割的定义可以看出，当和 为一切割时，如果去掉连接和的边集（，），就切断了由通往t的所有通路。所以，对网络的任一切割（，），（，）必为最大流的一个上界，而。,例9.9 网络如图9.6所示，边（弧）上的两数字分别表示边容量及实际流量。取，则，显然、是网络的一个切割。对于这一切割容易算出而网络的流量。,为了尽可能地增大网络上的流量，按如下方法作出一个和具有相同顶点并具有相同发点和收点的增广网络（）（简记）。包含两类边，对中每一条边（i，j）：,（1）若，作正向边（i，j）,规定容量，即剩余容量。,（2）若，作反向边（j,i），规定容量 事实上是边（j,i）上最多可减少的容量。,第一类边称为正规边，第二类边则称为增广边。例如由图9.6中的流可以作出其相应的增广网络图9.7，其中实箭线为正规定，虚箭线为增广边，边上的数字为边容量。,如果增广网络上存在着由st的通路p（称为原网络的一条增广路），记，则只要在P中的一切正规边上增加流量a，而在对应增广边（j,i），G的边（i,j）上减少流量a，就得到G的一个由st的增大了流量a的更大的流。例如，从图9.7上可以找出增广路，a=2。于是，图9.6中的流可改进增大为图9.8(a)中的流，总流量为7。由于其增广网络图9.8(b)中不再存在增广路，无法再继续增大。容易看出，若取s出发（在增广网络上）可到达的点的集合为P，则P=,，=,，C（P，）=7，而流量已达到7，故此流已是最大流。,（1）,（2）,故，已不能再增大，（注：这是线性规划的补松驰定理）。,综上所述，有下面的有关网络流问题的定理。,定理9.5（Ford和Fulkerson最大流最小切割定理）任一由s到t的流，其流量不大于任一切割的容量C（P，），而最大流的流量则等于最小切割的容量。进而 为最大流且（P，）为最小切割当且仅当：（1）有（2）有。,增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数，而每次经改进，流量至少增加一，故算法总能很快求得最大流。,定理9.4 网络G上的流是最大流的充要条件为其增广网络上不存在由s到t 的通路。,证明：若增广网络上存在由s到t的通路P，则对P上的正规边（i,j）增加流量a，对P的增广边（j,i）对应G的边（i,j）减少流量a，即可得到一个更大的可行流。若增广网络上不存在由s到t的路，记增广图上s可达到的点组成的集合为P，则对切割（P,）必有：,2、最小费用最大流问题,对于一个给定的网络，由发点s到收点t常常存在着多个具有相同流量的最大流。如图9.9所示，图中的（a）、（b）、（c）均是流量为7的最大流，边上的两个数字依次为容量和边上的实际流量。有时候，当流流经一条边时需支付一定的费用，我们不仅希望找出一个最大流，而且希望找出的最大流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有向图G=（V，A）的每条边（弧）（i,j）给定一个边容量C（i,j）及一个单位流量费用l(i,j)。希望求出由s到t的最大流，使得总费用最少，即求最大流*，使,例如，在交通网络中，l(i,j)可以是i,j之间的距离或运费。自然，在运送相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。,对于网络上的一个现行流，作出其增广网络G()，对G中的正规边赋值l(i,j)，对G中的增广边(i,j)则赋值l(i,j)。,定义9.6 增广网络G上由s到t的流量为零但边流量不全为零的流称为一个循环流。,最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理论可以证明下面的定理：,定理9.6 网络中的流 是最小费用的，当且仅当其增广网络G中不存在负费用的循环流（证明略）。,例9.10 图9.10（a）给出了有向图G上的一个可行流，其中弧上的三个数字分别为容量、单位流费用及实际流量。图9.10（b）为相应的增广网络，其中边（弧）上的两个数字分别为容量及单位流费用。求此网络的一个更小费用流。,从图9.10（b）中可以找出一个负费用循环流s21s（其余边流量为0），每单位流量的总费用为5。调整此循环流上的流量，得到图9.11（a）中的流。原先的流总费用为17，调整后的总费用为12，减少值为负费用循环流的总费用。,图9.11（a）中流的增广网络（b）中已不存在负费用循环流，它是一个最小费用的流。,定理9.7 设1是网络上流量为的最小费用流，2是其增广网络上由s到t的最小费用单位流增广路，则1+2是此网络流量为+1的最小费用流。,证明：设1+2不是流量为+1的最小费用流，由定理6，在 1+2的增广网络中必存在一负圈C。记构造2的增广路为P。由于 1是最小费用流，1的增广网络中不存在负圈，故C中必有一边（i,j），其反向边（j,i）含在P中（因为如若不然，C不含P中任意边，则C将含在1的增广网络中，与1为最小费用流的假设矛盾，见图9.12），但这又说明P（C（i,j）是S到t的更小费用单位流增广路，与P是最小费用单位流增广路的假设矛盾。,根据定理9.7及定理9.6，求最大流的算法只需稍作变动即可用来求解最小费用最大流。算法可以用归纳方式给出，当=0时，可取=0，这显然是=0的最小费用流。在以后逐次增大流量时，若增广网络中存在着多于一条增广路时，每次均选用其中单位流费用最小的一条。这样，每次得到的均为相同流量的流中费用最小的，而最后得到的即为最小费用最大流。,网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻找网络的瓶颈即最小切割（P，）确定的边。作为一个网络流问题的应用实例，我们来求解例9.7中的婚姻姻问题：增加发点s和收点t，将原图的边改为有向边，所有边的容量为1。找出最大财礼数28，以此数减每边原有的财礼费，并用此差为各边的费用，得一最小费用最大流问题（未注数字的边费用均为零），其网络图见图9.13。此问题在使用三次增广路后可求得最佳结果。,四、最短路径问题,最短路径问题是又一个经常遇到的P问题，它在工艺流程的安排、管道或网络的铺设、设备更新等实际生产中常被用到，是网络规划的基本问题之一。顾名思义，最短路径求的是以下问题：给定一个网络，如何求出网络中指定两点间总距离（或总费用）最小的路径。,例9.11 给定图9.14中的网络，边上的数字为两顶点间的距离（或费用），求由A到E的最短路径。,求解最短路径问题的Dijkstra算法体现了动态规划算法的基本思想。若点P在A到E的最短路上，则P到E的最短路径必整个地包含在A到E的最短路径上。因为，若不然，将由P到E的最短路径导出A到E的更短路径，从而导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。（两者目的略有不同）对例9.11中的网络，如从起点A开始标导，先在A点标上0。再找出离A最近的点B3，标上A到B3的最短矩离1并记录下A点（表明由A而来）。一般，在标新顶点时，先找出离已标号顶点最近的顶点。比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号顶点距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的已标号顶点。直到拟到达的终点已标号为止。例如，图9.15指出，A到E的最短路径为AB2C1D1E，最短距离为19。,容易看出，算法是多项式时间的。在标每一顶点时，最多作了|V|次运算。算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为O（|V|2）。,按一般习惯，动态规划算法常按逆顺序进行。图9.16给出了按向前标号的结果，最短路径已用双线划出。,从图9.15中可看出A到各点的距离及最短路径，而从图9.16中则可看出由各点到E点的距离及最短路径，这是两者的区别。,读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最短路径的算法。,作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题：,例9.12 某单位使用一种设备。该设备在5年内的预期价格见表9.1，使用不同年数的设备的年维修费用见表9.2。现准备制订一个五年内的设备更新计划，使五年内支付的设备购置费用及总维修费用最少。,这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况，还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已使用年数有关。,解：作有向图图9.17，图中点i表示第i年初（或第i1）年末），弧（i,j）上的数字表示第i年初购买设备到第j年初更换，在该段时间内的总费用。例如，弧（，）上的数68表示第一年初购买设备到5年后的第六年初更换，需支付购设备费10万元及各年维修费 58 万元，共计68万元。问题化为求由顶点到顶点的最短路。,容易看出，作出n年设备更新问题的有向图将问题化为最短路径问题大约需要O(n2)计算量，其后要求求解的最短路径问题的计算量也是O(n2)，故设备更新问题可在O(n2)时间内求解。,表9.1,表9.2,五、欧拉圈与最短邮路问题,欧拉圈问题起源于著名的七桥问题。给定一个无向图G=（V，E），问能否由一个顶点出发，经且仅经过每条边一次并返回原出发顶点。如果能够，则每一个这样的圈被称为图G的欧拉圈，而图G则被称为是一个欧拉图。显然，图G为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾不能相连时则被称为欧拉路）。由此，立即可得出下面的定理：,定理9.8 G为 欧拉图的充要条件是：G是连通的且G的每一个顶点都与偶数条件相关联。,把关联偶数条边的顶点称为偶顶点，把关联奇数条边的顶点称为奇顶点，则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与一个终点），又易得出,定理9.9 G为欧拉路的充要条件为：G是连通的且奇顶点的个数为2。,综合定理9.8和定理9.9可知，G可一笔画出的充要条件为G是连通的且奇顶点的个数为0或2，当奇顶点个数为零时，尚可设法使起点和终点相重。下面的图9.18（a）为欧拉圈，而图9.18（b）则为欧拉路，后者虽可一笔画出，但必须以一个奇顶点为起点，以另一个奇顶为终点。,图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可通过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故欧拉圈问题和欧拉路问题均是十分简单的P问题，从而，等价地，一笔画问题也可十分容易地求解：若图G是欧拉图，则从任一顶点出发均可将它一笔画出；若图G是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各条边，最后到达另一奇顶点，即可将G一笔画出；否则G不能一笔画出，（当然，如何走法仍需规划一下）。,与欧拉图有较大联系的另一有名的P问题是无向图上的中国邮路问题。给定一个无向图，它的每一条边上都赋有一个表示该边长度（或费用）的权。要求从一指定顶点出发，至少经过每一条边一次最后返回原出发点，并使经过边的总长度最小。其中如重复走过某些边，则边长应重复计算，重复几次计算几次。一个由邮局出发去各街道送信最后返回邮局的邮递员遇到的问题就是一个中国邮路问题。,无向图上的中国邮路问题也不难解决。若无向图G是欧拉图，则任一欧拉图都提供了一条最佳邮路。若G不是欧拉图，如前所说，图中的奇顶点数必为偶数。然后，求出任意两个奇顶点之间的最短路径及最短矩离最短路径长度），再解一个奇顶点之间的最小权匹配（或指派问题，注意这里的距离矩阵是对称的）。将各匹配奇点间的最短路径加入G中，就得到了最知路问题的解，我们将在9.5中考察一个这类问题的实例。,在本节中，我们例举了几个较为典型而又时常遇到的P问题。由于事实上存在着无穷多个P问题，而且即使某问题是NP完全的，它的许多特殊条件下的子问题也仍然可以是多项式时间可解的，因而我们不可能对P类作一完整的介绍。如果本章内容能起到抛砖引玉的作用，使读者看到一些P问题所具有的某些特征及构造算法上的某些技巧，那么，我们的目的也就达到了。从上述P问题（包括第八章中的线性规划、运输问题及指派问题）可以看出，它们都可以用某种逐次改进的方法来求解。每次改进中的计算量是多项式界的，改进的次数也是多项式界的。线性规划的单纯形法例外，改进次数可能达到指数次。但即使是线性规划问题，也已经找到了具有这种特性的算法，如椭球算法、卡马卡算法，虽然其结构是相当复杂的，但计算量却是多项式时间的。,最后，我们还想强调几点：,1、许多表面有点相象的问题事实上可能具有完全不同的计算复杂性。这样的例子举不胜举，我们略举一、二，以提醒读者注意。,（1）最短路径问题是P问题，而由一点出发到达每一顶点一次（不必返回原点）的哈密顿路问题及由一顶点出发经所有顶点一次到达另一顶点的最短路径问题流浪的旅行商问题（WTSP）均是NP完全的。这里只增加了每个顶点都要去一次的要求，但问题发生了质的变化，由P问题变成了NP完全问题。,（2）指派问题与TSP也有相似之处，前者求一置换而使目标值最小，后者求一循环置换（不包含子圈）而使目标值最小。前者是P问题，而后者则是NP完全的。,（3）欧拉圈问题求由一顶点出发经且仅经过每边一次回到原顶点的圈，而TSP则求由一顶点出发经且仅经过每个顶点一次返回原顶点的圈。前者是十分容易的P问题，而后者是极其困难的NP完全问题，迄今还没有求解它的较好算法。,（4）线性规划问题、运输问题及指派问题均为P问题，但相应的整数线性规划及01规划均为NP完全的。,（5）无向图中国邮路问题是P问题，而有向图中中国邮路问题则是NP完全的，（容易看出，会解有向图上的某问题必也会解无向图上的相同问题，但反之不真）。,2、求最小的问题是P问题，求最大的问题可以是NP完全的，这样的例子也不少。例如，最短路径问题是P问题，而最长简单路径（不含圈的路径）问题却是NP完全的。如若不然，我们可以利用它的有效算法如下构造出哈密顿问题的有效算：令图G=（V，E）的所有边的权均为1，以一端点为起点求到其余各顶点的最长简单路径。由于简单路径不含圈，所有顶点均不会重复到达，故G有哈密顿路当且仅当存在一起点及一终点，其最长简单路径为|V|1。由于哈密顿路问题是NP 完全的，故最长简单路径问题的有效算法不可能存在，除非P=NP。所以，如果你想设计一个求图上两点间的最长简单路径的有效算法，不管你是多么努力，最终必将以失败告终。又譬如，网络流中的最大流问题是P问题。相应地，最小切割问题也是P问题（它是最大流问题的对偶问题，见线性规划的对偶理论）。但可以证明，最大切割问题却是NP完全的。,总之，在研究离散模型时应当极其小心。一方面，我们必须先搞清问题的计算复杂性，而另一方面，条件的微小改变就有可能将一个P问题转变为NP完全的。当然，相反的转变也完全是可能的。,9.2 关于NP完全性证明的几个例子,上节介绍了几个P问题及求解它们的算法。从某种意义上说，可以认为这些问题已被较好地解决了。然而，在研究离散问题时并非都能遇上这样的好运。正如第八章所讲，存在着大量具有NP完全性的问题，虽然许多人作了巨大的努力，仍未找到任何有效算法。其中的许多问题，例如TSP，甚至经受了两代数学家的顽强攻击，竟然毫无进展。各种迹象使人们来越来越倾向于相信，对这些问题根本不存在有效算法，自1972年Cook发表那篇著名的论文以来，这些问题越来越多地被发现。因此，当我们着手研究一个离散问题时，不得不首先搞清遇到的会不会也是这样一个问题。有时，我们可以从有关书籍或文献中查到它，因为别人早已对它作过研究。例如可查阅和的著作“计算机和难解性”，其中例举了大量NP完全问题。但这类问题事实上有无限多个，很多时候，我们会遇到一些对其计算机复杂性一无所知的问题。这时，假如我们仍要去研究它，首当其冲的问题就是搞清问题的性质，以便保证研究工作沿正确的途径展开。要判定一个离散问题的性质没有一个固定的程式可以沿用（虽然总是用多项式转换的方法），常常要用到较高的技巧，并要求对问题的组合结构有相当的了解。尽管如此，别人的经验对我们仍然是很有用的。本节将再分析一些问题，看看别人是如何判定它们的NP完全性的。,例9.13（独立集问题）给定图G=（V，E），求G的一个最大独立集。,所谓独立集是指V的一个子集，有,例9.14（复盖问题）给定图G=（V，E），求G的顶点的一个最小复盖。,所谓复盖是指V的一个子集C，uC或C至少有一个成立。,对于例9.13和例9.14，我们为叙述方便，采用了图的语言，其实也完全可以将它们表达成其他方式。,定理9.10 独立集问题与点复盖问题都是NP完全的。,证明 称图 为图G的补集，若 与G有相同的顶点集，且（i,j）是 的边当且仅当它不是G的边。显然，求G的独立集即求 的团，由G作出 可在多项式时间内完成，故独立集问题等价于团问题。而团问题是NP完全的（见第八章六个基本NP完全问题），故独立集问题是NP完全的。类似地，容易证明K是G的团当且仅当VK是 的复盖，故点复盖问题也是NP完全的。事实上，对任意 中的边（i,j），有（i,j）不在G中，故i,j不能全在G的团K中，从而i与j中至少有一个在VK中，由边（i,j）的任意性可知，VK中，由边（i,j）的任意性可知，VK 必为 的一个复盖。,前面已经讲过，哈密顿圈问题已被证明是NP完全的，从而可得出TSP是NP完全的，哈密顿问题是NP完全的，进而又可得出有向图上的哈密顿圈、哈密顿路和TSP也是NP完全的，因为用两条具有相反方向的弧来代替每一条边，就可将一个无向图上的问题转化为一个有向图上的问题，从而任一有向图问题的有效算法必能用来求解无向图问题。,例9.15（背包问题）给定一组整数C=c1,cn以及一整数K，问是否存在C的一个子集S，使得。,不难看出，背包问题是NP完全的，因为若取，问题就化成了划分问题。,例9.15之所以被称为背包问题是因为它等价于其优化形式：以K为“背包”的容量，欲将C中的整数装入背包中，使背包中的各数之和尽可能地大（求C的子集S，使 且尽可能大），即要求求解01（线性）规划问题：,St xi0，xi1 xi为整数,例9.16（装箱问题Binpacking）有一批待装箱的物品J=p1,pn，pj的长度为l(pj)。现有一批容量为C的箱子（足够数量），要求找到一种装箱方法，使得所用的箱子数最少。,例9.16是一个一维的装箱问题。例如，我们有一批具有相同长度的钢材，如果想取出几根已知长度的钢料生产某种设备，当然会希望少用几根原始钢材以减少浪费。此时，我们就遇到了一个一维的Binpacking问题。当我们想从购买来的三夹板上锯出n块已知长、宽的板来制作家具时，遇到的是二维Binpacking问题。而当我们真正想把一批已知长、宽、高的物体装入具有相同尺寸的箱子时，又遇到了三维的。下面的定理 告诉我们，即使是一维的 Binpacking问题也是NP完全的，故二维和三维的 Binpacking问题更不可能是P问题（它们也是NP完全的）。,定理9.11（一维）Binpacking问题是NP完全的。,证明：易见，划分问题可转化为Binpacking问题。事实上，取，J=c1,cn可划分为两个相等的集合的充要条件是 它们可装入两只容量为C的箱中。,从某种意义上讲，3划分问题（即分为三个相等子集的问题）也许比2划分问题更难，因为已经找到了求解 2划分问题的一些较好算法（称为伪多项式时间算法）。但对3划分问题不可能存在类似算法，由于本书篇幅有限，不再作详尽的讨论。读者不难发现，Binpacking问题至少不会比3划分问题容易。顺便指出，Binpackin问题中的臬子容量C可以取为1，这样的问题与例9.16是等价的。,例9.17（排序问题Scheduling）拟用m台机器加工n个零件，对零件的加工可以提出各种不同的附加条件，希望排出一个加工顺序（或时间表），使在某种衡量标准下所求得的加工顺序为最佳。,Scheduling是一类应用面极广的离散问题，可以讲它不是一个问题，而是一类问题，因为不同的机器环境、不同的加工要求或不同的衡量标准所得出的模型是不同的。按目前流行的做法，人们常用三个参数，来描述一个特定的排序问题，并记为/排序问题，其中描述机器情况，描述加工零件时的附加要求或附加条件，表示衡量排序好坏的标准。按此方法分类，有人作过统计，认为至少有9000多个不同的排序问题已被或多或少地研究过，其中76%为NP完全的，12%的为P问题，余下的12%目前还未搞清其计算复杂性，但根据种种迹象，大部分可能是NP完全的。有关排序问题，目前已有十多本专著及至少数千篇论文，这里不准备细述专业知识，仅以几个排序问题模型为例，来分析其计算复杂性。,Jm/no wait/Cmax问题是NP完全的。在这一模型中，=Jm，J代表一类被称为Job shop的问题，m表示有m台机器。Job shop意指每一工件要在m台机器的每一台上加工（当不需某台加工时可令加工时间为零），且各工件使用机器的顺序可以不同。=no wiat，表示任一工件在开始第一道工序加工后不允许中间等待，直到它的各道加工均被完成。=Cmax表示排序优劣的评价标准是全系统的加工时间最短，即由第一台机器开始加工起到最后一台机器完工为止的时间跨度最小。第八章例8.8（轧钢问题）就是Jm/no wait/Cmax排序问题的一个实例。在那里已经证明了这一问题等价与TSP，从而是NP完全的。,P2/Cmax问题是NP完全。这里，=P2表示是一个2台机器的平行机问题，即有两台完全相同的机器，每一工件只需在其中任意一台上加工一次即可。=，表示工件加工没有附加要求或条件。=Cmax的解释同上。容易看出，这一问题至少不会比划分问题容易，故不可能是P问题。,在上面的例9.13到例9.17中，我们又列举了几个NP完全问题，它们的NP完全性证明都非常简单。但一般地讲，事情决非如此简单，要将某一NP完全问题多项式时间转化为我们要研究的问题，常常需要用到一些巧妙而又精细的技巧。下面给出一个稍难一些的例子，供有兴趣的读者参考。,讨论1/rj,prmp/排序问题，我们将证明它是NP完全的，这是一个一台机器的排序问题，待加工的工件Tj有一个准备时间rj，rj0，仅当trj时 它才能被加工。prmp表示加工允许中断以便先加工其他工件，未完成的加工可在此后的某一时期补上。各工件的重要程度不同，对每一Ti有一权因子wj。评判排序优劣的标准为各工件完工时间Cj的加权和 越小越好。,这一问题很难直接利用前面提到过的那些NP完全问题来证明其NP完全性。我们将用到下面的已被证明的NP完全问题。,例9.18（三元划分问题）给定3t个正整数的集合a1,a3t，令，问是否能将此集合划分成两两不相交的t个子集，使得每一子集恰含总和为b的三项，（标准型中可设）。,现在，我们来证明，对三元划分问题的每一实例，总可构造出一个等价的1/1/rj,prmp/排序问题的实例，（因此，会解后者就必会解前者）。,对例9.18给出的三元划分问题，作如下的1/rj,prmp/排序问题实例，该例中共有4t1项加工任务。相应数据为,j=1,3t，令rj=0，需加工时间Pj=aj,wj=1j=3t+1,4t1，令rj=(j3t)(b+1)1Pj=1,wj=2,等价性证明可分以下几步完成，有兴趣的读者可以自己完成它：,（1）证明最后t1项工件应尽早加工，否则必将增大，因为它们的wj=2，而前3t项则有 wj=1。这样，这t1项工件应分别在 b,b+1,2b+1,2b+2,(t1)b+12,(t1)b+t1时段内加工。除去加工这t1项工件的时段，整个加工期还留下长度均为b的t个时段。,（2）若三元分划问题有解，可利用每一时段加工一个子集中的工件，此时不必中断任何工件的加工，而若三元分划问题无解，则必有 ZZ是与排序无关的一个常数，而=Z当且仅当三元划分有解。,9.3 分枝定界法与隐枚举法（精确算法）,在上一章中我们已经看到，整数规划、01规划都是NP完全的。事实上，仅对部分变量有非负约束的线性规划（称为混合整数规划）也是NP完全的。这样，一方面不可能找到求解的有效算法，另一方面枚举所有可能情况的办法对规模较大的例子又无法实现。出于实际需要，人们不得不采取一些折中的办法，即以枚举为基础，选用一些减少计算量的技巧或规则，以增大算法的实用效果。前面已经指出，所谓指数算法实际上是指在最坏的情况下可能达指数时间的计算量，它并不排斥在大多