首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
写出设计动态规划算法的主要步骤。
[问答题]
写出设计动态规划算法的主要步骤。
查看答案及解析
添加笔记
求解答(0)
邀请回答
收藏(21)
分享
纠错
3个回答
添加回答
1
Bonjour2019
(1)找出最优解的性质,并刻画其结构特征 (2)递归的定义最优值 (3)以自底向上的方式计算出最优值 (4)根据计算最优值时得到的信息,构造最优解
发表于 2019-06-30 17:25:57
回复(0)
1
Angel_Q
设计一个标准的动态规划算法,通常可按以下几个步骤进行: (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。 (2)选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。 (4)写出规划方程(包括边界条件):动态规达式。 一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算。实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个步骤进行: (1)分析最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。 最优解。 步骤(1)~(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此时,在步骤(3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的信息,快速地构造出一个最优解。
发表于 2018-05-07 20:33:56
回复(0)
1
蜡蜡
①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解;
发表于 2017-07-31 15:42:57
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
动态规划
上传者:
蜡蜡
难度:
3条回答
21收藏
6097浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3692)
来自
华为研发工程师编程题
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
有20000人的就餐需求,现建了一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题