数据结构与算法实习 算法之五:动态规划 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang lat]net. pku.edu.cn http://www.ipk.pku.edu.cn/pkuipk/course/siig/shixi/ 20118 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验教程》 (国家十一五规划教材),高教社2011年1月
数据结构与算法实习 ——算法之五：动态规划 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验教程》 （国家十一五规划教材），高教社2011年1月
引子 Ⅳloyd动态规划算法 自底向上,利用中间结果,迅速构造 ◎最优子结构、重复子结构、无后效性 o搜索中分支定界的特例 o空间换时间 o贪心法是动态规划的特例 ° Huffman树 ● Dijkstra算法 ●Prim算法, Kruskal算法
引子 Floyd动态规划算法 自底向上，利用中间结果，迅速构造 最优子结构、重复子结构、无后效性 搜索中分支定界的特例 空间换时间 贪心法是动态规划的特例 Huffman树 Dijkstra算法 Prim算法，Kruskal算法
内容 o动态规划的概念 o数字三角——递推、递归、备忘录 BestBsT构造 o动态规划与其他算法的比较
内容 动态规划的概念 数字三角——递推、递归、备忘录 BestBST构造 动态规划与其他算法的比较
什么是动态规划 动态规划( dynamic programming)是在上 世纪50年代由美国数学家贝尔曼( Richard Bellman)为研究最优控制问题而提出的 o在计算机科学界,动态规划成为一种通用的算法 设计技术用来求解多阶段决策的最优化问题
什么是动态规划 动态规划（dynamic programming）是在上 世纪50年代由美国数学家贝尔曼（Richard Bellman）为研究最优控制问题而提出的。 在计算机科学界，动态规划成为一种通用的算法 设计技术用来求解多阶段决策的最优化问题
动态规划法原理 动态规划法将待求解的问题分解成若干个子问题(这些子 问题间往往不是相互独立的) 将每个子问题只求解一次并将其解保存在一个表格中 o当需要再次求解此子问题时,只是简单地通过查表获得该 子问题的解,从而避免了大量的重复计算。 原问题 子问题1又子问题 子问题n 填表 匚原间题的解
动态规划法原理 动态规划法将待求解的问题分解成若干个子问题（这些子 问题间往往不是相互独立的） 将每个子问题只求解一次并将其解保存在一个表格中 当需要再次求解此子问题时，只是简单地通过查表获得该 子问题的解，从而避免了大量的重复计算。 原问题 子问题 子问题n 2 子问题1 填表 原问题的解
相关概念 o最优化问题 o多阶段决策 o最优化原理
相关概念 最优化问题 多阶段决策 最优化原理
最优化问题 o求最优解的问题,即“最优化问题” o问题求解 ●有n个输入,它的解由这n个输入的一个子集组成 这个子集必须满足某些事先给定的条件,这些条件 称为约束条件 满足约束条件的解称为问题的可行解 o目标函数 衡量可行解的优劣的标准 o最优解 ●使目标函数取得极值(极大或极小)的可行解
最优化问题 求最优解的问题，即“最优化问题” 问题求解 有n个输入，它的解由这n个输入的一个子集组成 这个子集必须满足某些事先给定的条件，这些条件 称为约束条件 满足约束条件的解称为问题的可行解 目标函数 衡量可行解的优劣的标准 最优解 使目标函数取得极值（极大或极小）的可行解
例如:付款问题 超市的自动柜员机(POS机)要找给顾客数量最 少的现金。例如,要找4元6角现金,如果POS机 送出一大堆硬币,比如46个1角钱,就会招人笑 话了,而最好找2个2元,1个5角和1个1角。 这个问题就是一个最优化问题。约束条件是只能 在现有的面值货币中选择找给顾客,并且总值为 要找的现金。目标函数所找的货币个数,我们要 求这个函数的最小解,这个最小解就是最优解
例如：付款问题 超市的自动柜员机(POS机)要找给顾客数量最 少的现金。例如，要找4元6角现金，如果POS机 送出一大堆硬币，比如46个1角钱，就会招人笑 话了，而最好找2个2元，1个5角和1个1角。 这个问题就是一个最优化问题。约束条件是只能 在现有的面值货币中选择找给顾客，并且总值为 要找的现金。目标函数所找的货币个数，我们要 求这个函数的最小解，这个最小解就是最优解
多阶段决策 对于一个具有n个输入的最优化问题,其求解过程 往往可以划分为若干个阶段,每一个阶段的决策 仅依赖前一个阶段的状态,由决策所采取的动作 使状态发生转移,成为下一阶段决策的依据。 ●阶段:把问题分成几个相互联系的有顺序的几个环节, 这些环节即称为阶段。 ●状态:某一阶段的出发位置称为状态。通俗的说状态 是对问题在某一时刻的进展情况的数学描述。 决策:从某阶段的一个状态演变到下一个阶段某状态的 选择 P1 P2 S ■■■■■■
多阶段决策 对于一个具有n个输入的最优化问题，其求解过程 往往可以划分为若干个阶段，每一个阶段的决策 仅依赖前一个阶段的状态，由决策所采取的动作 使状态发生转移，成为下一阶段决策的依据。 阶段：把问题分成几个相互联系的有顺序的几个环节， 这些环节即称为阶段。 状态：某一阶段的出发位置称为状态。通俗的说状态 是对问题在某一时刻的进展情况的数学描述。 决策：从某阶段的一个状态演变到下一个阶段某状态的 选择。 P1 P2 Pn Sn- 1 S0 S1 S2 Sn
阶段、状态、决策 C1 5 D1 B1K5C2 D2H4 E 3 B28 C38 图中的每个顶点代表一个城市,两个城市间的连 线代表道路,连线上的数值代表道路的长度。从 城市A到达城市E,怎样走路程最短,最短路程的 长度是多少?
阶段、状态、决策 第一 阶段 第二 阶段 第三 阶段 第四 阶段 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 图中的每个顶点代表一个城市，两个城市间的连 线代表道路，连线上的数值代表道路的长度。从 城市A到达城市E，怎样走路程最短，最短路程的 长度是多少？
