所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到,即贪心选择来达到。这是贪心算法可行的第一个基本要素.也是贪心算法与动态规划算法的主要区别:
动态规划算法:每步所做出的选样往往依赖于相关子问题的解,因而只有在解出相关子问题后.才能做出选择。
贪心算法:仅在当前状态下做出最好选样,即局部最优选则。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做出的贪心选则可以依赖于以往做过的选则,但决不依赖于将来所做的选样,也不依赖于子问题的解。
动态规划:是自底向上的方法解各子问题;
贪心算法:是自顶向下的方法。每做出一次贪心选择就将所求问题简化为规模更小的子问题.
使用贪心法的难点在于:证明所设计的算法确实能够正确解决所求解的问题。即对于一个具体的问题,必须证明每一步所做出的贪心选择最终导致问题的整体最优解。
首先,考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。做出贪心选择后.原问题简化为规模更小的类似子问题。然后,用数学归纳法证明、通过每一步做贪心选择.最终可得到问题的整体最优解。
其中,证明贪心选择后的问题简化为规模最小的类似子问题的关键在于利用该问题的最优子结构性质。
最优子结构性质: 当一个问题的最优解包含其子问题的最优解时,
称此问题具有最优子结构性质。
贪心算法和动态规划算法都要求问题具有最优子结构性质,这是两类算法的一个共同点。但是都具有最优子结构的问题该选则贪心法还是动态规划算法求解?是否能用动态规划法的也能用贪心算法解?
背包问题:
给定n种物品{u1,u2, ,un}和一个背包,物品i的体积为si,价值为vi。已经知道背包的承重量为C。
第八章 贪心算法 8.1 8.2 8.3 8.4 8. 5 引言 最短路径问题 最小耗费生成树(Kruskal算法) 最小耗费生成树(Prim算法) 文件压缩 8.1 引言● 贪心算法...
第八章 贪心算法第十讲:黄丽韶 ly_sa@qq.com 1 ? 贪心算法的概念。 目 录 ? 贪心算法的基本要素 ① 最优子结构性质 ② 贪心选择性质 ? 通过应用范例...
第八章 贪心算法_物理_自然科学_专业资料。第三部分 最先割技术第八章 贪心算法 第九章 图的遍历 本章采用知识发明的第三条线,即 “方法——应用”为主线...
8第八章 贪心算法 51页 7下载券 第8章 贪心算法 38页 免费 第8章 贪心...贪心算法 ---总是作出现在看来最好的选择。 顾名思义,贪心算法总是作出在当前...
第8章 贪心算法 48页 免费 第八章贪心算法 47页 1下载券 第八章_贪心...第8讲 贪心算法 1 所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来...
如果这个无法证 明,贪心算法所得的解不是最优解,一般只是较优 解(较优解可为搜索剪枝提供方便)。 下面是贪心算法最经典的例子:部分背包问题。 (下一章会讲到...
第四章 贪心算法 2012-5-27 计算机算法设计与分析 1 贪心算法的特点 ? 贪心算法总是作出在当前来看是最好的选择。 ? 就是说,贪心算法并不从整体最优上来...
实验四 贪心算法 实验四 贪心算法(一) 实验目的 、实验目的通过编程实现有关的... 第4章贪心算法 98页 1下载券 贪心与归纳算法 47页 1下载券...
贪心算法_工学_高等教育_教育专区。贪心算法主讲人:张云聪 目录什么是贪心算法... 第4章贪心算法 98页 1下载券 贪心与归纳算法 47页 1下载券...
热门文档