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)放宽约束和增加约束 这个思想是在陈启锋的论文里看到的, 具体内容就是给问题增加一些条件或删除一些条件使 问题变的清晰。



更多相关文章:
动态规划与递推
动态规划与递推_城乡/园林规划_工程科技_专业资料。动态规划与递推——动态规划是最优化算法 动态规划的实质是分治和解决冗余, 因此动态规划也是递归思想的应用 之...
动态规划方法求解线性规划问题
动态规划方法求解下列线性规划问题。 max f ? 2x 1 ? 5x 2 ? x 3 ?2 x 1 ? x 2 ? 4 x 3 ? 10 ? ?x 1 , x 2 , x 3 ? 0 设 xi —...
完整动态规划答案
完整动态规划答案_信息与通信_工程科技_专业资料。优秀论文02 队 备件配置优化问题摘 要 本文讨论了在一定总费用下, 如何配置各部件的备件使系统的可靠性最大 的...
动态规划 分类
动态规划 分类_计算机软件及应用_IT/计算机_专业资料。动态规划分类 1、背包模型 包括 0-1 背包、无限背包、有限背包、有价值背包、小数背包(贪心即可) 等,是极...
有关动态规划的一篇小论文
动态规划 Dynamic Programming by Starfish 【摘要】 本文介绍了动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算 法的具体途径,讨论了动态规划的一些...
动态规划100例
9 资源问题 4 金明的预算方案:加花的动态规划 ... 11 资源问题 5 化工场装箱员 ......
动态规划基本原理
动态规划基本原理近年来, 涉及动态规划的各种竞赛题越来越多, 每一年的 NOI 几乎都至少有一道题目需 要用动态规划的方法来解决; 而竞赛对选手运用动态规划知识的...
动态规划的编程实例
动态规划编程实例 最短路的求解: #include<stdio.h> void main() { int i,j,k,n,h,f; int a[20],b[20][20],c[20],d[20],g[20],e[20][20...
动态规划总结经典题目(经典中的经典)
动态规划总结经典题目(经典中的经典)_计算机软件及应用_IT/计算机_专业资料。经典算法总结(acm为例) 动态规划总结——经典问题总结 本文着重讨论状态是如何表示,以及...
动态规划应用举例
南京航空航天大学 运筹学 课程论文题目:动态规划应用举例 学号: 姓名: 完成日期:2013。5。16 摘要 动态规划是解决最优控制的一种重要方法之一,算法的优点有: (...
更多相关标签:
动态规划算法    动态规划原理及应用    动态规划 背包问题    贪心算法    动态规划算法例题    动态规划法    2038年问题    动态规划 最短路径    

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

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