文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1442
阅读 2
收藏 0
点赞 0
评论 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
游戏与常用的五大算法---上篇

前言: 什么时候,我们之间竟然变得这么生疏 什么时候,我想见到你,却又害怕见到你 什么时候,才能在我身边,告诉我。其实,你一直都在 -----------《仙剑奇侠传》 PS:为了方便大家阅读,个...

loving_forever_
2016/09/15
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) 求解过程是多阶段决策过程,每步处理一个字问题,可用于求解组合优化问题 适用条件:问题要满足优化原则或最优子结构性质...

wenhui12345
2017/11/12
0
0
动态规划算法思想解决找零钱问题

动态规划算法思想解决找零钱问题 前言 关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受...

niaonao
2017/10/16
0
0
分治法,动态规划及贪心算法感悟

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

努力的C
2017/10/16
0
0
diff程序的算法

diff程序很重要,linux中的源代码补丁都是diff作出来的,diff在比较两个文本文件的不同方面很高效,它是基于行的,diff会将两个文件都按照行分成若干部分,然后计算这些行每一行的校验码,之...

晨曦之光
2012/04/10
1K
0
算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy
2017/10/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CentOS “Destination Host Unreachable”问题解决办法

挑战极速安装CentOS时遇到局域网主机不能通信的情况: [root@zjd network-scripts]# ping 8.8.8.8PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.64 bytes from 8.8.8.8: icmp_seq=1 ttl=......

wffger
8分钟前
0
0
CentoOS6.6安装netcat

CentOS下安装netcat 使用zookeeper过程中,需要监控集群状态。在使用四字命令时(echo conf | nc localhost 2181),报出如下错误:-bash: netcat: command not found。 我的系统是CentOS 6....

ghou-靠墙哭
19分钟前
0
0
es6之解构赋值巧用

ES6 允许按照一定模式,从数组、对象等中提取值,对变量进行赋值,这被称为解构赋值。 如何进行解构赋值我这里就不赘述,本篇文章主要是将解构赋值的巧妙使用之处。 1、交互变量的值 常用交互...

秋季长青
24分钟前
0
0
Elasitcsearch High Level Rest Client学习笔记(三)批量api

Bulk Request BulkRequest可以在一起从请求执行批量添加、更新和删除,至少需要添加一个操作 BulkRequest request = new BulkRequest(); //创建BulkRequestrequest.add(new IndexRequest("...

木子SMZ
27分钟前
0
0
mybatis-dynamic sql

OGNL expressions if 判断是否存在值 <select id="findActiveBlogLike" resultType="Blog"> SELECT * FROM BLOG WHERE state = ‘ACTIVE’ <if test="title != null"> AND title like #{tit......

writeademo
35分钟前
0
0
社交系统ThinkSNS+ V1.8.3更新播报

     研发发布版本号:1.8.3   本次版本于2018年7月16日发布   本次发布类型:新增功能、细节调整与优化   社交系统ThinkSNSPlus更新体验:请于官网下载/安装最新版或联系QQ35159...

ThinkSNS账号
38分钟前
0
0
教育思考:选择编程是一场父母和孩子的和解[图]

教育思考:选择编程是一场父母和孩子的和解[图]: 之前有个很热的段子是这样讲的:深夜十点的时候,某小区一女子大声喊叫“什么关系?啊?!到底什么关系?你说!”最后发现原来是一位妈妈陪...

原创小博客
39分钟前
0
0
X64汇编之指令格式解析

最近由于项目组内要做特征码搜索的东西,便于去Hook一些未导出函数,你懂得...于是就闲着学习了一下x86/x64的汇编指令格式。x86的汇编指令格式请参照http://bbs.pediy.com/showthread.php?t...

simpower
42分钟前
0
0
rust 语法概要(只适合不熟悉时快速查阅使用,不适合理解其精髓。未完待续)

注意:本内容只适合快查,不适合理解精髓。精髓请研读 https://kaisery.github.io/trpl-zh-cn/foreword.html 基本数据类型 i8,i16,i32,i64,i128 u8,u16,u32,u64,u128 f32,f64 char bool:true...

捍卫机密
45分钟前
0
0
JS中严格模式和非严格模式

1,使用 严格模式的使用很简单,只有在代码首部加入字符串 "use strict"。必须在首部即首部指其前面没有任何有效js代码除注释,否则无效 2.注意事项 (1)不使用var声明变量严格模式中将不通...

AndyZhouX
45分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部