资源简介

(共18张PPT)
第13课
算法的设计
目录
动态规划算法
01
动态规划算法的应用
02
动态规划算法
01
Part One
【动态规划算法】最优化原理
1951年美国数学家R．Bellman等人，根据一类多阶段问题的特点，把“多阶段决策”问题变换为一系列互相联系的“单阶段问题”，然后逐个加以解决。而且一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。
与此同时，他提出了解决这类问题的“最优化原理”(Principle of optimality)：“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。
这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 \u003C k \u003C n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。
最优化原理是动态规划的基础，任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件。
(1) 问题中的状态必须满足最优化原理；
(2) 问题中的状态必须满足无后效性。所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。
满足条件：
问题求解模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。
动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
(1)划分阶段：
按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
01
02
(2)确定状态和状态变量： 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
03
动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
01
02
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
03
04
动态规划算法的应用
02
动态规划算法的应用：
最长公共子序列(LCS)
最长递增子序列(LIS)
背包问题
用动态规划实现导弹拦截
最大化投资回报问题的实现
矩阵连乘
走金字塔
凸多边形最优三角剖分
双调欧几里得旅行商问题
小结
今天你学到了什么 说一说自己的收获。
练习1
针对机器人画正六边形的问题,设计一个算法。
练习2
练习3
感谢聆听

展开更多......

收起↑