课程教学目标 针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程中加以介绍。 课程内容安排 本课程的内容分成两大部分：算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识，约占20%，主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法，主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
055得不到最优解的处理方法
Loading...
From the course by Peking University
算法设计与分析 Design and Analysis of Algorithms
35 ratings
From the lesson
贪心法的设计
贪心法是处理组合优化问题的常用算法。通过几个典型例子说明了贪心法的设计思想，同时重点阐述了贪心策略正确性的证明方法。针对某些不能保证对所有的输入都得到最优解的贪心策略讨论了其适用范围。
Meet the Instructors
Wanling QuProfessor
School of EECS, Peking University
这一讲介绍得不到最优解的处理方法。
得不到最优解的处理呢 有两种方法，第一个是输入参数分析，
考虑输入参数在什么取值范围内 使用贪心法可以得到最优解，这是一种分析方法。
第二种分析方法呢就是误差分析，估计贪心法
它实际上是一个近似算法，它可能得到的解不是最优， 我们就来分析它和最优解的误差。
对所有的输入实例，这个误差在最坏的情况下它的上界是什么。
这是它的一个误差分析的方法。
那么这两个呢是通常常用的一些方法。
下面呢我们就用这个找零钱问题为例， 来看一看参数分析。假设有n种零钱，
每一个零钱有一个重量w1到wn， 零钱含有价值，最小的钱的币值是1，
然后V2，一直到Vn，就是这是系统的币值。
需要付的总钱数是y， 这里边不妨假设币值和钱数
都是正整数，问 如何付钱使得所付钱的总重量最轻？
这是问题的描述。下边我们看一个例子，
这里头是4种币值，币值是1，5，14，18，
然后每一个钱币的重量假定都是1， 我们需要找的这个总钱数呢是28，
这是一个实例。问问你怎么样选择付钱的办法，
使得最后这个总重量最轻？实际上就是用的钱的张数最少。
我们看到这就是一个最优解，最优解就是我们选用第三种币值的钱，
28，每一个币值是14，只需要两个就可以了，
其他的钱币币值都不用，这个总重量最后达到2，
这是一个最优解。下边对这个问题建模，
第i种硬币的数量是xi
用这么多个。那么这个是它的目标函数， 这是第i种硬币的个数，
这是第i种硬币的重量，乘起来就是第i种硬币的总重量。
然后我对所有的硬币数求和， 就是所使用的钱币的总重，希望它达到最小。
那么所使用的这些硬币的 价值呢用这个公式来计算，
这是第i种硬币的个数，乘以第i种硬币的单位价值，
这一求和就是使用的钱币的总价值，总价值应该等于总钱数y。
这就是它的约束条件。
这是对问题建模成一个组合优化问题。
对这个问题可以使用动态规划的算法， Fk(y)表示使用前k种零钱，
总钱数为y的时候的最小重量。那么这是它的递推方程，
我们可以看到这个表示第k种零钱使用了Xk个，
这是第k种零钱的产生的重量， Xk乘以单位重量，这是使用的重量。
然后第k种零钱呢产生的币值在这一项，
我们要找的总钱数是y，减掉第k种零钱所占用的钱数，
剩下的这个钱应该用k-1种零钱来继续找零钱。
所以这个是一个动态规划的一个方程。那么第k种零钱
它使用的个数是在下面这个范围里头，
最少的个数是0，最大的个数就是它使用的y除以Vk，下取整，
比如说y等于238，这个Vk是100，
那一除的话就等于2，就是100块钱的只能使用2张。这就是它的最大个数。
这个是它的递推方程。初值就是说我们只使用第一种钱来 找的话，它应该重量是多少。
第一种钱的价值是1，所以y除以v1等于y除1，除以1的话
再取整还是y，所以它用的这个重量就是w1y，这个是初值。
这个是动态规划算法所对应的递推方程。
下边我们考虑一种贪心法， 这个贪心法呢是什么呢？就是说单位价值重量越轻的
要优先， 那么单位重量价值越轻的是谁呢？我们排一个序，
排了序以后最后这一项第n种钱是单位
价值的重量最轻，因此我们 按照这个排序的原则，先选择标号大的钱，
比如说238，那按照人民币系统的话我们就要先选100的，
用两张。38呢应该怎么用呢？先用一个20的，
然后再用一个10的，然后后边再 依次地分配，就是尽量选用
币值大的。那我们这个有重量的限制呢，就是单位价值重量最轻的优先选。
这个是它的贪心法的一个策略。
那么按照贪心法，也可以写出一个方程出来， 使用前k种钱总钱数是y的时候，贪心法的
重量得到的叫Gk(y)， 那么Gk(y)满足这个方程，就是我第k种钱
尽量地用，那用到最大的是多少，是y除以Vk下取整，这多用这么多个，
然后乘以第k种钱的单位重量，这就是第k种钱所产生的重量。
那么还剩下多少零钱需要用k-1 种钱来分配呢？相当于y除以Vk的那个余数，
就是ymodVk，就是y除以Vk的余数，零头， 就像238用100块钱分配完了以后
剩38了，这个38就是它这个余数，这个只能用 更小标号的钱来分配，所以我们考虑把
这个钱数用k-1种钱的，仍旧是贪心法来继续分配。
这是它的公式，然后它的初值呢和动态规划算法一样，
因为当钱的币值是1的时候，所有的算法结果都是一样，
这是贪心法的它的 分配策略。下边我们可以看到那个贪心法
它是不是正确的。先可以肯定只有一种钱或两种钱
贪心法都是最优的。一种钱没有问题， 贪心法的解跟动态规划的这个解
它的初值是一样的。所以贪心法的解就是最优的。
下边我们考虑两种钱，两种钱贪心法来讲是 尽量用第二种钱，x2用得越大，得到的解就越好。
那么是不是这个情况呢？可以证明这个策略是对的。
就是第二种钱用的越多，得到的解最好。
我们考察一下动态规划的那个方程，
这是动态规划的方程，那就是说当这个x2取得最大值，取得这项值的时候，正好是
贪心法的选择。而当它取得这项值的时候， 这个里边的值一定是达到最小。
这是它的，根据这个公式要证明这样一个结果才行。
下边我们来看一下怎么证明。
我们把这个公式在这里头写一下， 这个跟它一样，就是说当x2
是第二种钱的个数，记作x2的时候，它所产生的这个
重量就是这个公式。下面我把第二种钱的数量增加，
增加一个δ，就是我多用一点，看看是不是好一点。
那么我们把这个x2用x2+δ代进来，
这个x2也用x2+δ代进来，那就是这个公式。
所以这个公式也是刚才这个方程，只不过把x2的量 这个是没有增加之前的，这个是增加以后的。
如果增加以后的减掉增加以前的，最后如果证明它是个
不超过0的数，可能是负的，那说明我增加了第二种钱以后，它的重量是减轻的，
那按照这个趋势，我把它增加到最大， 取得x2最大值以后，那重量就最轻了，
那说明贪心法的解就是最优的了。下边我们就来推这两个相减为什么是个负的。
首先我们看到这两个的区别，就是这个是增加了一个δ，
这个是没增加，这个是增加了一个δ，这个是没增加。其他的都是一样的。
下边我们就把这F1的这个表达式用初值的公式代进来，
代进来就是这一项。就是说 这个是代进来的结果，就是第一个
F1，y减掉它，就等于这个里边的这个钱币数 乘以w1，就是这一项。那么
这一项保持不动，把括号拆开，就是这一项。
下边这个方括号的同样处理，把这个第一项也用F1的公式代进来，
然后这一项保持不动。
下边我们就来看看这两个减的以后是什么结果。
这部分是完全一样的，这部分是完全一样的，一减以后，就
抵消掉了。所以减完以后剩的是w1乘以-v2δ，
就是这一项。然后这两项抵消掉以后，剩的是w2δ，就是这一项。
所以减完了以后剩的是这样一项，把这一项的 这个δ提到外面来，里边剩的是这样一个项。
那么δ是正的，没有问题，这里边这一项到底是正是负我们来考察一下。
这个结果是 w1大于等于w2/v2，为什么呢？我们开始排序就是说了，
w1/v1大于等于w2/v2，v1是1， 所以就得到这样一个不等式。把这个不等式
两边去掉分母，那么w1乘以v2大于等于 w2就是这个公式，w1v2大于等于w2。
这个负的这一项大，正的这一项小， 当然这个客户里边是，可能是个负数，
所以整个这个计算的结果是一个小于等于0的数。
这就说明了我第二种钱用的越多，这个重量越轻， 所以贪心法是用到最多了，所以贪心法的解就是一个最优解。
下边我们考虑，假定三种钱会怎么样。
这里有一个定理，对每一个正整数k，
假设对所有的非负整数，就是前k种钱的分配，贪心法的解都是最优的，
和动态规划的解一样。那么 还有一个条件就是存在着p和δ，满足下面这个公式，
这个公式是怎么得到的呢？就是把第k+1种钱的币值， 和k种钱的币值，这两个是输入给的参数，
通过这两个参数把p和δ给算出来， 那么这个δ的要求是要
不超过vk，它是在0和vk之间的这样的一个
数，那么当知道vk+1和vk以后，这个p和δ是可以唯一地被确定下来。
当有了这两个数以后， 我们可以通过下边的命题来做判断。下边一共有3个命题，
第一个命题，贪心法对k+1种钱的分配的解
和动态规划的解一样，那就是说，对k+1种钱来讲，贪心法仍旧是正确的，
得到最优解。这个钱数可以是任意正整数。
第二个对于pvk这个币值，vk是
已知参数，这个p是通过刚才这个公式算出来的这个p，
那么pvk对这个币值，贪心法的解 和动态规划的解用k+1种钱分配，它是一样的。
这是第二个结果。
第三个结果呢，就是是一个不等式， wk+1加上Gk(δ)
小于等于pvk，这是三个命题，
这个定理告诉我们这三个命题是等价的。
那这个命题是什么含义呢？这第一个命题是说的 贪心法对k+1种钱的分配是得到最优解的，是正确的。
那么第二个命题正好是第一个命题的一个特例情况，
就是y等于pvk的情况下，这两个值相等，
那么第一个成立，显然第二个成立。而这个结果告诉我们
这两个是等价的，那就是说当第二个如果不成立的话，第一个也，也不成立。
那么这个就说明 通过这个pvk这个特定的值，它相当于给出了
第一种情况不成立的一个反例。找到这样一个不成立的点，
这是帮助我们找反例的。那么第三个是一个判别条件，
δ的值不大，因为根据这个计算，它不超过它小于vk，它既然小于vk的话，
Gk(δ)的计算很方便的，这样一个小的钱数用贪心法，用
k种钱来分配，看看它用多少张，多少个重量，而这个计算是很方便的，
O(k)个时间就可以做到。那么这个是已知的，
做一次加法，然后这个p的值这已经知道了，p乘以wk做一次乘法，
所以这个不等式的判定非常地方便，它用O(k)的时间就可以判定。
由这个不等式如果不成立的话， 那么第一个条件也不成立，因为这三个命题是等价的。
因此我们可以用它作为判定 贪心法对k+1种钱是不是工作的一个判别条件。
这个是这个命题的含义。我们把它总结一下。
根据条件(1)和(3)的等价性，可以对k 等于3,4到n，依次地利用第(3)个条件
对贪心法是不是得到最优解作出判别， 这是我们的第一个说明。
第二个说明，条件(3)的判别的时间不长， 因为它一次判定只需要O(k)个时间，
如果我们对所有的3,4到n都判定完了，最多用n²时间。
所以在这个时间里就可以判定这个贪心法是不是对所有的
输入，对所有的这个y都得到最优解。
条件(2)是条件(1)的一个特例，
如果条件(2)不成立， 我们就可以找到一个条件(1)不成立的反例，
这是它的应用。下边我们看一个 具体的例子。这是刚才的p和
δ的计算公式，和第三个条件那个判别条件， 我们看一个具体的例子，这是
有四种钱币的一个币值系统， 简单一点，大家的重量都是1，所以最小的重量
就代表你使用钱币的张数最少就可以了。
那么对于第1种钱，或者前两种钱的分配，贪心法都是正确的，这个刚才已经证明过了。
然后我们使用这个定理的判别条件，来看一看
使用前三种钱，我对任意的y进行分配，它是不是正确。
可以证明前三种钱的贪心法对 所有的y都得到最优解，和动态规划的解是一样的。
这个验证的办法就是 用这个公式。那么v3是多少呢？是14，
这个v2是多少呢？v2是5，14等于几倍的5减掉δ， 3倍的5,
三五十五，减掉1就可以了，所以p等于3， 这个δ等于1，这就计算出来了这个p和δ。
然后利用这两个数代到下边这个不等式去验证，
左边是w3加上G2(δ)，δ是1，如果钱币是1的话，用
前两种钱来分配，只能用第一种钱用1个，所以这个值等于1，
前面这w3也等于1，左边等于2，而右边，
右边是什么呢？就是pv2，pv2，v2是1，p，p的值刚才算过了，等于3，
右边是3，正好2小于等于3， 这个不等式是正确的。因此我们可以判定，
由于这个不等式的成立，也就说明 我们用前三种钱来分配，不管这y等于多少，贪心法都得到最优解。
也就是我们的这个结论。
下边接着加入第四种钱继续判定， 加入第四种钱以后，也就是说在前三种
钱的分配，贪心法都得到最优解，我们来验证 对前四种钱会怎么样。这个时候我们还要
计算p和δ，这个v4是18， 这个v3是14，所以这个p应该取2，
这就是28，28减掉10等于18，计算出来p等于2，δ等于10。
然后我们就代入这个不等式来做验证，
那么不等式是w4加上G3(δ)，w4是1，
δ是10，使用前三种钱分配贪心法，那么
标号14的钱不能用，因为10比它还小，所以只能用标号
等于5的这个第二种钱，这个用两张就可以了。所以左边计算出来等于3。
公式的右边是pv3，p等于2，v3等于1，右边等于2，
我们看到这个不等式不成立了，它 左边的值大于右边，在
这个情况下，不等式不成立，说明这个贪心法对于前4种钱的分配会出错，
出错在哪个点上呢？我们刚才说了，条件2
就是判断那个出错点的，就是pv3这个点，v3是多少？是14，
p等于2，所以28，说明在28，钱数等于28的时候，贪心法会出错，
当钱数等于28的时候，用贪心法分配，先用第四种钱，
用一张，然后再用两张第二种钱，一共用三张钱。
但是如果我们不用贪心法，不取这个币值最大的，
直接取第三种钱，用两张就可以了。所以，贪心法不是最优的。这个就找到了
它的反例，就是在28这个钱数的时候它会出错。
把这一章小结一下。贪心策略不一定得到最优解，
在这种情况下可以有两种处理的办法。一个是参数化的分析， 另外一个就是做误差的估计。
那么参数化分析的例子呢，在这一讲里给了一个找零钱问题，
它就通过定理给出了这个条件。这个定理 呢没有证明，但是我们通过实例讲了这个定理的应用。
这是这一讲的主要内容。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
