文档章节

解决最优子结构问题的两种方法----动态规划和贪心算法

t
 thoresa
发布于 2015/05/18 13:39
字数 1108
阅读 824
收藏 0

1、两种重要算法思想: 动态规划,贪心算法

2、动态规划:

  1. 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基本思想:将一个具有最优子结构性质的问题分成若干个子问题,在求解过程中,记录下子问题的结果,存储在一个表格中,使得公共的子问题只需要计算一次。书中给出的基本原理:动态规划将问题分成若干个相互重叠的子问题,递归的求解子问题,保存子问题的解,再将它们的解组合起来,求出原问题的解。

  2. 从基本原理中可以看出动态规划需要满足两个条件,最优子结构和子问题重叠。

  3. 最优子结构:书中定义:问题的最优解由相关子问题的最优解组合而成,一个问题的最优解包含其子问题的最优解。典型的有背包问题和钢条切割我问题。所谓子问题就是一中组合,将一个问题分成许多子问题的集合。某个子问题转化为问题时,所需要的代价是固定的。

  4. 一般这类问题的解题过程:(自己总结)


    1. 画出子问题图(类似于逆拓扑排序的图,子问题必须在问题前面完成)

    2. 用数学表达式构建出问题的最优解和子问题最优解之间的代数表达式

    3. 通常采用自底向上的方法进行递归地求解问题的解,自底下上的含义是从最小的子问题求起。

    4. 保存每一步求出的子问题的最优解

    5. 利用计算出的信息构造一个最优解

3、贪心算法:

  1. 基本原理:从初始状态出发,每步都经过贪心选择,最终得到问题的最优解。

  2. 含义: 将每一步都看成是当前最佳的选择,做到局部最优化,直到无法选择为止。寄希望于局部最优的选择能够导致全局最优解。

  3. 两个实例:最小生成树算法和单源最短路径算法,以及集合覆盖问题的贪心启发式算法。


    1. prim算法:将集合A看成是一棵树,每次选择剩余的节点中与这棵树形成的边的权值最小的点加入到集合A中形成新的树,循坏调用该过程,知道所有的点都已经放入到集合A中。初始时随机选择一个节点放入到集合A中。

    2. kruskal算法:在所有连接森林中两颗不同树的边里面,找到权重最小的边(u,v),并将其加入到集合A中,循环调用该过程,直到所有的点已经放入到集合A中

  4. 贪心选择:当进行选择时,我们直接作在当前问题看来是最优的选择,而不必考虑子问题的解。这与动态规划不同,动态规划当前问题依赖于较小的子问题。而贪心算法中做当前问题最优选择,这样每步之后只需要做一个子问题的解。

  5. 也必须满足最优子结构的性质,即一个问题的最优解包含其子问题的最优解。

  6. 那么,如何区分什么时候使用动态规划,什么时候使用贪心算法呢?


    1. 典型的两个问题,0-1背包和分数背包。两者都具有最优子结构性质,但是贪心算法只能用来求分数背包的问题,而不能用来求0-1背包的问题。即只有分数背包具有贪心选择性。

    2. 我得总结(不一定对):具有贪心选择性的一类问题是:每次做选择时只有性能不同,而代价是一样的。那么这样每次的选择都是最好的,最终会得到最好的结果。

    3. 哈夫曼编码也使用贪心选择算法。每次选择待编码的字符都选择在剩余的字符中出现次数最多的


© 著作权归作者所有

t
粉丝 0
博文 29
码字总数 10639
作品 0
嘉定
私信 提问
分治法,动态规划及贪心算法感悟

分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 1.分治法 分治法(d...

努力的C
2017/10/16
0
0
[转]常用算法:分治,贪心,动态规划

分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 1. 分治法 分治法(...

HongYu
2015/01/05
0
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
2018/05/29
0
0
算法的设计基本方法的理解

算法设计基本方法有什么好处? 了解常见的算法设计方法以及它们之间的区别,有利于构建算法思维的广度,有充分的理论知识。当然,如果算法思维的深度再好的话,将来你见识的算法越多,天下之...

qingliangdexiar
2017/05/31
0
0
JavaScript 动态规划&贪心算法

原文链接 前言 这一章,我们将介绍另外两种常用的算法:动态规划和贪心算法。动态规划常被人比作是递归的逆过程,而贪心算法在很多求优问题上,是不二之选。下面,我们针对这两种算法,展开详...

Checkson
07/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部