资源描述：
《离散优化模型及算法设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九章离散优化模型及算法设计浙江大学数学建模基地在上一章中,我们介绍了与计算复杂性有关的一些基本概念.人们发现,在离散问题中存在着两个互不相交的类：P类与NP完全类（若P≠NP）。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，P问题可以看成是一类具有良好性质而又较容易求解的问题，而NP完全问题则是固有地难解的。在§8.4中看到，有着广泛应用背景的线性规划问题是一个P问题。这样，作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是P问题。虽然从平均的角度讲，人们似乎更常遇到NP完全问题，但P仍不失为一个十分重要的问题类。一方面，很多P问
2、题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些经常遇到的P问题并给出求解它们的有效算法。一、拟阵问题及贪婪算法在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有的P问题都具有的。例9.1（最小生成树问题——MST）给定一连通图G=（V，E），e，有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有最小总权的生成树。此问题的标准形式为给定一完全图G，其每边赋有一
3、权数，求此完全图的最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗树。树用(U，T)表示，U为树的顶点，T为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明，对于一个连通图G，G的任一生成树必有∣V∣-1条边。求解最小生成树的算法主要依据下面的定理：定理9.1设{（V，T），…（V,T）}为连通图G中的森林，VUV…U11kk12Vk=V。i1,…k,若仅有一个顶点在Vi中的具有最小权的边为（,u），则必有一棵G的最小生成树包含边（,u）。证明：设G的一棵最小生成树（V，T）不含（,u）。将（
4、,u）加入T，由于（V，T）是生成树，TU（,u）中含有过（,u）的唯一的圈。不妨设V，则V，此圈中的点不全由V中的点组成,因此必存在iii''''''圈中的另一边,u,iui。删去边u得到一新的生成树（V，T1），T1=,u，'u须'其总权不超过（V，T）的权,即（V，T）是包含边（,u）的最小生成树。根据定1可以作了如下算法：任选一点1，令V1:1,T:.若V=V，停；否则，找出仅有一个顶点在V中的边里具有最小权的边11（,u），设，将u加入V（,u）加入T。重复上述步骤，直到V=V
5、。11例9.2求图9.1中图G的最小生成树。解：不妨从顶点开始寻找。V11,1标号1，先加入2（因为边权12最小），标号2。再加入标号3。…，每次加入一条一顶点已标244号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找到的最小生成树已用又线标在图9.2中。容易看出算法的计算量为O∣(V)2∣，所以此算法是有效算法，若G具有2O（C）条边，其中n=∣V∣，计算量的界还是不能改进的，因为每条n边至少应被检查一次。由例9.2可以看出，算法执行的每一步均加入一条可以加入的（即不生成圈的）具有最小权的边，而不去考虑它对以后选取的影响
6、，这种算法被称为贪婪算法。例9.3(入树问题)给出一个有向图G=（V，A），对A中的每一条孤e，给出一个权C（e），求A的一个具有最大权（或最小权）的子集B，要求B中任意两条孤都没有公共的终点。考察下面的入树问题实例：例9.4给出有向图G=（V，A）（图9.3），孤上标出的数字为该边的权，求此图具有最大权的入树。解：由于入树不能包含具有公共终点的孤，故对每一顶点只能选取i一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的入孤，可用计算量为O（∣V∣∣E∣）的贪婪法求解，具有最大权的入树为1,2,2,1,2,4,4,5
7、,5,。3类似地，出树问题也可以用贪婪法求解。例9.5(矩阵拟阵问题)给出一个矩阵A，记其n个列向量为e,…，e。mxn1n设对每一列向量en已指定一权C（en）求ii1,,n的一个线性无关的子集，它具有最大的权和。易见，这一问题也可以用贪婪法求解。集合ii1,,n的线性无关的子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用线性代数知识加以证明（见习题1）。例9.6求矩阵A的列向量具有最大权和的独立子集11013541213721A000134510126754*7C(ei)＝84
8、75264解：采用贪婪法
