重庆工商大学数学模型与数学实验课件05离散优化模型及算法设计

离散优化模型及算法设计重庆工商大学§9.1某些P问题及其算法在上一章中,我们介绍了与计算复杂性有关的一些基本概念.人们发现,在离散问题中存在着两个互不相交的类：P类与NP完全类（若P≠NP）。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，P问题可以看成是一类具有良好性质而又较容易求解的问题，而NP完全问题则是固有地难解的。在§8.4中看到，有着广泛应用背景的线性规划问题是一个P问题。这样，作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是P问题。虽然从平均的角度讲，人们似乎更常遇到NP完全问题，但P仍不失为一个十分重要的问题类。一方面，很多P问题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些经常遇到的P问题并给出求解它们的有效算法。一、拟阵问题及贪婪算法在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有的P问题都具有的。例9.1（最小生成树问题——MST）给定一连通图G=（V，E），，有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有最小总权的生成树。e此问题的标准形式为给定一完全图G，其每边赋有一权数，求此完全图的最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗树。树用(U，T)表示，U为树的顶点，T为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明，对于一个连通图G，G的任一生成树必有∣V∣-1条边。求解最小生成树的算法主要依据下面的定理：定理9.1设{（V1，T1），…（Vk,Tk）}为连通图G中的森林，V1UV2…UVk=V。…k,若仅有一个顶点在Vi中的具有最小权的边为（,u），则必有一棵G的最小生成树包含边（,u）。,1i根据定1可以作了如下算法：任选一点，令若V1=V，停；否则，找出仅有一个顶点在V1中的边里具有最小权的边（,u），设，将u加入V1（,u）加入T。重复上述步骤，直到V1=V。111:,:.VT证明：设G的一棵最小生成树（V，T）不含（,u）。将（,u）加入T，由于（V，T）是生成树，TU（,u）中含有过（,u）的唯一的圈。不妨设，则，此圈中的点不全由Vi中的点组成,因此必存在圈中的另一边。删去边得到一新的生成树（V，T1），T1=，须其总权不超过（V，T）的权,即（V，T）是包含边（,u）的最小生成树。iVuiV'''',,iiuu''u'',uu例9.2求图9.1中图G的最小生成树。解：不妨从顶点开始寻找。标号1，先加入（因为边权最小），标号2。再加入标号3。…，每次加入一条一顶点已标号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找到的最小生成树已用又线标在图9.2中。111,V212244容易看出算法的计算量为O∣(V)2∣，所以此算法是有效算法，若G具有O（）条边，其中n=∣V∣，计算量的界还是不能改进的，因为每条边至少应被检查一次。2nC由例9.2可以看出，算法执行的每一步均加入一条可以加入的（即不生成圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被称为贪婪算法。例9.3(入树问题)给出一个有向图G=（V，A），对A中的每一条孤e，给出一个权C（e），求A的一个具有最大权（或最小权）的子集B，要求B中任意两条孤都没有公共的终点。考察下面的入树问题实例：例9.4给出有向图G=（V，A）（图9.3），孤上标出的数字为该边的权，求此图具有最大权的入树。解：由于入树不能包含具有公共终点的孤，故对每一顶点只能选取一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的入孤，可用计算量为O（∣V∣∣E∣）的贪婪法求解，具有最大权的入树为。i1221244553,,,,,,,,,类似地，出树问题也可以用贪婪法求解。例9.5(矩阵拟阵问题)给出一个矩阵Amxn，记其n个列向量为e1,…，en。设对每一列向量en已指定一权C（en）求的一个线性无关的子集，它具有最大的权和。1,,iin易见，这一问题也可以用贪婪法求解。集合的线性无关的子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用线性代数知识加以证明（见习题1）。1,,iin例9.6求矩阵A的列向量具有最大权和的独立子集7*45762101543100012731214531011AC(ei)＝8475264解：采用贪婪法，先取权最大的列e1，同时对A作高斯消去，逐次加入线性无关的向量：A的列向量中具有最大权的独立子集为。1354取e6取e4取e3۷۷۷۷۷۷۷۷۷45110205431000334211045310111231110543100033421104531011A4/904/194/90204/514/34/100033421104531011定义9.1(拟阵)设E是一个有限集，γ为E的部分子集构成的封闭系统（即若，则必有）。若M=（E，γ）上的离散优化问题的每一实例均可用贪婪算法求出最优解，则称M为一拟阵。（注：γ被称为独立系统）。,'AA'A现以矩阵拟阵为例，对定义9.1作一说明。对矩阵拟阵的每一实例，E={e1,…en}为矩阵列向量的集合，γ为E的线性无关子集构成的系统，称为独立系统，其元素被称为独立子集。由于E的任一线性无关子集的子集也是E的线性无关子集，故独立系统γ是封闭的。又由于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称为矩阵拟阵。例9.1被称为图拟阵，例9.3被称为划分拟阵。拟阵问题（或称拟阵结构）有一个明显而又本质的特性，其任一极大独立子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向量的所有线性无关极大组均具有相同的向量个数，这就导出了基——即矩阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为|V|-1。对于划分拟阵，孤集被划分成个|V|个子集，每一子集由指向同一顶点的孤组成。显然，任一极大独立集应在每一子集中取一条孤，故其基数为顶点个数。我们不加证明地引入下面的定理，虽然其证明并不十分困难。定理9.2E为一有限集合，为E的部分子集构成的封闭独立系统。以下两个条件均为M=(E,y)构成拟阵（即其上的优化问题可用贪婪法求解）的充分必要条件：（条件2）若I、I‘均为A的两个极大独立集，则|I|=|I’|。AE（条件1）若I、I‘|I||I’|，则必可找到一个元素e，使得（注：|·|表示元素个数）'IIe,二、两分图匹配问题与增广路算法在上一小节中我们已经看到，有些P问题可以用极为简单的贪婪法求解。但对绝大多数的P问题来说，这一结果并不成立，只能根据其本身的结构，去寻找求解它的独特算法。下面，我们将介绍几个这样的P问题。例9.7（婚姻问题）在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为A、B、C，三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她们的喜欢程度而定：问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。7412810272653zyxCBA例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）中的匹配已是最大匹配。本例再次表明两分图匹配问题不是拟阵问题（即使是不加权的），因为其极大独立集中的无素个数可以不同。33424311,,4iui定理9.3M是图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）上的流量