下载文档原格式
算法分析与设计课程设计动态规划一、课程目标知识目标：1. 理解动态规划的基本概念、原理和应用场景；2. 学会运用动态规划方法解决实际问题，如背包问题、最长公共子序列等；3. 掌握动态规划与其他算法（如贪心、分治等）的区别和联系；4. 了解动态规划在实际应用中的优化方法及策略。
技能目标：1. 能够运用动态规划思想分析和解决具体问题，提高编程实现能力；2. 培养逻辑思维能力和问题解决能力，通过案例分析和实践，掌握动态规划的核心技巧；3. 学会运用数学知识对动态规划问题进行建模和求解。
情感态度价值观目标：1. 培养学生对算法分析与设计的学习兴趣，激发学习动力；2. 培养学生的团队合作精神，学会与他人共同解决问题；3. 增强学生对我国在计算机科学领域取得成就的自豪感，培养创新意识和爱国情怀。
课程性质：本课程属于算法分析与设计领域，旨在帮助学生掌握动态规划的基本原理和方法，提高解决实际问题的能力。
学生特点：学生已具备一定的编程基础和算法知识，具有一定的逻辑思维能力和数学基础。
教学要求：注重理论与实践相结合，通过案例分析、实践操作和课后练习，使学生能够熟练掌握动态规划方法，并应用于实际问题解决。
同时，关注学生个体差异，因材施教，提高教学质量。
二、教学内容1. 动态规划基本概念：包括动态规划的定义、特点和应用场景，以及与分治、贪心算法的对比分析。
教材章节：第3章 动态规划基础2. 动态规划核心要素：状态、状态转移方程、边界条件和最优子结构。
教材章节：第3章 动态规划基础3. 典型动态规划问题：a. 背包问题：0-1背包、完全背包、多重背包等；b. 最长公共子序列、最长公共子串；c. 最短路径问题：Dijkstra算法、Floyd算法。
教材章节：第4章 动态规划典型问题4. 动态规划优化方法：记忆化搜索、自底向上与自顶向下、状态压缩等。
教材章节：第5章 动态规划优化方法5. 实际应用案例分析：介绍动态规划在计算机科学、运筹学等领域的应用案例，提高学生实际应用能力。
动态规划xx年xx月xx日CATALOGUE目录•动态规划算法简介•动态规划的基本原理•常见动态规划问题分析•动态规划算法优化•动态规划在实际应用中的实例•总结与展望01动态规划算法简介动态规划是一种通过将问题分解为相互重叠的子问题来解决问题的方法动态规划适合用于最优化决策序列，具有重叠子问题和最优子结构两个特征1 2 3动态规划的核心思想是记忆已经求解过的子问题的解，避免了重复计算动态规划通常用于最优化问题，可以得出全局最优解动态规划通常是基于自底向上的思路进行实现动态规划的应用场景最短路径问题如Floyd算法、Dijkstra算法等资源分配问题如背包问题、装箱问题、货郎担问题等序列比对问题如Smith-Waterman算法、Genetic Code算法等控制领域如最优控制、预测控制等计算机视觉领域如光流计算、立体视觉匹配等02动态规划的基本原理03自底向上的设计方法可以节省存储空间，减少重复计算，提高算法效率。
动态规划的自底向上设计方法01动态规划的自底向上设计方法是一种通过将问题分解为子问题，并从简单子问题求解逐步设计复杂问题的策略。
02在自底向上的设计过程中，首先解决基本子问题，并利用这些解来解决更大规模的问题，逐步构建出原问题的最优解。
动态规划的递推关系式是算法的核心，它通过将问题分解为子问题，将问题的解表示为子问题的解的组合。
递推关系式通常是一个数学公式，它根据子问题的解来推导出更大规模问题的解。
在递推关系式中，每个子问题的解都会被存储起来，以便后续使用。
动态规划的递推关系式动态规划的边界条件在动态规划中，每个子问题都有一个起始点和终止点，这些点就是边界条件。
边界条件确定了问题的起始状态和终止状态，使得算法可以正确地求解问题。
动态规划的边界条件是算法中非常重要的一个概念，它规定了问题的边界情况。
03常见动态规划问题分析Dijkstra算法、Floyd-Warshall算法、Bellman-Ford 算法总结词最短路径问题是在图中找到从起点到终点的最短路径，有多种算法实现，如Dijkstra算法、Floyd-Warshall 算法和Bellman-Ford算法等。
1算法设计与分析第3章动态规划(2)2理解动态规划算法的概念。
掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。
（1）找出最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
3通过应用范例学习动态规划算法设计策略。
（1）矩阵连乘问题；（2）最长公共子序列；（3）凸多边形最优三角剖分；（4）0/1背包问题；（5）最优二叉搜索树。
4应用Catalan 数多边形三角剖分是数字城市研究许多工作的前提城市景观三维重建中的三角剖分算法基于图像特征和三角剖分的水印算法基于三角剖分的小脑模型在增强学习中的应用 传感网中的动态Delauanay 三角剖分算法 ……5多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T 。
输入:给定凸多边形P ，以及定义在由多边形的边和弦组成的三角形上的权函数w 。
输出:要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
6用多边形顶点的逆时针序列表示凸多边形，即P={v 0,v 1,…,v n-1}表示具有n 条边的凸多边形。
若v i 与v j 是多边形上不相邻的2个顶点，则线段v i v j 称为多边形的一条弦。
弦将多边形分割成2个多边形{v i ,v i+1,…,v j }和{v j ,v j+1,…v i }。
7一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。
叶结点: 表达式中一个原子例如，完全加括号的矩阵连乘积((A 1(A 2A 3))(A 4(A 5A 6)))相应的语法树为 叶结点: 一个矩阵矩阵连乘积A[i+1:j]对应于三角剖分中的一条弦89最优三角剖分问题 输入：多边形P 和代价函数W 输出：求P 的三角剖分T ，使得代价Σs ∈ST W(s)最小，其中ST 是T 所对应的三角形集合P={v,v,…,v}的最优三角步骤11120-1背包问题是一类经典的组合优化问题 对0-1背包问题的研究可以广泛运用于资源分配、投资决策、货物装载等方面。
1
算法设计与分析
第3章动态规划
(2)
2
理解动态规划算法的概念。
掌握动态规划算法的基本要素
（1）最优子结构性质
（2）重叠子问题性质
掌握设计动态规划算法的步骤。
（1）找出最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
3
通过应用范例学习动态规划算法设计策略。
（1）矩阵连乘问题；
（2）最长公共子序列；
（3）凸多边形最优三角剖分；
（4）0/1背包问题；
（5）最优二叉搜索树。
4
应用
Catalan 数
多边形三角剖分是数字城市研究许多工作的前提
城市景观三维重建中的三角剖分算法
基于图像特征和三角剖分的水印算法
基于三角剖分的小脑模型在增强学习中的应用 传感网中的动态Delauanay 三角剖分算法 ……
5
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T 。
输入:给定凸多边形P ，以及定义在由多边形的边和弦组成的三角形上的权函数w 。
输出:要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和
为最小。
6
用多边形顶点的逆时针序列表示凸多边形，即P={v 0,v 1,…,v n-1}表示具有n 条边的凸多边形。
若v i 与v j 是多边形上不相邻的2个顶点，则线段v i v j 称为多边形的一条弦。
弦将多边形分割成2个多边形{v i ,v i+1,…,v j }和{v j ,v j+1,…v i }。
7
一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。
叶结点: 表达式中一个原子
例如，完全加括号的矩阵连乘积((A 1(A 2A 3))(A 4(A 5A 6)))相应的语法树为 叶结点: 一个矩阵
矩阵连乘积A[i+1:j]对应于三角剖分中的一条弦
8
9
最优三角剖分问题 输入：多边形P 和代价函数W 输出：求P 的三角剖分T ，使得代价Σs ∈ST W(s)最小，其中ST 是T 所对应的三角形集合
P={v,v,…,v}的最优三角
步骤
11
12
0-1背包问题是一类经典的组合优化问题 对0-1背包问题的研究可以广泛运用于资源分配、投资决策、货物装载等方面。
处理机和数据库在分布式计算机系统上的分配问题
项目选择的货物装载问题 削减库存问题等
13
研究
在量子计算机上求解0/1背包问题 计算机学报，中国科学技术大学计算机科学与技术系国家高性能计算中心，1999，12：1314～1316 二次背包问题的一种快速解法 计算机学报，国防科学技术大学计算机学院长沙2004，9：1162 ～1169
多维背包问题的一个蚁群优化算法
计算机学报，哈尔滨工业大学计算机科学与技术学院，2008，5：810 ～819
14
给定n 种物品和一背包。
物品i 的重量是w i ，其价值为v i ，背包的容量为C 。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
每种物品要么装入，要么不装入 不能装入多次，也不能装入部分9输入：C>0, w i >0, v i >0, 1≤i≤n 9输出：(x 1, x 2, …, x n ), x i ∈{0, 1}, 满足
{}n
i x i ≤≤∈1,1,0
15
0-1背包问题－①最优子结构性质 0-1背包问题具有最优子结构性质 设是所给问题的一个最优解,
则是下面相应子问题的一个最优解: 反证法证明
),...,(2,1n y y y )y ,...,y (n 2⎪⎩⎪⎨⎧≤≤∈−≤∑
∑==n i 2},1,0{x y w c x w x
v max i n
2i 11i i n
2i i
i
0-1
0-1
18
例
n =5, c=10, w={2,2,6,5,4}, v={6,3,5,4,6} 当i=5时
当i=4时?
4
04
06),5(<≤≥⎩⎨⎧=j j j m 0-1背包问题－算法改进
22
p[i]= p[i+1]∪q[i+1]–控制点 在递归地由表p[i+1]计算表p[i]时 先由p[i+1]计算出q[i+1]
然后合并表p[i+1]和表q[i+1]
清除其中的受控跳跃点得到表p[i]。
q[i+1]=p[i+1]⊕(w i ,v i )
={(j+w i ,m(i,j)+v i )|(j,m(i,j))∈p[i+1] p[n+1]={(0，0)}。
n=3，
m(3,x)
27
当所给物品的重量是整数时，(|p[i]|) ≤c+1, 1≤i ≤n)
改进后算法的计算时间复杂性为
O(min{nc,2n })
间
最优二叉搜索树
..k
j
最优二叉搜索树
k
最优二叉搜索树
36
p i 0.15 0.10 0.05 0.10 0.20q i 0.05 0.10 0.05 0.050.050.10
i
0 1 2 3 4 5
给定有序集S = <k 1, k 2, ..., k n > ，(k 1< k 2< ···< k n ), 如何建立BST ?
对每个key k i , 搜索概率p i
对不在S 中的值, 建立n+1个“虚拟键”d 0, d 1, ..., d n ，d 0表示该值< k 1; d n 表示该值> k n
for 1≤i ≤n-1, d i : k i < d i < k i+1. 搜索概率q i
每个k i 对应一个内结点，每个d i 建立一个叶子结点
40
最优二叉搜索树问题描述
对于有序集S 及其存取概率分布
(q 0,p 1,q 1,…,p n ,q n ), 在所有表示有序集S 的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树
(a) cost: 2.80(b) cost: 2.75
Figure (b) shows an optimal BST
不一定要求树的高度最小(An optimal BST is not necessarily a tree
42
穷举检查所有的可能性的算法效率很低.
Matrix-chain multiplication; Scheduling assembly lines; LCS
为了构造a BST ，对具有n 个节点的任何二叉树，将其节点分别标记为k 1, k 2, …, k n , 然后附加dummy keys 作为树叶。
则
有Ω(4n /n 3/2)种二叉树。
穷举搜索法的时间复杂度为指数级
Not surprisingly, we will solve this problem
with dynamic programming . ?
子问题。
