Java编程

不是贪心算法特点

算法设计与分析(二)之动态规划

贪心算法的特点

设计要素:

贪心法适用于组合优化问题。

求解过程是多不判断过程,最终的判断序列对应于问题的最优解。

不是贪心算法特点

依据某种“短视的”贪心选择性质判断,性质好坏决定算法的成败。

贪心法必须进行正确性证明。

证明贪心法不正确的技巧:举反例。

贪心法的优势

:算法简单,时间和空间复杂性低

最优装载问题

问题:

n个集装箱1,2,3,…..,n装上轮船,集装箱i的重量wi,轮船装载重量限制为C,无体积限制。问如何装是的上船的集装箱最多?不妨设每个箱子的重量Wi =C.

该问题是0-1背包问题的子问题,集装箱相当于物品,物品重量是Wi,价值Vi都等于1,轮船载重限制C相当于背包重量限制b。

建模:

设 x1,x2,x3,x4….,xn 表示解向量,Xi=0,1,Xi=0当且仅当第i个集装箱装上船

算法设计

贪心策略:轻者优先

算法设计:

将集装箱排序,使得

W1 =W2 =… =Wn

按照标号从小到大装箱,直到装入下一个箱子将使得集装箱 总重超过轮船装载重量限制,则停止。

正确性证明思路

命题:对装载问题任何规模为n的输入实例,算法得到最优解。

设集装箱从轻到中记为1,2,3…,n

归纳基础:证明对任何只含1个箱子的输入实例,贪心法得到最优解。显然正确

归纳步骤: 证明:假设对于任何n个箱子的输入实例贪心法都能得到最优解,那么对任何n+1个箱子的输入实例贪心法也得到最优解。

小结

装载问题是0-1背包问题的子问题(每件物品重量为1),NP难的问题存在多项式时间可解的子问题

得不到最优解的问题的处理方法

找零钱问题

最小生成树

Prim算法

Kruskal算法

单源最短路径问题及算法

Dijkstra算法

贪心法小结

贪心法适用于组合优化问题

求解过程是多步判断过程,最终的判断序列对应于问题的最优解

判断依据某种“短视的”贪心选择性质,性质的好坏决定了算法的正确性。贪心性质的选择往往依赖于直觉或经验。

贪心法正确性证明方法:

1).直接结算优化函数,贪心法的解恰好取得最优值

2).数学归纳法(对算法步数或者问题规模归纳)

3). 交换论证

证明贪心策略不对:举反例

对于某些不能保证对所有的实例都得到最优解的贪心算法(近似算法),可做参数化分析或者误差分析

贪心法的优势:算法简单,时间和空间复杂性低

几个著名的贪心算法

最小生成树的Prim算法

最小生成树的Kruskal算法

单源最短路的Dijkstra算法

大数据学习交流QQ群:374038693

更多关于hadoop,spark和机器学习,数据结构与算法文章请关注本文公众号:

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注