文档介绍：贪心、动态规划、海量数据处理贪心算法容易想到证明可能困难应用广泛应用MST(prim,Krusal)DijkstraHuffmanLRU缓存替换机制(其实最好的机制是换掉最远不使用)其他问题的启发式——给出近似解贪心选择性质每一步只看“眼前利益”,选择最优解,能导致全局最优解。这是非常“强”的性质一般,证明问题具有这种性质是困难的!框架可选对象全集S已经选择对象的集合T(部分解)一个判断解合法函数isValid(T)一个评价解的函数cost(T),revenue(T)例1找钱问题,目前的钱币系统1,2,5,10,用来换钱是最优的。贪心的证明超过10一定要用10,为什么?有5在,2的个数一定不超过3,因为如果有3个2,1个5,则换成1个10和1个1。没5在,2的个数不超过5。1,2凑超过10的,不如把10换掉。[5..9]一定要用5,为什么?枚举即可。[2..4]一定要用2,枚举即可。注:{1,5,7}凑10就不可以贪心!例2活动安排有若干个活动第i个开始时间和结束时间是[Si,fi),活动之间不能交叠,求最多安排多少个任务?贪心原则:按照结束时间排序,找所有不冲突的。简证:有一个其他的最优解,我们把其中的活动也按照结束时间排序,我们可以把其中的任务一个一个换成我们贪心的任务,而不造成冲突。其他策略的反例最早开始时间,最短任务,最少冲突例3最优装载一艘船容量有限,想装载尽可能多的集装箱,每个集装箱的体积为xi,如何装载,使得装的集装箱个数尽可能多?分析:贪心策略,按照最小的体积优先简证:也是通过“换”,把任意一个解所选的集装箱按体积排序,然后按顺序逐个换为我们贪心策略得到的解所选择的集装箱,占用的总体积不会增大……例4部分背包一个背包容量有限,若干个物体,每种物品有自己的体积和价值,每个物品可以拿一定比例,请让价值总和最大。分析,按照每种物品“性价比”排。同样可以依靠交换,我们可以把任意解中选择的物品逐个换我们按贪心策略得到的解所选的物品,即换位同样体积的“更贵重”的物品,从而导致解更好。例5(独木舟)有n个人,一条独木舟最多可以乘坐两个人且独木舟载重量有限(每条独木舟可载重量相同),每个人体重不一样,求这些人最少需要几条独木舟。分析:最重的人肯定要上船,因此最重的人和另外一个人(船能承受的另外一个尽可能重的人)共乘一条独木舟,问题规模减少2。起源——BellmanFord的书dynamicprogramming(1956)框架有向无环图节点:状态初始状态:起点最终状态:终点集合(可能有多个)边:状态A能转换到状态B,则有一条A->B的边可能有权值问题:求最短(长)路,是否可达