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

数学建模离散优化模型及算法设计

第9章：某些P问题及其算法

之前,我们介绍了与计算复杂性有关的一些基本概念.人们发现,在离散问题中存在着两个互

不相交的类：P类与NP完全类（若P≠NP）。前者具有求解的有效算法而后者不可能有这

种算法。从这一点上讲，P问题可以看成是一类具有良好性质而又较容易求解的问题，而

01NP完全问题则是固有地难解的。

在§8.4中看到，有着广泛应用背景的线性规划问题是一个P问题。这样，作为线性规划子

问题的运输问题及作为运输问题子问题的指派问题自然更是P问题。虽然从平均的角度讲，

人们似乎更常遇到NP完全问题，但P仍不失为一个十分重要的问题类。一方面，很多P问

题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们

02也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些

经常遇到的P问题并给出求解它们的有效算法。

一、拟阵问题及贪婪算法

在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的

任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有

的P问题都具有的。

例9.1（最小生成树问题——MST）给定一连通图G=（V，E），e，

有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有

最小总权的生成树。

此问题的标准形式为给定一完全图G，其每边赋有一权数，求此完全图的

最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗

树。树用(U，T)表示，U为树的顶点，T为树的边集。不相交的树的集合

被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容

易证明，对于一个连通图G，G的任一生成树必有∣V∣-1条边。

求解最小生成树的算法主要依据下面的定理：

定理9.1设{（V1，T1），…（Vk,Tk）}为连通图G中的森林，V1UV2…U

。若仅有一个顶点在中的具有最小权的边为（），

Vk=Vi1,…k,Vi,u

则必有一棵G的最小生成树包含边（,u）。

证明：设G的一棵最小生成树（V，T）不含（,u）。将（,u）加入T，

由于（V，T）是生成树，TU（,u）中含有过（,u）的唯一的圈。不

妨设，则，此圈中的点不全由中的点组成因此必存在

VVVi,

圈中的另一边ii。删去边得到一新的生成树（，

,u,uV

11iiu

T），T=，须其总权不超过（V，T）的权,即（V，T）

,uu

是包含边（,u）的最小生成树。



根据定可以作了如下算法：任选一点，令

11V1:1,T:.

若V1=V，停；否则，找出仅有一个顶点在V1中的边里具有最小权的边

（），设，将加入（）加入。重复上述步骤，直到。

,uuV1,uTV1=V

例9.2求图9.1中图G的最小生成树。

解：不妨从顶点开始寻找。标号，先加入（因为边权

V11,1121