C++与C语言详解：经典贪婪算法及其应用实例

4星 · 超过85%的资源需积分: 10 6 浏览量更新于2024-07-23 收藏 800KB PDF 举报

"《常用算法大全》是一本介绍和探讨各种常见算法的指南，特别侧重于使用C++和C语言来实现这些算法。该书的核心内容围绕着第1章的贪婪算法展开，这是一种直观且在许多问题求解中颇具效果的方法。贪婪算法并不总是能得到全局最优解，但它在特定条件下能提供良好的局部最优解决方案。在最优化问题这一部分，作者定义了最优化问题的基本构成，包括限制条件（约束）和优化函数，目标是找到符合约束条件且优化函数值最大的可行解，即最优解。例如，第1章通过渴婴问题来阐述最优化概念，婴儿面临选择多种饮料以最大化满足感，同时还要确保总容量满足解渴需求。这个问题可以转化为一个线性规划问题，需要找出一组变量xi（代表每种饮料的量），使得总满意度最大化，同时满足总量限制和非负条件。本章涵盖了多个实际问题的应用，如货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题以及最小代价生成树等。这些问题的解决策略是利用贪婪算法的思想，通过一步步做出看似最优的选择，期望最终达到整体最优。然而，贪婪算法并非万能，对于某些问题，特别是那些存在最优子结构和重叠子问题特性的动态规划问题，贪婪算法可能无法找到全局最优解，这时就需要寻找其他算法，如动态规划或者回溯法。《常用算法大全》第一章向读者展示了如何运用贪婪算法解决实际问题，同时也强调了算法设计的艺术性和灵活性。学习者可以通过理解和实践这些算法，提高自己的编程技巧和问题解决能力。后续章节可能会深入讨论其他类型的算法，帮助读者构建更全面的算法工具箱。"

d[j] > d[i] + a[i][j])) {

// 减小 d [ j ]

d[j] = d[i] + a[i][j];

// 将 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 )。

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) 数据结构的选择及复杂性分析

为了按耗费非递减的顺序选择边，可以建立最小堆并根据需要从堆中一条一条地取出各边。当图中有

e 条边时，需花(e) 的时间初始化堆及 O ( l o ge) 的时间来选取每一条边。边的集合 T 与 G 中的顶点一起定义

了一个由至多 n 个连通子图构成的图。用顶点集合来描述每个子图，这些顶点集合没有公共顶点。为了确定

边（ u,v）是否会产生环路，仅需检查 u,v 是否在同一个顶点集中（即处于同一子图）。如果是，则会形成

一个环路；如果不是，则不会产生环路。因此对于顶点集使用两个 F i n d 操作就足够了。当一条边包含在 T

中时，2 个子图将被合并成一个子图，即对两个集合执行 U n i o n 操作。集合的 F i n d 和 U n i o n 操作可利

用 8 . 1 0 . 2 节的树（以及加权规则和路径压缩）来高效地执行。F i n d 操作的次数最多为 2e，Un i o n 操

作的次数最多为 n- 1（若网络是连通的，则刚好是 n- 1 次）。加上树的初始化时间，算法中这部分的复杂

性只比 O (n+e) 稍大一点。

对集合 T 所执行的唯一操作是向 T 中添加一条新边。T 可用数组 t 来实现。添加操作在数组

的一端进行，因为最多可在 T 中加入 n- 1 条边，因此对 T 的操作总时间为 O (n)。

总结上述各个部分的执行时间，可得图 1 3 - 1 3 算法的渐进复杂性为 O (n+el o ge)。

(4) 实现

利用上述数据结构，图 1 - 1 3 可用 C + +代码来实现。首先定义 E d g e N o d e 类（见程序 1 3 - 6 )，它

是最小堆的元素及生成树数组 t 的数据类型。

程序 13-6 Kruskal 算法所需要的数据类型

template

class EdgeNode {

p u b l i c :

operator T() const {return weight;}

p r i v a t e :

T weight;//边的高度

int u, v;//边的端点

} ;

为了更简单地使用 8 . 1 0 . 2 节的查找和合并策略，定义了 U n i o n F i n d 类，它的构造函数是程序 8 - 1

6 的初始化函数，U n i o n 是程序 8 - 1 6 的加权合并函数，F i n d 是程序 8 - 1 7 的路径压缩搜索函数。

为了编写与网络描述无关的代码，还定义了一个新的类 U N e t Wo r k，它包含了应用于无向网络的所有

函数。这个类与 U n d i r e c t e d 类的差别在于 U n d i r e c t e d 类中的函数不要求加权边，而 U N e t Wo r

k 要求边必须带有权值。U N e t Wo r k 中的成员需要利用 N e t w o r k 类中定义的诸如 B e g i n 和 N e x t

Ve r t e x 的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的

边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起构成了 W N e t w o r k 类（见程序 1 3 -

7）。

程序 13-7 WNetwork 类

template

class WNetwork : virtual public Network

{

public :

virtual void First(int i, int& j, T& c)=0;

virtual void Next(int i, int& j, T& c)=0;

} ;

象 B e g i n 和 N e x t Ve r t e x 一样，可在 A d j a c e n c y W D i g r a p h 及 L i n k e d W D i g r a p h 类中

加入函数 F i r s t 与 N e x t。现在 A d j a c e n c y W D i g r a p h 及 L i n k e d W D i g r a p h 类都需要从 W

N e t Wo r k 中派生而来。由于 A d j a c e n c y W G r a p h 类和 L i n k e d W G r a p h 类需要访问 U N e t w

o r k 的成员，所以这两个类还必须从 U N e t Wo r k 中派生而来。U N e t Wo r k : : K r u s k a l 的代码见程

序 1 3 - 8，它要求将 Edges() 定义为 N e t Work 类的虚成员，并且把 U N e t Wo r k 定义为 E d g e N o d e

的友元）。如果没有生成树，函数返回 f a l s e，否则返回 t r u e。注意当返回 true 时，在数组 t 中返回最小

耗费生成树。

程序 13-8 Kr u s k a l 算法的 C + +代码

template

bool UNetwork::Kruskal(EdgeNode t[])

{// 使用 K r u s k a l 算法寻找最小耗费生成树

// 如果不连通则返回 false

// 如果连通，则在 t [ 0 : n - 2 ]中返回最小生成树

int n = Ve r t i c e s ( ) ;

int e = Edges();

/ /设置网络边的数组

剩余87页未读，继续阅读

立杰说

粉丝: 101
资源: 7

C++与C语言详解：经典贪婪算法及其应用实例

常用经典算法及讲解

C语言常用算法（很全，内有详细例子）

ACM常用算法(重要)

c常用算法程序集 源码

python常用算法手册

C语言数据结构常用算法

常用算法程序集.pdf

蓝桥杯题目常用算法模板

常用算法程序集-c语言描述

c/c++常用算法手册

最新资源

c常用算法程序集源码