贪心 动态规划 海量数据处理 北京算法班课件.ppt

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