9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

动态规划


动态规划是运筹学的一个分支, 是求解决策过程最优化的数学方法, 在解决实际问题中经常 被使用。 然而它本身或许不是很好理解,这里做一下本人对它的理解。 动态规划三要素:阶段,状态,决策 1、阶段是对整个过程的自然划分 2、状态表示每个阶段开始时过程所处的自然状况 3、当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选 择手段称为决策 找出此类问题的关键: 1、能够用动态规划来求解(这是基本前提) 利用最优性原理来进行判断(这里不做解释) 2、获得状态转移方程(这是重点) 可以看做动态规划求解实际问题的时候, 就是来获得当某阶段的状态和决策为已知, 下阶段 的状态可以通过该阶段来表示出来,而且它们之间满足一个状态转移方程: X[k+1]=T[k](X[k],U[k](X[k])) 3、根据题目要求对决策过程中产生的中间状态进行选取(如 0/1 背包问题中要求不超过重 量上限的情况下获得最大效益, 这里面获得大效益便是一个限制条件, 可以用来在中间决策 中产生的状态中进行选择 这里总结一下一般思路: 拿到多阶段决策最优化问题后, 第一步要判断这个问题是否可以用动态规划解决, 如果不能 就要考虑搜索或贪心了。 当确定问题可以用动态规划后, 就要用下面介绍的方法解决问题了: (1)模型匹配法: 最先考虑的就是这个方法了。 挖掘问题的本质, 如果发现问题是自己熟悉的某个基本的模型, 就直接套用, 但要小心其中的一些小的变动, 现在考题办都是基本模型的变形套用时要小心 条件,三思而后行。这些基本模型在先面的分类中将一一介绍。 (2)三要素法 仔细分析问题尝试着确定动态规划的三要素,不同问题的却定方向不同: 先确定阶段的问题:数塔问题,和走路问题 先确定状态的问题:大多数都是先确定状态的。 先确定决策的问题:背包问题 (3)寻找规律、拼凑法: 这个方法很简单,耐心推几组数据后,看他们的规律,总结规律间的共性,这里一般可以比 较容易的得到状态转移方程,也就是确定下一阶段与前一阶段之间的联系 (4)边界条件法 找到问题的边界条件,然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。 (5)放宽约束和增加约束 这个思想是在陈启锋的论文里看到的, 具体内容就是给问题增加一些条件或删除一些条件使 问题变的清晰。


赞助商链接

更多相关文章:
动态规划与搜索
动态规划与搜索_工作范文_实用文档。动态规划与搜索 动态规划与搜索——动态规划是高效率、高消费算法 同样是解决最优化问题,有的题目我们采用动态规划,而有的题目...
动态规划入门(论文)
动态规划思想入门作者:陈喻(2008 年 10 月 7 日)关键字:动态规划,最优子结构,记忆化搜索 引言 动态规划 (dynamic programming) 是运筹学的一个分支,是求解...
数学模型动态规划
动态规划动态规划(dynamic programming)是运筹学的一个重要分支,它是解决多 阶段决策问题的一种有效的数量化方法.动态规划是由美国学者贝尔曼 (R.Bellman)等人所创立...
动态规划习题
动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非...
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
动态规划的技巧——阶段的划分和状态的表示
动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中, 阶段的划分和状态的表示是非常重要的两步, 这两步会直接影响该问题的计算复杂性, 有时候阶段...
动态规划与静态规划的关系
动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若 干约束条件下的函数极值问题。 两种规划在很多情况下原则上可以相互 ...
动态规划习题答案
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C3 ...
动态规划与网络流
动态规划与网络流——动态规划是易设计易实现的算法 由于图的关系复杂而无序,一般难以呈现阶段特征(除了特殊的图如多 段图--参见例一),因此动态规划在图论中的应...
动态规划例1 求解下列整数规划的最优解
动态规划例1 求解下列整数规划的最优解_研究生入学考试_高等教育_教育专区。天大,考研,运筹学,管理科学与工程例1 求解下列整数规划的最优解: max Z ? 4 x1 ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图