算法-贪心法_贪心算法最优子结构

贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。贪心法的典型应用是求解最优化问题，而且对许多问题都能得到整体最优解，即使不能得到整体最优解，通常也是最优解的很好近似。

概述

贪心法的设计思路

贪心法目光短浅，并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优，这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

用贪心法求解的问题一般有两个最重要的性质：最优子结构性质和贪心选择性质。

1）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理，问题的最优子结构性质是该问题可以用动态规划法或贪心法求解的关键特征。

2）贪心选择性质：所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到，贪心法通常以自顶向下的方式作出一系列的贪心选择。确定是否有贪心选择性质

• 通常先考察问题的一个整体最优解，并证明可修改这个最优解，使其从贪心选择开始
• 作出贪心选择后，原问题简化为规模较小的类似子问题
• 用数学归纳法证明，通过每一步贪心选择，最终可得到问题的整体最优解

贪心法的求解过程

贪心法通常用来求解最优化问题，从某一个初始状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数增长最快(最慢)为准则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。

图问题中的贪心法

TSP问题

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，并要求所走的路程最短。

贪心法求解TSP问题的贪心策略有两种

1. 最近邻点策略：从顶点出发，每次选择相邻的同时又是距离最短的。该方案的最终结果难以保证，所以pass。

2. 最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。因此，当从剩余边集E’中选择一条边(u,v)加入解集合S中，应满足以下条件：

   • 边(u,v)是边集E’中代价最小的边
   • 边(u,v)加入解集合S后，S中不产生回路
   • 边(u,v)加入解集合S后，S不产生分枝
     

   这个思路可以解决TSP问题，获取最短边使用堆排序，判断两个顶点是否连通及是否产生分枝，使用并查集，可以将时间性能提高为O(nlog2 n)

TSP问题乐扣上没有相关题目，此处就不做了，不过这个思路其实比动态规划要容易一些，但是在具体的实现上，困难很多。

图着色问题

给定无向连通图G=(V,E)，求图G的最小色数k，使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着色不同。

贪心策略为：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，以此类推。

这种策略和选择顶点进行着色的顺序有很大关系，而且很难确认是最优解，我也不知道为啥作者讲这道题。

最小生成树问题

设G=(V,E)是一个无向连通图，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树。

1. 最近顶点策略：选一个顶点，找出和该顶点相邻的最近的顶点，加入该点后，找出和这两个顶点相邻的最近顶点，不断重复该过程，直到加入完所有顶点。这也叫做Prim算法，时间复杂度为O(n^2)。
   
2. 最短边策略:最短边策略从TE={}开始，每一次贪心选择都是在边集E中选取最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。这也叫Kruska算法，时间复杂度为O(elog2 e)。
   
   这两个算法的证明，其实可以用反证法，如果说不是最优的，那么说明存在一个点到其他各个点的距离要小于当前边，但这个是不存在的，所以说明是最优的。

乐扣的贪心算法系列里，没有图相关的算法，所以这里先不做习题了。

组合问题中的贪心法

背包问题

给定n中物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大？

这个背包问题不是0/1背包问题，因为物品可以部分装入，所以可以使用贪心法，贪心策略为：每次从物品集合中选择单位重量价值最大的物品，单位价值=vi/wi。

1. 1383. 最大的团队表现值 - 困难 代码 这道题我没有解出来，最初的思路有问题。后来看了答案才解出来的。确实是用的贪心算法。解这道题，一定需要想清楚思路，其实这道题的思路从宏观上看是很直白的，另外需要灵活使用go的堆。

活动安排问题

设有n个活动集合E={1,2,……,n}，其中每个活动都要求使用同一资源（如演讲会场），而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si>=fj或者sj>=fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集。

其中合理的贪心策略为：最早结束时间，这样可以使下一个活动尽早开始。

将所有活动按照最早结束时间排序，从头开始选择不相交的活动，便是最终结果。

麻烦的点在于如何证明该贪心策略能够计算出正确结果：

• 整体最优解从贪心选择开始：设E={1,2……,n}为n个活动的集合，且E中的活动按结束时间非减序排列，所以，活动1具有最早的结束时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1。设A是E的子集且是活动安排问题的一个最优解，且A中的活动也按结束时间非减序排列，A中的第一个活动是活动k。若k=1，则A就是以贪心选择开始的最优解；若k>1，则设B=A-{k}+1，即在最优解A中用活动1取代活动k。由于f1<=fk，所以B中的活动也是相容的，且B中活动个数与A中活动个数相同，故B也是最优解。由此可见，总存在以贪心选择开始的最优活动安排方案。
• 作出贪心选择后，原问题简化为规模较小的类似子问题：选择活动1后，原问题简化为对E中所有与活动1相容的活动安排子问题。也就是说，若A是原问题的最优解，则A’是活动安排子问题E’={si>=f1,si属于E}的最优解。如果不然，假设B’是E’的最优解，则B‘比A’包含更多的活动，将活动1加入B‘中将产生E的一个解B，且B比A包含更多的活动，这与A是原问题的最优解相矛盾。因此每一步贪心选择陡降问题简化为一个规模较小的与原问题具有相同形式的子问题。
• 对贪心选择次数应用数学归纳法可证，贪心法求解活动安排问题最终产生原问题的最优解。

1. 1386. 安排电影院座位 - 中等 代码

多机调度问题

设有n个独立的作业{1,2,……,n}，由m台相同的机器{M1,M2,……,Mm}进行加工处理，作业i锁需的处理时间为ti(1<=i<=n)，每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

多机调度问题问题是NP难问题，到目前为止还没有有效的解法。对于这类问题，用贪心法求解有时可以得到较好的近似解。贪心法求解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。

其实看贪心法这一章的时候，一直没明白为什么老师在这章里的很多题目，使用贪心法是无法计算出正确结果的。现在我多少有点明白了，因为本书的关键并不是在于计算出正确结果，而是让我们理解贪心法能做什么、不能做什么、能做到什么程度。真实社会中，可能也不需要最准确的结果，因为一些其他因素可能比结果是否最准确影响更大。

1. 621. 任务调度器 - 中等 代码

总结

本来以为DP的题麻烦，后来发现贪心法其实更麻烦。主要在于使用贪心法需要证明能够取得最优解

1. 从贪心选择开始
2. 简化为规模较小类似子问题
3. 使用归纳法证明能产生最优解

贪心法的证明比动态规划证明更加复杂一些，而且本章中做的习题，没有动态规划法做的更加顺畅。建议大家多多练习一下贪心法。

最后

大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）

我的个人博客为：https://shidawuhen.github.io/

往期文章回顾：

算法

1. 算法学习计划
2. 蛮力法
3. 分治法
4. 减治法
5. 动态规划法
6. 贪心法

技术

1. 微服务之服务框架和注册中心
2. Beego框架使用
3. 浅谈微服务
4. TCP性能优化
5. 限流实现1
6. Redis实现分布式锁
7. Golang源码BUG追查
8. 事务原子性、一致性、持久性的实现原理
9. CDN请求过程详解
10. 记博客服务被压垮的历程
11. 常用缓存技巧
12. 如何高效对接第三方支付
13. Gin框架简洁版
14. InnoDB锁与事务简析

读书笔记

1. 敏捷革命
2. 如何锻炼自己的记忆力
3. 简单的逻辑学-读后感
4. 热风-读后感
5. 论语-读后感

思考

1. 对项目管理的一些看法
2. 对产品经理的一些思考
3. 关于程序员职业发展的思考
4. 关于代码review的思考
5. Markdown编辑器推荐-typora