算法设计与分析.ppt

宋传鸣,算法设计与分析,辽宁师范大学计算机与信息技术学院,计算机科学与技术专业课程,chmsong,Algorithm Design and Analysis,最长公共子序列问题的描述,矩阵连乘 最长公共子序列 最大子段和 0-1背包,子序列的定义 给定序列X=x1,x2,xn和序列Z=z1,z2,zn,若存在一个严格递增的下标序列i1,i2,ik,使得对于任意j=1,2,k,有zj=xij,则称Z是X的子序列 例:设X=“zxyxyz”, Z=“xyy”是X的子序列 公共子序列的定义 给定两个序列X和Y,若另一个序列Z既是X的子序列,又是Y的子序列,则称Z是X和Y的公共子序列 例:再设Y=“xyyzx”,Z=“xyy”和“xyyz”都是X和Y的公共子序列 最长公共子序列问题:给定序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的一个最长公共子序列,最长公共子序列的朴素解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,基本思想 找出X序列的所有子序列,并验证其是否为Y的子序列.检查过程中记录长度最长的公共子序列 时间复杂度分析 X序列共有 个不同的子序列,最长公共子序列的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,最长公共子序列的最优子结构性质 设序列Xm=x1,x2,xm和Yn=y1,y2,yn的一个最长公共子序列为Z=z1,z2,zk,则有 如果xm=yn,那么zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列 如果xmyn,且zkxm,那么Zk是Xm-1和Yn的最长公共子序列 如果xmyn,且zk yn,那么Zk是Xm和Yn-1的最长公共子序列 两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,最长公共子序列的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,建立最优解的递归结构 求最长公共子序列的递归过程 如果xm=yn,那么只需找出Xm-1和Yn-1的最长公共子序列,然后再在其尾部加上xm 如果xmyn,那么分别求出Xm-1和Yn的最长公共子序列,以及Xm和Yn-1的最长公共子序列,然后从二者中取出较长者 最优值的递归关系 设cij表示序列Xi和Yj的最长公共子序列的长度,其中Xi=x1,x2,xi,Yj =y1,y2,yj, 则有,最长公共子序列的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,计算最优值 由递归式写出递归解法,需耗费指数级时间 Xm序列仅包含m个前缀,Yn仅包含n个前缀,所以子问题的数目有 个 动态规划的求解方法:以自底向上的方式求解,以 cij存储Xi和Yj的最长公共子序列的长度,bij记录cij的值是由哪一个子问题的解得到的,最长公共子序列的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,动态规划算法的步骤,最长公共子序列的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,计算复杂度分析 算法中包含一个二重循环和两个二维数组 T(n)=O(mn) S(n)=O(n2) 关于空间复杂度的改进 去掉数组b 每次只保存c的两行 S(n)=O(minn,m),最长子段和问题的描述,矩阵连乘 最长公共子序列 最大子段和 0-1背包,背景举例 操作系统要处理n个请求,并且只能在0W时间内提供服务,每个请求进程需wi时间处理.如何调度这些进程使得W时间内CPU尽可能地忙碌 形式化描述:给定n项1,2,n,每项具有一个非负权值wi (i=1,2,n),以及一个界W,要求从n项中选出若干项组成集合S,且: 问题描述 给定n个整数(可能为负数)组成的序列a1,a2,an,求该序列形如 的子段和的最大值,最长子段和问题的朴素解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,基本思想 尝试各种可能,即在任意位置开始,计算任意长度的子段和 算法步骤 时间复杂度分析 算法包含两重循环,T(n)=O(n2),最长子段和问题的分治解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,基本思想 将所给的序列a1:n分为长度相等的两段a1:n/2和an/2+1:n,分别求出两段的最大子段和 原序列的最大子段和有三种情形 等于a1:n/2的最大子段和 等于an/2+1:n的最大子段和 等于 ,且 子问题的合并:以a1:n/2最后一个元素为终点的最大子段和与以n/2+1:n第一个元素为起始点的最大子段和的和,最长子段和问题的分治解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,算法步骤 计算复杂度分析 两个一重循环和两次规模为n/2的递归求解 T(n)=O(nlog2n),最长子段和问题的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,最大子段和的最优子结构性质 最大子段和的定义为: 令 ,则有 又 , 此时有 若bj-10,则bjaj,即bj=aj+bj-1 若bj-1=0,则bj=aj 建立最优解的递归结构 bj=maxbj-1+aj,aj (ijn),最长子段和问题的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,算法步骤 计算复杂度分析 包含一重循环 T(n)=O(n), S(n)=O(n),0-1背包问题的描述,矩阵连乘 最长公共子序列 最大子段和 0-1背包,背景举例 操作系统要处理n个请求,并且只能在0W时间内提供服务,每个请求进程需wi时间处理.如何调度这些进程使得W时间内CPU尽可能地忙碌 形式化描述:给定n项1,2,n,每项具有一个非负权值wi (i=1,2,n),以及一个界W,要求从n项中选出若干项组成集合S,且:,0-1背包问题的描述,矩阵连乘 最长公共子序列 最大子段和 0-1背包,问题描述 给定n种物品和一个背包.物品i的重量是wi,其价值为vi,背包的容量为c.选择装入背包中的物品,使得装入背包中物品的总价值最大.注意:每种物品只有装入背包或不装入背包两种可能,故称“0-1背包” 形式化描述 给定c0,wi0,vi0,1in,要求找出n元0-1向量 (x1,x2,xn), xi0,1,使得 ,且 达到最大,即,0-1背包问题的朴素解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,基本思想 尝试各种可能的取法 时间复杂度分析 共有2n种可能的取法 T(n)=O(2n),0-1背包问题的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,0-1背包问题的最优子结构性质 若(y1,y2,yn)是0-1背包问题的一个最优解,则(y2, y3,yn)是下述问题的一个最优解 建立最优解的递归结构 设m(i,j)表示背包容量为j,可选择物品i,i+1,n时 0-1背包问题的最优值,则有,(边界条件),0-1背包问题的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,动态规划算法的步骤,0-1背包问题的动态规划解法,矩阵连乘 最长公共子序列 最大子段和 0-1背包,示例:假如有容量为9的背包,要装入4种重量为2,3,4和5的物品,它们的价值分别为3,4,5和7.求解该0-1背包问题 时间复杂性分析 计算量集中在二重循环, T(n)=O(cn),j=0 1 2 3 4 5 6 7 8 9,i=1 i=2 i=3 i=4