第3章_动态规划

1、1、第3章动态规划，2、学习要点：了解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构的性质(2)重叠子问题的性质，掌握动态规划算法的设计步骤。(1)找出最优解的性质并描述其结构特征。(2)递归定义最优值。(3)自下而上计算最佳值。(4)根据计算最优值时获得的信息，构造最优解。3。通过应用实例学习动态规划算法的设计策略。(1)矩阵乘法；(2)最长公共子序列；(3)最大分段金额；(4)凸多边形的最优三角剖分；(5)多边形游戏；(6)图像压缩；(7)0-1背包问题，4。塔的数量：如下图所示，从顶部开始，你可以选择在每个节点向左或向右走，一起走到底部，要求找到一条路径，使路径上的值最大

2、化。自顶向下分析，自底向上计算最优解的结构(最优子结构性质)子问题的重叠性质，首先看几个例子，并介绍“动态规划”的思想。5.假设AI和J代表数字塔中从上到下和从左到右的J数，让Mi和J代表从上到下和从左到右的J数。然后是下面的递归公式：当填充m数组时，应该是从下到上，从左到右，如下图所示。最短路径问题：(多阶段图)地图中的每个顶点代表一个城市，两个城市之间的连接代表一条道路，连接上的值代表道路的长度。现在，我们想从A市到e市。最短的距离是多少？7，A-EB1-E，B2-EC1-E，C2-E，C3-EC2-E，C4-E，C2-E被计算了两次，D1-E被计算了四次，8，制作一个表格来记录从每个点到

3、E的最短路径，并从末端到源填充该表格。注意：任何最短路径的子路径都是相对于子路径9的开始和结束的最短路径。让我们再举一个例子：最优子结构：如果ABEG是从A到G的最短路径，那么ABE也是从A到e的最短路径，10，11，12，13，旅行推销员问题(小贩承担问题)，在有向图中找出一个成本最低的旅行线路。一个销售员从第一城市开始，想在几个城市销售商品，并且知道城市之间的距离(或差旅费)。他想选择一条路线，从第一站开始，经过每个城市，最后一次又一次地回到车站，以使总成本最小化。1 2 4 3 1最小旅行费用：10 10 9 6=35，14，让g(i，S)是从顶点I开始的最佳路线的长度，通过S集合中的每

4、个顶点一次且仅一次，然后返回顶点1，然后：分析：假设从顶点1开始，从V-1中选择下一个顶点t，那么t1必须是|S|=0: g(2)，=c2，1=5 g(3)，=c3，1=6 g(4)，=c4，1=20 )=18 g(3，4)=c3，4 g(4)，=32 g(4，2)=c4，2 g(2)，=13 g(4，3)=c4，3 g(3)，=15，16，|S|=2 g(2，3，4)=minc2，3 g(3，4)，c2，4 g(4，3)=25 g(3，2，4)=minc3，2 g(2，4)，c3，4 g(4，2)=25 它的基本思想是把要解决的问题分解成几个子问题。该算法的一般思想是19，但是通过分解得到的

5、子问题通常不是相互独立的。不同子问题的数量通常只有多项式数量级。一些子问题在用分治法求解时会被重复计算多次。该算法的一般思想是20。如果我们能保存已解决的子问题的答案，并在必要时找出答案，就可以避免大量的重复计算，得到多项式时间算法。T(n)，算法的一般思想，21，动态规划的基本步骤，找出最优解的性质并描述其结构特征。递归定义最佳值。自下而上计算最佳值。根据计算最优值时获得的信息，构造最优解。，动态规划框架=最优解结构的递归定义，最优解填充模式的最优结果的构造，22。完全括号矩阵的连续乘积可以递归地定义为：有四个矩阵，它们的维数是：总共有五个完全括号的方式，(1)单个矩阵是完全括号的；(2)如

6、果矩阵连续乘积是完全括号内的，它可以表示为两个完全括号内的矩阵连续乘积和括号内的乘积之和，即16000，10500，36000，87500，34500，完全括号内的矩阵连续乘积，23。参见另一个示例：A1:100，A2:0。A3:550乘法阶数(A1A 2)a 3: 10 100 5 10 550=7500 A1(A2A 3): 10 100 50 100 550=75000，带完全括号的矩阵连续乘积，24，矩阵连续乘法问题，给定n个矩阵，其中和是乘法的。研究这N个矩阵的连续积因为矩阵乘法满足关联定律，所以计算矩阵的连续积有许多不同的计算顺序。这个计算顺序可以由括号决定。如果一个矩阵连续乘积的计算顺序是完全确定的，也就是说，这个连续乘积已经被完全括起来，那么矩阵乘法的标准算法就可以按这个顺序反复调用来计算这个矩阵连续乘积。25，给定n个矩阵a1，a2和an，其中Ai和Ai 1是乘法的，i=1，2，n-1。如何确定矩阵连续积的计算顺序，使按此顺序计算矩阵连续积所需的次数最少。穷举法：列出所有可能的计算顺序，计算每个计算顺序所需的次数，找出次数最少的计算顺序。算法复杂度分析：对于n个矩阵的连续乘积，让不同的计算顺序为P(n)。由于每个括号方法可以分解为两个子矩阵的括号问题：(A1.Ak(Ak)1An)，关于P(n