中国数学建模-编程交流-贪婪算法 - 1(6)

// 将j加入L

if (!p[j]) L.Insert(0,j); p[j] = i;} } }

}

若N o E d g e足够大，使得没有最短路径的长度大于或等于N o E d g e，则最后一个for 循环的i

f条件可简化为：if (d[j] > d[i] + a[i][j])) NoEdge 的值应在能使d[j]+a[i][j]

不会产生溢出的范围内。 2. 复杂性分析

程序1 3 - 5的复杂性是O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有可能在最短路径中。因此这种算法的最小可能时间为O ( e

)。由于使用耗费邻接矩阵来描述图，仅决定哪条边在有向图中就需O ( n2 )的时间。因此，采用这种描述方法的算法需花费O ( n2

)的时间。不过程序1 3 - 5作了优化（常数因子级）。即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e

)（因为只有与i 邻接的顶点的d 值改变）。从L中选择及删除最小距离的顶点所需总时间仍然是O( n2 )。

----------------------------------------------

plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);

2004-5-27 19:41:07

b

等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28

第 10 楼

1.3.6 最小耗费生成树

在例1 - 2及1 - 3中已考察过这个问题。因为具有n

个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是：

K r u s k a l算法，P r i m算法和S o l l i n算法。 1. Kruskal算法 (1) 算法思想

K r u s k a l算法每次选择n-

1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K

r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e

条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

考察图1-12a 中的网络。初始时没有任何边被选择。图13-12b 显示了各节点的当前状态。边（ 1 ,

6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 -

1 2 d所示）。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（

2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（

5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（

6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。

/ /在一个具有n 个顶点的网络中找到一棵最小生成树 令T为所选边的集合，初始化T= 令E 为网络中边的集合

w h i l e(E≠ )&&(| T |≠n- 1 ) { 令(u,v)为E中代价最小的边

E=E- { (u,v) } / /从E中删除边

i f( (u,v)加入T中不会产生环路)将（ u,v）加入T }

i f(| T | = =n-1) T是最小耗费生成树 e l s e 网络不是互连的，不能找到生成树 图13-13 Kruskao算法的伪代码

(2) 正确性证明

利用前述装载问题所用的转化技术可以证明图1 3 - 1 3的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点： 1)

只要存在生成树，K r u s k a l算法总能产生一棵生成树； 2) 产生的生成树具有最小耗费。令G为任意加权无向图（即G是一个无向网络）。从1 2 . 11 .

3节可知当且仅当一个无向图连通时它有生成树。而且在Kruskal

算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E=

和| T |< n- 1。

现在来证明所建立的生成树T具有最小耗费。由于G具有有限棵生成树，所以它至少具有一棵最小生成树。令U为这样的一棵最小生成树，

T与U都刚好有n- 1条边。如果T=U, 则T就具有最小耗费，那么不必再证明下去。因此假设T≠U，令k(k >0)

为在T中而不在U中的边的个数，当然k 也是在U中而不在T中的边的数目。 通过把U变换为T来证明U与T具有相同的耗费，这种转化可在k 步内完成。每一步使在T而不在U中的边的数目刚好减1。而且U的耗费不会因为转化而改变。经过k

步的转化得到的U将与原来的U具有相同的耗费，且转化后U中的边就是T中的边。由此可知， T具有最小耗费。每步转化包括从T中移一条边e

到U中，并从U中移出一条边f。边e 与f 的选取按如下方式进行： 1) 令e 是在T中而不在U中的具有最小耗费的边。由于k >0，这条边肯定存在。

2) 当把e 加入U时，则会形成唯一的一条环路。令f 为这条环路上不在T中的任意一条边。

由于T中不含环路，因此所形成的环路中至少有一条边不在T中。

从e 与f 的选择方法中可以看出， V=U+ {e} -{ f } 是一棵生成树，且T中恰有k-

1条边不在V中出现。现在来证明V的耗费与U的相同。显然，V的耗费等于U的耗费加上边e 的耗费再减去边f 的耗费。若e 的耗费比f

的小，则生成树V的耗费比U的耗费小，这是不可能的。如果e 的耗费高于f，在K r u s k a l算法中f 会在e

之前被考虑。由于f 不在T中，Kruskal 算法在考虑f 能否加入T时已将f 丢弃，因此f 和T中耗费小于或等于f

的边共同形成环路。通过选择e，所有这些边均在U中，因此U肯定含有环路，但是实际上这不可能，因为U是一棵生成树。e 的代价高于f

的假设将会导致矛盾。剩下的唯一的可能是e 与f 具有相同的耗费，由此可知V与U的耗费相同。

(3) 数据结构的选择及复杂性分析

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库中国数学建模-编程交流-贪婪算法 - 1(6)在线全文阅读。