贪心算法解决的问题-数据结构与算法(blog版)

在数据结构中，很多问题是用贪心算法的思路来解决的。

1.最小通信网问题

对许多问题，贪心算法能产生整体最优解，比如第6章中的最小通信网问题。在n个城市之间建立通信网络，则连通n个城市只需要n-1条线路，如何构造一个造价最低的通信网络呢？

在这个问题中，可以用连通图表示n个城市及n个城市之间可能设置的通信线路，其中顶点表示城市，边表示两城市之间的通信线路，边上的权值表示线路造价预算。连通n个顶点最少需要n-1条边，这n个顶点和n-1条边构成图的一棵生成树，一棵生成树就是一个通信网络。要建造一个造价最低又能连通的通信网络，就是构造图的一棵最小生成树。这里用贪心算法的思路重新看一下该问题是如何解决的。

分析最小通信网问题是否具有适用贪心算法解决问题的两个特征。

（1）贪心选择性质，即所求问题的整体最优解可以通过一系列局部最优选择获得。要找最小通信网即求图的最小生成树，可以从一个顶点出发逐步构造这棵总代价最小的最小生成树。从任意顶点u0出发，做局部最优选择，即找与u0连接的最短的带权边，将其加入最小生成树中，连同该边的另一个端点也加入最小生成树中；接着再做局部最优选择，还是找能与当前部分最小生成树中顶点相连的最短边，找到后将其边及其顶点加入最小生成树中，……依次按照局部最优选择不断地加入边和顶点，最后加入了n-1条边后也加入了n-1个顶点，最小生成树集合中就有了n个顶点和n-1条能连通这n个顶点的边，最小生成树也就构造完成了。这正好是Prim算法解决问题的思路。

（2）最优子结构性质，即问题的最优解包含其子问题的最优解。这个也很好理解，在利用Prim算法构造最小生成树的过程中，每次局部最优选择得到的部分最小生成树都是子问题（包含当前部分顶点和边的子图）的最小生成树，即问题的最优解包含子问题的最优解。

最小通信网问题满足贪心算法解决问题的两条特征，所以可以用贪心算法解决。参看上面特征（1）进行的贪心选择，按照这种贪心选择来构造最小生成树的方法就是第6章中介绍的Prim算法。用Prim算法，从第一个顶点出发，将其他顶点逐渐地加进最小生成树中，算法步骤如下。

设G=(V,E)是连通图，构造的最小生成树为T=(U,TE)，求T的Prim算法描述如下。

步骤1：初始化U={u0}，TE={ }，u0为任意顶点。(www.xing528.com)

步骤2：在所有u∈U，v∈V-U的边(u,v)∈E中，找一条最短（权最小）的边(ui,vi)，将该边并入最小生成树边集合TE，即TE+{(ui,vi)}⇒TE，边的另一个端点并入最小生成树顶点集合U，即{vi}+U⇒U。

步骤3：如果U=V，则算法结束；否则重复步骤2。

当最小生成树集合中已加入了n个顶点和n-1条能连通这n个顶点的边，最小生成树也就构造完成了。

2.单源最短路径问题

第6章的单源最短路径问题也是通过贪心选择得到的最优解。分析该问题是否具有适用贪心算法解决问题的两个特征。

（1） 贪心选择性质，即所求问题的整体最优解可以通过一系列局部最优选择获得。要找单源最短路径，即要从图的一个顶点出发逐步求得各条最短路径。那么贪心选择就是首先求得看来最短的那条路径，也就是从所有最短路径中最最短的路径先求得，然后是次最短的路径，依次到最后一条最短路径的求得。通过这样的贪心选择，最终可以得到从源点到所有顶点的最短路径。这正好是Dijkstra算法的解题思路。

（2） 最优子结构性质，即问题的最优解包含其子问题的最优解。这个也很好理解，在利用Dijkstra算法构造最短路径的过程中，每次局部最优选择得到的部分最短路径都是子问题（包含当前部分顶点和边的子图）的最短路径，即问题的最优解包含子问题的最优解。

在Dijkstra算法中找从一个源点出发到图中其他顶点的最短路径，是按照路径长度递增的顺序得到这些最短路径的。从顶点v0出发，做局部最优选择，即找到与v0连接的最短的带权边，将其加入已求得最短路径集合中；接着再做局部最优选择，找到v0与剩余顶点的最短路径，此时最短路径可以是直接连接的直达边，也可以经过已求得最短路径顶点中转，找到后将顶点及边加入已求得最短路径集合中，……依次按照局部最优选择不断地加入边和顶点，最后加入了n-1个顶点后，所有的最短路径也就求出来了。

除了上述两个问题外，还有很多问题都可以用贪心算法解决，如汽车加油问题、最优装载问题等。