文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1442
阅读 8
收藏 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
广州
私信 提问
解决最优子结构问题的两种方法----动态规划和贪心算法

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

thoresa
2015/05/18
0
0
递归和动态规划

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法,常常使用递归函数,也就是说能调用自身的函数。递归程序的基本特征:它调用自...

LoSingSang
03/12
0
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0
动态规划算法秘籍

本文来自通俗易懂算法入门书《趣学算法》。 动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

rainchxy
2017/12/26
0
0
动态规划法(一)从斐波那契数列谈起

动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,...

jclian91
05/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读取zookeeper上的dubbo注册信息

dubbo有自己的服务监听服务器,incubator-dubbo-ops-develop,github可以下载到,网上也有很多本地部署的例子,就想了下能不能自己监听dubbo的服务,于是写了如下代码。特别注意的是zookeep...

noob_chr
13分钟前
0
0
Java提高班(六)反射和动态代理(JDK Proxy和Cglib)

反射和动态代理放有一定的相关性,但单纯的说动态代理是由反射机制实现的,其实是不够全面不准确的,动态代理是一种功能行为,而它的实现方法有很多。要怎么理解以上这句话,请看下文。 一、...

王磊的博客
33分钟前
1
0
Ext grid 渲染

// 单元格字体颜色渲染function renderer_Meta_useStatus(value, cellmeta, record,rowIndex, columnIndex, store){ var color = ""; if("空闲"==value){ color = "green";......

MoksMo
42分钟前
4
0
log4j2在spring中的配置

<?xml version="1.0" encoding="UTF-8"?><!--日志级别以及优先级排序: OFF > FATAL > ERROR > WARN > INFO > DEBUG > TRACE > ALL --><!--Configuration后面的status,这个用于设置l......

TonyTaotao
48分钟前
3
0
java 中间变量缓存机制(i++,++i)

public class Test { public static void main(String[] args) { int i = 0; i = i ++ ; System.out.println(i); } } 答案是 0 如果是 i = ++......

shzwork
55分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部