算法的设计（第6章贪心法）.pptVIP

第6章 贪心法 简介 最小生成树 单源最短路径 贪心调度 贪心法简介 找零钱问题 10元?3元=7元: 5 + 2 100元?3元=97元: 50 + 20 + 20 + 5 + 2 100元?14元=86元: 50 + 20 + 10 + 5 + 1 没有更优的找钱方案 每次尽可能地选取最大面额的钞票 贪心法简介 找零钱问题 每次尽可能地选取最大面额的钞票 [贪心算法] Algorithm Change(int x) begin let a1 = a2 = a3 = 0; if (x ≥ 5) then a3 ? 1; x ? x ? 5; while (x ≥ 2) do a2 ? a2 + 1; x ? x ? 2; a1 ? x; return (a1, a2, a3); end 贪心法简介 找零钱问题 最优性证明： （1）若x的值为1, 2, 5，那么所需的零钱为1张，这显然是最少的。 （2）否则，所需的钱数至少为2张。算法对3, 4, 6, 7生成的找钱方案分别为2+1, 2+2, 5+1, 5+2，这显然也是最少的。 （3）若x的值为8和9，算法生成的找钱方案分别为5+2+1和5+2+2；而用2张钞票不能找出8元或9元的零钱，因此算法的结果也是最少的。 如果将x的值扩大到100以内，并增加面值为50, 20和10元的钞票，那么使用贪心算法仍然能够得到最优的找钱方案， 即每次尽可能地选取最大面额的零钞。 每次尽可能地选取最大面额的钞票 贪心法简介 贪心算法：在问题求解的过程中采用“贪婪”的策略来构造目标解。 实现起来较为简单 难点通常在于算法的正确性证明 贪心法简介 最优性证明： 【引理6.1】设A*是问题P(A,W)的一个最优解，那么a0总是可以包含在A*中。 【引理6.2】设A*是问题P(A,W)的一个最优解，且a0?A*，那么A*\{a0}也是问题P(A\{a0},W?a0)的一个最优解。 【定理6.1】贪心算法6.2输出最大数量装载问题P(A,W)的一个最优解。 每次尽可能地选取重量最小的物品 最大装载问题 最小生成树 树: 无回路的连通子图 生成树：含图中所有顶点的树 最小生成树: 加权图中权值最小的生成树 最小生成树 最小生成树: 加权图中权值最小的生成树 a b c d e 18 10 28 24 20 16 15 12 a b c d e 10 24 20 15 a b c d e 18 10 28 12 10 a b c d e 18 20 12 穷举法: O(2n) 最小生成树 Prim算法: 每次选取连接V和V?V的权值最小的边 a b c d e 18 10 28 24 20 16 15 12 a b c d e 18 10 15 12 最小生成树 O(n2) Algorithm Prim(V: setint; E: setint?int; w: int[,]) begin let n = |V|, Y = E \ {E[0]}; let V’ = {E[0].a, E[0].b}, E’ = {E[0]}, tw = w[E[0]]; while (|V’| n) do let i = 0; while (i |Y|) do if (Y[i].a?V’ ? Y[i].b?V’) ?? (Y[i].a?V’ ? Y[i].b?V’) break; i ? i + 1; let e = Y[i]; //e为V’和V?V’之间的最小边 E’ ? E’ ? {e}; V’ ? V’ ? {e.a, e.b}; tw ? tw + w[e]; Y ? Y \ {e}; return (E’, tw); end Prim算法: 每次选取连接V和V?V的权值最小的边 最小生成树 最优性证明： （1）权值最小的边e0可以包含在G的最小生成树中。 （2）设T = V′,E′为最小生成树T的一棵子树，e为连接V和V?V′之间的所有边中权值最小的一条，那么e可以包含在最小生成树中。 按数学归纳法，Prim算法的结果是一棵最小生成树。 Prim算法: 每次选取连接V和V?V的权值最小的边 最小生成树 Kruskal算法: 每次选取不产生回路的最小边 a b c d e 18 10 28 24 20 16 15 12 a b c d e 18 10 15 12 最小生成树 Kruskal算法: 每次选取不产生回路的最小边 O(m logm) Algorithm Kruskal(V: setint; E: setint?int; w: