[数据结构与算法]2021-09-07

一分钟学会贪心算法思想

和动态规划有所不同的是，贪心算法不是从整体最优上加以考虑，所做的只是某种意义上的局部最优选择。
常见贪心有

1. 活动安排问题
2. 最优装载问题
3. 哈夫曼编码
4. 单源最短路径Dijkstra
5. 最小生成树Prim
6. 最小生成树Kruskal
7. 多机调度问题
   ……
   贪心算法的基本要素
   贪心选择性质
   贪心选择性质是指，所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选并来达到，这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别在动态联划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关了问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖以往所做过的选择，但决不依赖将来所做的选择，也不依赖子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为规模更小的子问题。
   对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每步所做的贪心选择最小终导致问题的整体最优解，通常可以用类似于证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明，通可以过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于，利用该问题的最优子结构性质。
   最优子结构性质
   当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的动性最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题择 中，其最优子结构性质表现为：若A是对于E的活动安排问题包含活动1的一个最优解，则相容活动集合A′=A-{1}是对于E’=(i∈E：si<f1)的活动安排问题的一个最优解。