动态规划法要素.ppt

1 1 F 2 2 F 4 + 1 = 5 2 + 2 = 4 4 E2 6 + 1 = 7 9 + 2 = 11 7 E1 7 + 1 = 8 5 + 2 = 7 7 E2 1 + 4 = 5 5 + 7 = 12 / / / 5 D1 8+ 4 = 12 4 + 7 = 11 6 + 7 = 13 11 D2 4+ 4 = 8 4+ 7 = 11 2+ 7 = 9 8 D1 9+ 5 = 14 5+ 11 = 16 / / / 14 C1 4+ 5 = 9 3+ 11 = 14 5+ 8 = 13 9 C1 / / / 1+ 11 = 12 7+ 8 = 15 12 C2 3+ 14 = 17 5+ 9 = 14 4+ 12 = 16 14 B2 下 顶 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E1 E2 F 3 5 4 9 5 4 3 5 1 7 1 5 8 4 6 4 4 2 2 2 6 9 7 5 1 4 即： A ? B2 ? C1 ? D1 ? E2 ? F 本章小结 动态规划法的设计思想： 把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题，最后一个子问题就是初始问题的解。 动态规划算法的基本要素： 最优性原理、子问题重叠性 设计动态规划算法的基本步骤： 分析最优解的性质，并刻划其结构特征； 递归地定义最优值； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，自顶向下构造最优解。 课后作业 1. 用动态规划法求解下图中从顶点0到顶点15的最短路径，写出求解过程。 练习：给定集合{k1,k2,k3,k4,k5}，满足k1＜k2＜k3＜k4＜k5，查找成功的概率分别为：p1=0.15,p2=0.1,p3=0.05,p4=0.1,p5=0.2，失败的概率为：q0=0.05,q1=0.1,q2=q3=q4=0.05,q5=0.1。构造一颗具有最小平均查找长度的二叉有哪些信誉好的足球投注网站树。 A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ⑷ 构造最优解 依据MatrixChain算法中数组s[i][j]记录的信息，可以确定计算矩阵链A[i:j]的最佳方式应该在矩阵Ak和Ak+1之间断开，即最优加括号的方式应为(A[i:k])(A[k+1:j])。因此，递归地构造最优解： void Traceback (int i, int j, int **s) { if (i==j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout“Multiply A”i“,”s[i][j]; cout“and A”(s[i][j]+1)“,”jendl; } 6.2 动态规划算法的基本要素 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 最优子结构是问题能用动态规划算法求解的前提。 用反证法说明问题的最优子结构性质。 重叠子问题 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 课后作业 1. 对以下5个矩阵相乘应用算法MatrixChain及算法Traceback。 A1：4*5，A2：5*3，A3：3*6， A4：6*4，A5：4*5 ⑴找出这5个矩阵相乘所需的最少数乘的次数m[1, 5]及部分中间结果m[i, j]： ⑵给出s[i, j]及最优括号表达式。 0 m[1,2]= m[1,3]= m[1,4]= m[1,5]= 0 m[2,3]= m[2,4]= m[2,5]= 0 m[3,4]= m[3,5]= 0 m[4,5]= 0 i j 6.3.1 最长公共子序列 子序列：若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}，使得对于所有j=1,2,…,k有：zj=xij。 例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 公共子序列：给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 6.3 动态规划法应用举例 问题