模型与算法(一)：贪心算法
贪心算法（Greedy Algorithm) 简介
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉，极端点就是"鼠目寸光"。}
贪婪法的基本步骤：
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。
事例一：找零钱问题
假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？
这里需要明确的几个点：
1. 货币只有 25 分、10 分、5 分和 1 分四种硬币；
2. 找给客户 41 分钱的硬币；
3. 硬币最少化。
思考，能使用我们今天学到的贪婪算法吗？怎么做？
（回顾一下上文贪婪法的基本步骤，1，2，3）
1.找给顾客sum_money=41分钱，可选择的是25 分、10 分、5 分和 1 分四种硬币。能找25分的，不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3.此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币。
事例二：多人过桥
在漆黑的夜里，甲、乙、丙、丁共四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、10分钟；而如果两人同时过桥，所需要的时间就是走 得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。
这里需要明确的几个点：
1. 一次最多只能通过两个人，过桥时间取两人中的最大值；
2. 只有一个手电筒，过了桥之后需要有人把手电筒再带回来；
3 .时间最小化。
借鉴贪心算法的步骤，我们想到的方案的关键是，让过桥最快的人负责多次来回把手电筒带回，因此，具体方案为：
1. 甲乙过桥，甲（甲过河最快）返回，用时 S1 = 2 + 1 = 3；
2. 甲丙过桥，甲返回，用时 S2 = 5 + 1 =6;
3. 甲丁过桥，用时 S3 = 10
总用时 T = S1 + S2 + S3 = 19
看似解决了问题，实际上却暴露出了贪心算法的不足：每次采用同样逻辑，没有考虑整体。
本题还有另一种方法：让最慢的两个人同时过河（不是最慢的先过河），方案为：
1. 甲乙过桥，甲返回，用时 S1 = 2 + 1 = 3；
2. 丙丁过桥，乙（乙在第一步已经在桥对面）返回，用时 S2 = 10 + 2 =12;
3. 甲乙过桥，用时 S3 = 2
总用时 T = S1 + S2 + S3 = 17
把四人所需要的时间，改变一下分别，是1、4、5、8分钟。
第一种方法：先甲乙过去（4分钟），甲回来（1分钟），甲丙过去（5分钟），甲回来（1分钟），甲丁再过去（8分钟），总共需要19分钟就可以让四个人都过去。
第二种方法：先让甲乙过去（4分钟），甲回来（1分钟），丙丁过去（8分钟），乙回来（4分钟），甲乙再过去（4分钟），总共需要21分钟就可以让四个人都过去。
这一次，两个最慢的人一起过去反而更慢了。
这两次方案的差异：次快的人要不要也传递一次手电筒。
假定四个人过河时间是T1,T2,T3,T4且T1＜T2＜T3＜T4，如何选择过桥方案。
第一种过河方法的总时间为：T2＋T1＋T3＋T1＋T4
第二种过河方法的总时间为：T2＋T1＋T4＋T2＋T2
二者之差为：（T1＋T3）-2T2。
结论：如果（T1＋T3）大于2T2，第二种方法优；如果（T1＋T3）小于2T2，第一种方法优；如果（T1＋T3）等于2T2，两种方法无差异。
两种方法PYTHON代码参考：
def pass_river(array):""":param array: 过河的时间数组:return:"""assert type(array) == listn = len(array)if n <= 2:time = max(array)print("人数不超过2，过河时间为", time)else:# 数组排序array = sorted(array)# 第一种方法：由速度最快的来多次来接time_1 = array[0] * (n - 2) + sum(array[1:])# 第二种方法：由速度最快的两个先过去，第二快的留着那里，速度最快的返回time_2 = array[0] * (n - 3) + array[1] * 2 + sum(array[1:]) - array[-2]print("方法1过河总时间为：", time_1)print("方法2过河总时间为：", time_2)print("最快的过河时间为：", min(time_1, time_2))if __name__ == '__main__':# 过河时间array_river = [1, 2, 5, 10]pass_river(array_river)
问题推广
现在我们把这个问题推广：如果有N（N大于等于4）个旅行者，假设他们有各自所需的过桥时间有快有慢，各不相同。在只有一只手电筒的情况下，要过上述的一条桥，怎样才能找到最快的过桥方案？
现在我们假定，N个人单独过桥的时间分别是T1,T2,T3,……,Tn，且满足T1＜T2＜T3＜…… ＜Tn。
经过分析，要满足最快过桥，合理的安排包括以下几点：
1）让最快的送手电筒的次数尽可能多些；
2）某些方案中，次快的也送电筒也可能会电筒；
3）让慢的过桥次数尽可能少些；
4）最快的两个先过桥，以保证此二人是能来回送电筒的人。
借助上述结论，来逐步分析多人情形。
当N=5人时，第一次先T1、T2两人过桥，T1把电筒送回，没过桥的又变成了T1、T3、T4、T5的4人情形。这个时候，需要比较T1＋T4与2T3的大小吗？
第一种方案，还是选择T1来回送电筒，过桥总时间：为T2＋T3＋T1＋T4＋T1＋T5
第二种方案，让慢的一起走，但因为送回电筒的不是T3，而是更快一点的T2,总过桥时间：T2＋T5＋T2＋T3＋T1＋T2。
两种方案两者之差为T1＋T4－2T2，这里与T3没有关系。
当N=6人时，第一次先T1、T2两人过桥，T1把电筒送回，没过桥的又变成了T1、T3、T4、T5、T6 的5人情形。按照刚才的分析，要比较T1＋T5－2T2的大小。
以此类推，两种方案的差异，只与最快的人、次快的人和次慢的人的单独过桥时间有关，而与其他人的快慢无关。
现在，我们再回顾一下第一个事例问题
现在问题变了，还是需要找给顾客41分钱，现在的货币只有 25 分、20分、10 分、5 分和 1 分四种硬币；该怎么办？
按照贪心算法的三个步骤：
1.41分，局部最优化原则，先找给顾客25分；
2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；
3.最终，找给顾客一个25分，一个10分，一个5分，一个1分，共四枚硬币。
是不是觉得哪里不太对，如果给他2个20分，加一个1分，三枚硬币就可以了呢？
总结：贪心算法的优缺点
优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；
缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。