《算法设计与分析》-贪婪法-教学课件（非AI生成）.pptx

算法设计与分析;第四章基本的算法策略;回顾;4.4贪婪算法;回顾;回顾;回顾;回顾;回顾;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;4.4.1贪婪算法举例;?;4.4.1贪婪算法举例;1.贪心法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策，尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。

;2.该算法适用的问题：

贪婪算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪婪算法的前提是“局部最优策略能导致产生全局最优解”。

该算法的适用范围较小,若应用不当,不能保证求得问题的最佳解。一般情况下通过一些实际的数据例子(当然要有一定的普遍性)，就能从直观上就能判断一个问题是否可以用贪婪算法。更准确的方法是通过数学方法证明问题对贪婪策略的选用性。

;3.该策略下的算法框架：

从问题的某一初始解出发；

while能朝给定总目标前进一步do

利用可行的决策，求出可行解的一个解元素;

由所有解元素组合成问题的一个可行解。;4.贪婪策略选择：

首先贪婪算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的（在一定的标准下），决策一旦作出，就不可再更改。

用贪婪算法只能解决通过局部最优的策略能达到全局最优的问题。

因此一定要注意判断问题是否适合采用贪婪算法策略，找到的解是否一定是问题的最优解。

5.证明方法：（正确）数学归纳法，（错误）举反例;4.4.3可绝对贪婪问题;问题分析：

我们通过实例来认识题目中描述的计算过程。对三个具体的数据3，5，7讨论，可能有以下三种结果：

（3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109

由此可见，先运算小数据得到的是最大值，先运算大数据得到的是最小值。

;下面再以三个数为例证明此题用贪心策略求解的合理性。不妨假设：ab=a+k1c=a+k1+k2，k1,k20，则有以下几种组合计算结果：

1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1

2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1

3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1;下面再以三个数为例证明此题用贪心策略求解的合理性。不妨假设：ab=a+k1c=a+k1+k2，k1,k20，则有以下几种组合计算结果：

1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1

2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1

3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1

证明思路：如果有一串操作其中有一次操作并不是挑最小的两个数，那么你可以构造另一串操作，之前和这串操作相同，从那一次操作起后面全用的挑最小两个数的策略，可以证明这个新操作得到的结果比原来的要大。所以任何一次不挑最大两个都得不到最优解。;下面再以三个数为例证明此题用贪心策略求解的合理性。不妨假设：ab=a+k1c=a+k1+k2，k1,k20，则有以下几种组合计算结果：

1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1

2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1

3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1

证明思路：如果有一串操作其中有一次操作并不是挑最小的两个数，那么你可以构造另一串操作，之前和这串操作相同，从那一次操作起后面全用的挑最小两个数的策略，可以证明这个新操作得到的结果比原来的要大。所以任何一次不挑最小两个都得不到最优解。;下面再以三个数为例证明此题用贪心策