动态规划ch15.pdfVIP

算法设计与分析 算法设计与分析 算法设计与分析 Design and Analysis of Algorithms Design and Analysis of Algorithms Design and Analysis of Algorithms 主讲人 徐 云 主讲人 徐 云 Fall 2010, USTC , USTC Part 1 Foundation Part 1 Foundation Part 2 Sorting and Order Statistics Part 2 Sorting and Order Statistics Part 3 Data Structure Part 3 Data Structure Part 4 Advanced Design and Analysis Techniques Part 4 Advanced Design and Analysis Techniques chap 15 Dynamic Programming chap 15 Dynamic Programming chap 16 Greedy Algorithms chap 16 Greedy Algorithms chap 17 Amortized Analysis chap 17 Amortized Analysis Part 5 Advanced Data Structures Part 5 Advanced Data Structures Part 6 Graph Algorithms Part 6 Graph Algorithms Part 7 Selected Topics Part 7 Selected Topics Part 8 Supplement Part 8 Supplement 第15章 动态规划 第15章 动态规划 15.1 方法概述 15.1 方法概述 15.2 多段图规划 15.2 多段图规划 15.3 矩阵链乘法 15.3 矩阵链乘法 15.4 最大子段和 15.4 最大子段和 15.5 最长公共子序列 15.5 最长公共子序列 15.6 0-1 背包 15.6 0-1 背包 15.1 方法概述 历史及研究问题 一些术语和概念 最优性原理 方法的基本思想 方法的求解步骤 动态规划法的适用条件 最优性原理判别举例 设计技巧—— 阶段划分和状态表示 存在的问题 2010-10-13 算法设计与分析 4 历史及研究问题 （1） 动态规划(dynamic programming) 是运筹学的一个 分支，20世纪50年代初美国数学家R.E.Bellman等 人在研究多阶段决策过程(multistep decision process) 的优化问题时，提出了著名的最优化原 理 (principle of optimality) ，把多阶段过程转化为 一系列单阶段问题，逐个求解，创立了解决这 类过程优化问题的新方法—动态规划。 多阶段决策问题：求解的问题可以划分为一系 列相互联系的阶段，在每个阶段