动态规划的模型构建.ppt

《动态规划的模型构建.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划的模型构建及其一般优化方法长沙市雅礼中学朱全民NOIP的动态规划试题加分二叉树(2003)—树型动态规划合唱队形(2004)—线型动态规划青蛙过河(2005)—线型动态规划能量项链(2006)—合并类型动态规划金明的预算方案(2006)—资源类型动态规划矩阵取数游戏(2007)—规则类型动态规划传纸条(2008)—规则类型动态规划星球贸易(2009))—线型动态规划乌龟棋(2010))—线型动态规划引例：数字三角形如图所示的数字三角形中从第一行的数字出发每次向左下或右下走一格，直到最后一行要求沿途数字之和最大132410143220动

2、态规划的基本概念阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。决策：从某阶段的一个状态演变到下一个阶段某状态的选择。策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。动态规划的基本概念状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途

3、径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。最优化原理一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。无后效性“过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内

4、涵。举例最短路（不带负权边，带负权边）动态规划的解题步骤划分阶段：注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。选择状态：状态的选择要满足无后效性。确定决策：决策决定着状态的转移，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。写出状态转移方程（包括边界条件和取值范围）：根据问题的性质（求最大/最小），用数学方程描述状态转移的方法和过程编程实现？循环Fori…Forj…(dummy)递归Solve(i,j)Ifsolvedf[i][j]returnf[i][j](dummy)数字三角形求解状态：f(i,j)表示走到第i行j

5、列获得的最大值状态转移方程:f(i,j)=max{f(i-1,j),f(i-1,j+1)}+a[i,j]初始：f(0,0)=0问题1：求最短距离（1）某人要从S1前往SN，其中Si至Si+1有若干种行进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间问最快到达的时间是多少？分析划分阶段、选择状态：到达各个不同的地点作为一个阶段一个阶段里就一个状态用F[i]表示从S1到达Si所需最短的时间写出规划方程（包括边界条件）：F[1]=0F[i]=F[i-1]+Si-1到达Si所需花费的最短时间问题1：求最短距离（2）某人要从S1前往

6、SN，其中Si至Si+1有若干种行进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间，并且如果在一个地点选择切换行进方式，需要额外消耗一定的时间。问最快到达的时间是多少？分析划分阶段、选择状态：使用与上面一样的方案发现不可行，无法解决判定是否需要切换行进方式加一维状态进行表示用f[i][j]表示要从S1到达Si，在Si时使用的出行方式为j，所需最短的时间写出规划方程（包括边界条件）思考？必须在每个地点切换行进方式？“Si至Si+1有若干种行进方式”为“Si至Sj(j>i)有若干种行进方式”？若为任意两点Si至Sj之间都有若干

7、种行进方式？（dijstra算法）若在切换时候需要行进方式时须增加时间？（加一维）中途经过的地点不能超过X个，该如何处理？（加一维或者加上一个数组来保存途径的地点数）若费用为负怎么办？(迭代)两个权值（时间，费用）分析设f(i)表示前i个数的最长不上升序列的长度。则,f(i)=max{f(j)+1},其中j=a[i]这里0

8、序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，…，k-1，有xij=yj。例如