文档章节

算法---->动态规划(一)

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1442
阅读 55
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

动态规划

多阶段决策问题

问题的活动过程分为若干相互联系的阶段,任一阶段i以后的行为仅依赖于i阶段的过程状态,而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策,这一系列的决策称为多阶段决策过程(multistep decision process) 。

根据这类问题多阶段决策的特性, 提出了解决这类问题的“最优性原理”,把多阶段过程转化为一系列单阶段问题,从而创建了一种新的算法设计方法—动态规划。

最优性原理(Principleof Optimality)

过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么, 其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列

在多阶段决策过程的每一个阶段, 都有多种决策可供选择,但必须从中选取一种。一旦各种阶段的决策选定之后,就构成了一个决策序列。决策序列不同会导致问题结果也不同。

动态规划的目标:  在所有允许选择的决策序列中选取一个会获得问题最优解的决策序列,即最优决策序列。

利用动态规划求解问题的前提

1)  证明问题满足最优性原理

   如果对所求解问题证明满足最优性原理,则说明用动态规划方法有可能解决该问题

2) 获得问题状态的递推关系式

   得各阶段间的递推关系式是解决问题的关键。

动态规划模型的基本要素

阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段,以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示

状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性,即当某阶段的状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关,即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。

描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set ofadmissible states)

决策:当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策(decision) 。

决策组成的序列称为策略(policy)由初始状态x1开始的全过程的策略记作p1,n(x1),即p1,n(x1)={u1(x1),u2(x2),...,un(xn)}。

状态转移方程

在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便完全确定。用状态转移方程(equation ofstate)表示这种演变规律

指标函数(objective function)是衡量过程优劣的数量指标,它是关于策略的数量函数,从阶段k到阶段n的指标函数用Vk,n(xk,pk,n(xk))表示,k=1,2,...,n。

使指标函数Vk,n达到最优值的策略是从k开始的后部子过程的最优策略

动态规划的基本思想:

(1)动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点,必须将问题的过程分成几个相互联系的阶段,恰当选择状态变量,决策变量和定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解。即从边界条件开始,逐段递推寻优,在每一个子问题的求解中,均利用了它前面的子问题的最优化结果,依次进行,最后一个子问题的最优解,就是整个问题的最优解。

(2)在多阶段决策过程中,动态规划方法是既把当前一段和未来各段分开,又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此,每段决策的选取是从全局来考虑的,与该段的最优选择答案一般是不同的。

(3)在求整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段状态的函数,故最优策略所经的各段状态便可逐次变换得到,从而确定最优路线。

最优化决策序列的表示

向前处理法(forwardapproach)

   最优决策序列的表示法启发我们从最后阶段开始,以逐步向前递推的方式, 列出求解前一阶段决策值的递推关系式, 即根据xi+1, … xn的那些最优决策序列来列出求取xi决策值的关系式

向后处理法(backwardapproach)

   从初始阶段开始, 以逐步向后递推的方式, 列出求解后一阶段决策值的递推关系式, 即根据x1, … xi-1的那些最优决策序列来列出求取xi决策值的关系式

动态规划应用举例

多段图

0/1背包问题

每对定点之间的最短路径

可靠性设计

流水线调度问题

货郎担问题

最优二分检索树

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/14/5637098.html

小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
加载中

评论(0)

MIT6.0002 笔记,LECTURE1&2 Optimization

Lecture1&2 Optimization 最优化问题 这是MIT课程MIT60002 Computational thinking and data science 的第一二课,主要内容是最优化,包括贪心算法,暴力算法和动态编程(dynamic programmi...

Li Kang
03/31
0
0
动态规划算法(Dynamic Programming,简称 DP)

动态规划算法(Dynamic Programming,简称 DP) 浅谈动态规划 动态规划算法(Dynamic Programming,简称 DP)似乎是一种很高深莫测的算法,你会在一些面试或算法书籍的高级技巧部分看到相关内...

osc_yj7nerbn
2019/06/29
10
0
动态规划(dynamic programming)(二、最优子问题与重叠子问题,以及与贪心的区别)

一、动态规划基础   虽然我们在(一)中讨论过动态规划的装配线问题,但是究竟什么时候使用动态规划?那么我们就要清楚动态规划方法的最优化问题中的两个要素:最优子结构和重叠子问题。  ...

osc_jjc36t9p
2018/02/18
2
0
解决最优子结构问题的两种方法----动态规划和贪心算法

1、两种重要算法思想: 动态规划,贪心算法 2、动态规划: 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基...

thoresa
2015/05/18
1.3K
0
『嗨威说』算法设计与分析 - PTA 数字三角形 / 最大子段和 / 编辑距离问题(第三章上机实践报告)

本文索引目录: 一、PTA实验报告题1 : 数字三角形   1.1  实践题目   1.2  问题描述   1.3  算法描述   1.4  算法时间及空间复杂度分析 二、PTA实验报告题2 : 最大子段和 ...

osc_jx98daik
04/16
6
0

没有更多内容

加载失败,请刷新页面

加载更多

kafka重要概念与集群重点配置详解

重要概念 broker 一个broker就是一个kafka实例,负责接收、转发、存储消息,kafka集群就是由多个broker组成。 topic kafka的topic是一个逻辑概念,就是对消息分组、分类,便于区分处理不同业...

trayvon
56分钟前
44
0
在树莓派里搭建 Lighttpd 服务器

Lighttpd 像 Ngnix 一样,是被设计运行在低内存,低 CPU 负载的设备上,它们都非常适合在树莓派上运行。 本文将介绍如何在树莓派上运行基本配置的 Lighttpd ,以及如何与 PHP-FRM 一起使用。...

良许Linux
56分钟前
21
0
Service Mesh 高可用在企业级生产中的实践 | 线上直播回顾

Service Mesh Virtual Meetup 是 ServiceMesher 社区和 CNCF 联合主办的线上系列直播。本期为 Service Mesh Virtual Meetup#1 ,邀请了四位来自不同公司的嘉宾,从不同角度展开了 Service Me...

SOFAStack
今天
37
0
word转pdf软件有哪些?word转pdf软件怎么操作?

虽说日常生活中,很多人写报告写策划都依然会使用word程序,但是严格来说,word却并非是唯一常用的办公软件,就比如说pdf,就越来越受年轻人的欢迎了,那么经常用电脑办公的你是否知道,其实...

开源86
今天
48
0
Java创建对象的过程(类实例化)

1.检查类是否被加载。 当虚拟机遇到new指令后,会先去常量池检查有没有该类的符号引用,并且检查这个类有没有进行加载、解析、初始化过,没有就先执行类加载过程。 2.为对象分配内存空间*。 ...

曦鱼violet
今天
26
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部