数据结构各章讲稿DS9-1 贪心算法.pptx

第9章算法设计常用方法

9.1贪心算法;贪心算法（greedyalgorithm）又称为贪婪算法

是一种对某些求最优解问题的简单快速的算法设计技术。

用贪心法设计算法的特点是将问题的求解过程分解为一系列选择过程，在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致最好或最优的结果。

贪心算法所做出的选择仅仅是依据当前局部状态，而并不考虑各种可能的整体情况。;贪心算法采用自顶向下，以迭代方式相继做出贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个解。

尽管贪心算法的每一步选择都能保证得到一个局部最优解，但由此产生的全局解有时不一定是最优的，所以，贪心算法并不是对所有问题都能得到整体最优解。;9.1.1活动安排问题;求解思想：优先选择最早结束的相容活动，以便为后续活动留下尽可能多的时间。为此，可先将所有活动按结束时间从小到大排序。

算法9.1：活动安排问题

templateTypenameType

voidGreedySelector(intn,Types[],Typef[],booleanA[]){

intk=1;

A[1]=true;

for(inti=2;i=n;i++){

if(s[i]=f[k]){A[i]=true;k=i;}

elseA[i]=false;

}

}

;例如，假设需要安排10个活动，并且这10个活动按照结束时间的非递减序列排列如下：

;9.1.2贪心算法的设计思想;4）还有一个函数feasible(S)检查是否一个所选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。在活动安排问题中，这个函数用来判断所选出的活动之间是否相容。

5）选择函数select(C)用来从剩余候选对象集合中，根据当前状态选择出最有希望构成问题最优解的对象。在在活动安排问题中，选择函数是从剩余活动中选择最早结束的活动。

6）最后，有一个目标函数给出问题解的值，如在活动安排问题中被选择安排的活动数。

;贪心算法的处理过程可描述如下：;2贪心算法的基本要素;为了判断一个问题是否可以使用贪心算法，要确定该问题是否具有贪心选择性质，也就是说，必须证明每一步所做的贪心选择最终可以产生该问题的全局最优解。

证明过程一般为：

①首先证明第一步贪心选择是包含在问题的一个全局最优解中。

②用数学归纳法证明，通过每一步贪心后最终能够得到问题的全局最优解。

一般来说，在证明了一次贪心选择可以将原问题转化为规模更小的类似的子问题后，实际上就把对正确性的证明转化为了对最优子结构的证明。

;（2）最优子结构性质

贪心算法可行的第二个基本要素是最优子结构。

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。

问题的最优子结构性质是用贪心算法求解该问题的关键要素。;9.1.3贪心算法的应用;算法的主要计算时间在于对物品进行排序，因此该算法的时间复杂度为O(n2)。

如果采用快速排序，总的时间开销可以降至O(nlogn)。

更好的做法是用大顶堆保存这些物品，创建初始堆所花的时间在O(n)内，不过贪心算法每次选择物品后需要花费O(logn)来调整堆，因此最坏情况的时间复杂度是O(nlogn)。但当只需要往背包中装入少量物品的时候，利用堆就会使算法稍快一些。

;2最小生成树;3单源最短路径; 从贪心思想的角度来说，Dijistra算法的基本思想就是，设置顶点集合S，并通过不断做贪心选择来扩充这个集合。开始时，顶点集合S中只包含源点，而C中包含其余顶点，即C=V-S。算法每一次都是从C中选出一个目前由源点可到达的路径最短的顶点，其相应的路径就作为源点到该顶点的最短路径，并将该顶点加入到集合S中。算法结束时，S包含了图G中的所有顶点，此时所有顶点的最短路径全部找到。

;算法9.4：Dijistra贪心算法

founctionDijistra::Dijistra(G){

arraydist[1..n];/*dist是所求得的解*/

S={1};

dist[1]=0;

C={2,3,…,n};/*C是候选对象集合*/

fori=2tondodist[i]=w(1,i);/*初始化解*/

while(C!=Ф){

v=select(C,dist);/*从C中选取dist最小的顶点*/

C=C-{v};

S=S∪{v};

foreachi∈Cdodist[i]