算法设计的与分析第6章动态规划法.pptVIP

TSP问题 ——算法 TSP问题 输入：图的代价矩阵arc[n][n] 输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度 1. 初始化第0列： for (i=1; in; i++) d[i][0]=c[i][0]; 2. 依次处理每一个子集数组V[2n-1] for (i=1; in; i++) if (子集V[j]中不包含i) 对V[j]中的每个元素k， 计算d[i][j]=min{arc[i][k]+d[k][j-1]}; 3. 输出最短路径长度d[0][2n-1-1]; 组合问题中的动态规划法 ——最长递增子序列问题 问题描述：在数字序列A={a1, a2, …, an}中按递增下标序列(i1, i2,…, ik)（1≤i1 i2… ik≤n）顺序选出一个子序列B，如果子序列B中的数字都是严格递增的，则子序列B称为序列A的递增子序列。最长递增子序列问题就是要找出序列A的一个最长的递增子序列。 最长递增子序列问题——想法 设序列A={a1, a2, …, an} 最长递增子序列是B={b1, b2,…, bm} 最长递增子序列问题满足最优性原理。 设L(n)为数字序列A={a1, a2, …, an}的最长递增子序列的长度，显然，初始子问题是{a1}，即L(1)=1。考虑原问题的一部分，设L(i)为子序列A={a1, a2, …, ai}的最长递增子序列的长度，则满足如下递推式： 1 i = 1或不存在ajai（1≤j＜i） max{L(j) + 1} 对于所有的ajai（1≤j＜i） L(i) = 于序列A={5, 2, 8, 6, 3, 6, 9, 7}，用动态规划法求解最长递增子序列。 最长递增子序列问题——实例 首先计算初始子问题，可以直接获得： L(1)=1({5}) 然后依次求解下一个阶段的子问题，有： L(2)=1({2}) L(3)=max{L(1)+1, L(2)+1}=2({5, 8}, {2, 8}) L(4)= max{L(1)+1, L(2)+1}=2({5, 6}, {2, 6}) L(5)=L(2)+1=2({2, 3}) L(6)=max{L(1)+1, L(2)+1, L(5)+1)}=3({2, 3, 6}) L(7)=max{L(1)+1, L(2)+1, L(3)+1, L(4)+1, L(5)+1, L(6)+1}=4({2, 3, 6, 9}) L(8)=max{L(1)+1, L(2)+1, L(4)+1, L(5)+1, L(6)+1}=4({2, 3, 6, 7}) 序列A的最长递增子序列的长度为4，有两个最长递增子序列，分别是{2, 3, 6, 9}和{2, 3, 6, 7})。 最长递增子序列问题——实例（填表） 序号 1 2 3 4 5 6 7 8 序列元素 5 2 8 6 3 6 9 7 子序列长度 1 1 2 2 2 3 4 4 递增子序列 {5} {2} {5,8},{2,8} {5,6},{2,6} {2,3} {2,3,6} {2,3,6,9} {2,3,6,7} 最长递增子序列问题——算法 设序列A存储在数组a[n]中，数组L[n]存储最长递增子序列的长度，其中L[i]表示元素序列a[0]~a[i]的最长递增子序列的长度，二维数组x[n][n]存储对应的最长递增子序列，其中x[i][n]存储a[0]~a[i]的最长递增子序列，注意到数组下标均从0开始，给出用C++语言描述的算法。 组合问题中的动态规划法 ——最长公共子序列问题 问题描述：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij≤m）。 给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。 设序列X={x1, x2,…, xm}，Y={y1, y2,…, yn} 最长公共子序列为Z={z1, z2,…, zk} 最长公共子序列问题满足最优性原理。 设L(m, n)表示序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列的长度，显然，初始子问题是序列X和Y至少有一个空序列，即： L(0, 0)=L(0, j)=L(i, 0)=0