文档章节

动态规划

cumtm3
 cumtm3
发布于 2017/04/12 21:32
字数 857
阅读 14
收藏 0

    1.基本概念  

     再要两个月就要离开人生的象牙塔,走向工作单位。下面我简单介绍一下动态规划。

     动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就成为动态规划。

     2.基本思想与策略

     基本思想与分治法类似,也是将带求解的问题分为若干子问题,按顺序求解子阶段,前一子问题的解,为后一个子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过策略保留那些有可能达到的最优的局部解,丢弃其他的局部解。依次解决各个子问题,最后一个子问题的解也就是最终的结果。

    由于动态规划解决的问题多数有重叠子问题的特点,为了减少重复的计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的差别是:适合与动态规划求解的问题,经过分解后得到的子问题往往不是相互的,独立的。

3.适用的情况

    适用的情况一般有下面三种特点:

    (1)最优化原理:如果问题的最优解,所包含的子问题的解也是最优解。就称该问题具有最优子结构,即满足最优化原理。

     (2)无后效性。即在某阶段中的状态一旦确定,就不受这种状态以后决策的影响,也就是说,某状态以后的过程不会影响以前的状态,只和当前的状态有关。

     (3)有重叠的子问题。

4.求解的基本步骤

动态规划所处理的问题是一个多阶段决策问题,一般由初始化状态开始,通过对中间段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线。

初始状态->决策1->决策2->....->决策n->最后结果

(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段,阶段的划分,注意一定是有序的或者可排序的,否则问题无法求解。

(2)确定状态和状态的变量:将问题发展到各个阶段时所处于的各个客观情况用不同的状态表示出来。

(3)确定决策并写出状态转移方程:因为决策和状态有着天然的联系,状态转移就是根据上一阶段的状态来决定出来本阶段的状态。所以,如果确定了决策,状态转移方程也就可以写出

(4)寻找边界条件:给出的状态转移方程是一个递推式,需要找到其终止条件。

 

    实际中的应用步骤:

    (1)分析最优解的性质,并得到其结果特征

    (2)递归的定义最优解

    (3)从底向上计算最优值。

 

    

 

© 著作权归作者所有

共有 人打赏支持
下一篇: 回溯法
cumtm3
粉丝 3
博文 32
码字总数 20918
作品 0
徐州
程序员
私信 提问

暂无文章

dockerfile 镜像构建(1)

通用dockerfile 利用已经编译好的.jar 来构建镜像。要构建的目录如下: [root@iZuf61quxhnlk9m2tkx16cZ demo_jar]# docker build -t demo:1 . 运行镜像: [root@iZuf61quxhnlk9m2tkx16cZ de...

Canaan_
15分钟前
0
0
Redis radix tree源码解析

Redis实现了不定长压缩前缀的radix tree,用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。 核心数据结构 raxNode是radix tree的核心数据结构,其结构体...

阿里云云栖社区
18分钟前
4
0
vue import 传入变量

在做动态添加component的时候,传入变量就会报错,出现以下错误信息: vue-router.esm.js?fe87:1921 Error: Cannot find module '@/components/index'. at eval (eval at ./src/components ......

朝如青丝暮成雪
20分钟前
0
0
Flutter开发 Dio拦截器实现token验证过期的功能

前言: 之前分享过在Android中使用Retrofit实现token失效刷新的处理方案,现在Flutter项目也有“token验证过期”的需求,所以接下来我简单总结一下在Flutter项目中如何实现自动刷新token并重...

EmilyWu
21分钟前
5
0
final Map可以修改内容,final 常量不能修改

1.final Map 可以put元素,但是不可以重新赋值 如: final Map map = new HashMap(); map = new HashMap();//不可以 因为栈中变量map引用地址不能修改 2.final str = “aa”; str = "bb";/......

qimh
24分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部