AlgoDALectureNotesW6.ppt
《AlgoDALectureNotesW6.ppt》由会员分享,可在线阅读,更多相关《AlgoDALectureNotesW6.ppt(81页珍藏版)》请在三一文库上搜索。
1、Last Section,Divide and Conquer,大整数乘法: n log 3 n1.59 矩阵乘法与STRASSEN 算法:nlog7 n2.81 最近点对:nlgn 凸包:nlgn,n2,减 治,插入排序: n2, n, n2/4 快速排序+插入排序 拓扑排序: 减一 生成排列+ Johnson-Trotter 生成子集+比特串方法 假币问题 俄式乘法 约瑟夫斯问题 欧几里德算法 插值查找 二叉查找树,变治_实例化简,预排序 检验数组中元素的惟一性: n(n-1)/2, nlogn+n 模式计算: n(n-1)/2+n-1, nlogn+(n) 高斯消去法 Partial p
2、ivoting LU 分解 矩阵的逆 AVL树: 1.39logn, 1.01logn,变治,变换为同样实例的不同表现改变表现(Representation Change) 2-3 树 堆和堆排序,霍纳法则,问题: 针对一个给定的x 的多项式 p(x) = anxn + an-1xn-1 + + a1x + a0 求值 霍纳法则是一个很好的改变表现技术的例子。 它不断地把x作为公因子从降次以后的剩余多项式中提取出来: p(x) =(anx + an-1)x + )x + a0,霍纳法则,对于多项式 p(x) = 2x4 - x3 +3x2 + x - 5, 有: p(x) = 2x4 - x3
3、 + 3x2 + x - 5 = x(2x3 - x2 + 3x + 1 )- 5 = x(x(2 x2 - x +3)+1)-5 = x(x(x(2 x-1)+3)+1)-5,霍纳法则,用一个两行的表来帮助计算: 第一行包含了该多项式的系数 第二行中,除了第一个单元用来存储an, 其他单元都用来存储中间结果 用第二行的最后一个单元乘以x的值再加上第一行的下一个系数, 来算出表格下一个单元的值 以这种方式算出的最后一个单元的值,就是该多项式的值。 *例:计算 p(x) = 2x4 - x3 + 3x2 + x 5 在x=3时的值,霍纳法则,Horner(P0n,x) /用霍纳法则求一个多项式在
4、一个给定点的值 /输入:一个n次多项式的系数数组P0n(从低到高存储),以及一个数字x /输出:多项式在x点的值 pPn for in-1 downto 0 do px*p+Pi return p 乘法和加法次数均为 n,二进制幂,霍纳法则计算an时,它退化成了一种对a 自乘的蛮力算法,以及一些无用的加法。 两种基于改变表现思想的计算an 的算法: 从左至右处理二进制串(n的二进制表示) 从右至左处理,二进制幂,设n = bIbib0是在二进制系统中,表示一个正整数n 的比特串,则可以通过以下多项式的值来计算n: p(x) = bI xI + + bi xi + + b0 其中x = 2。 应
5、用霍纳法则计算p(2) p1 / n=1, 第一个数字总是1 for i I-1 downto 0 do p 2 p + bi,二进制幂,a n = a p(2) : a p a 1 for i I-1 downto 0 do a p a 2 p + bi 另 = = = 如果bi = 0 = 如果bi = 1,二进制幂,LeftRightBinaryExponentiation(a,b(n) /用从左至右二进制幂算法计算an /输入:一个数字a和二进制位bI, b0 的列表b(n), 这些位来自于一个正整数n的二进制展开式 /输出:an 的值 product a for iI-1 downt
6、o 0 do product product*product if bi = 1 then product product*a return product,二进制幂,因为该算法在每次重复它惟一循环的时候都要做一到两次的乘法,所以它在计算an时,总的乘法次数M(n)是 b-1 M(n) 2(b-1) b 是代表指数n 的比特串的长度 b-1 = Vs. 减半,问题化简(Reduction),P1 reduced to P2 which can be solved by Algo A Solve P2 with Algo A Solution of P2 transformed to P1,问题
7、化简_lcm,Lcm(24,60)=120 24=2*2*2*3 质数因子 60=2*2*3*5 Lcm(24,60)=(2*2*3) *2*5 缺乏效率,并且需要一个连续质数的列表。 问题化简: lcm(m,n)和gcd(m,n)的积把m 和n 的每一个因子都恰好包含了一次,因此就简单地等于m 和n 的积。 lcm(m,n) =,问题化简,综合除法 (2x4 - x3 + 3x2 + x 5)/(x-3)的 商2 x3 + 5x2 + 18x +55;余数 160。 凸包:点的相对位置。 解析几何:几何-代数,计算图中的路径数量,从图(无向图或有向图)中第i个顶点到第j个顶点之间,长度为k0
8、的不同路径的数量等于Ak 的第(i,j)个原素,其中,A是该图的邻接矩阵。 例:,优化问题的化简,必须求某个函数f(x) 的最小值,并且我们知道一个求函数最大值的算法。 min f(x) = -max-f(x) max f(x) = -min-f(x),化简为线性规划问题,线性规划问题是一个多变量线性函数的最优化问题,这些变量所要满足的一些约束是以线性等式或线性不等式的形式出现的。,化简为线形规划问题,线性规划问题是一个多变量线性函数的最优化问题,这些变量所要满足的一些约束是以线性等式或线性不等式的形式出现的。 背包问题: 给定一个承重为W的背包和n个重量为w1, wn、价值为v1,vn的物品
9、,求出这些物品中最有价值的一个子集,并且要能够装到背包中。,背包问题与线形规划,背包问题的连续版本可以表示为下面这个线性规划问题: S.T. 0 xj 1, j = 1,n 离散版本 xj 0,1, j = 1,n,简化为图问题,状态空间图: 顶点,初始状态,目标状态 边,状态之间的可能转变 一过河迷题版本:,MST & Element Uniqueness,Dynamic Programming,动态规划,动态规划,动态规划是解决多阶段决策过程最优化的一种方法。 对于离散问题,解析数学无法施展,动态规划则成为一非常有效的工具。 两个弱点: 得出目标函数方程后,尚无统一的处理方法,必须根据具体
10、问题的性质结合相应的数学技巧来求解; 维数障碍。,动态规划,动态规划模型的分类: 根据决策过程的时间参量是离散的还是连续的变量 离散(多段)决策过程 连续决策过程 根据决策过程的演变是确定性的还是随机性的 确定性决策过程 随机性决策过程 离散确定性 离散随机性 连续确定性 连续随机性,多阶段决策问题,由于它的特殊性,可将过程划分为若干互相联系的阶段; 在它的每一个阶段都需要作出决策,并且一个阶段的决策确定以后,常影响下一个阶段的决策,从而影响整个过程的活动路线; 各个阶段所确定的决策就构成一个决策序列,通常称为一个策略; 每一个阶段可供选择的决策往往不止一个,对应于一个策略就有确定的活动效果;
11、 多阶段决策问题,就是要在允许选择的那些策略中间,选择一个最优策略,使在预定的标准下达到最好的效果。,问题举例,例1 最短路线问题 给出一个线路网络, 从A点要铺设一条管道到G点,其两点之间连线上的数字表示两点间的距离; 要求选择一条由A到G的铺管线路,使总距离为最短。,问题举例,例2 机器负荷分配问题 某种机器,可以在高低两种不同的负荷下进行生产。 在高负荷下进行生产时,产品的年产量s1和投入生产的机器数量u1的关系为 s1 = g (u1) 这时,机器的年折损率为a,即如果年初完好机器的数量为u,到年终时完好的机器就为au, 0a1. 在低负荷下生产时,产品的年产量s2和投入生产的机器数量
12、u2的关系为 s2= h (u2) 相应的机器的年折损率为b, 0b1. 假定开始生产时完好的机器数量为x1。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。,例3 部件的生产计划问题,某车间需要按月在月底供应一定数量的某种部件给总装车间。 由于生产条件的变化,该车间在各月份中,生产每单位这种部件所耗费的工时不同。 各月份的生产,除供应该月的需要外,余下部分可存入仓库备用。但因仓库容量的限制,库存部件的数量不能超过某一给定值H。 已知半年期间的各个月份的需求量,以及在这些月份生产该部件每单位数量所需工时数如表所示。 设
13、仓库容量限制H= 9, 开始库存量为2,期末库存量为0。 要求制定一个半年的逐月生产计划,使在满足需要和库存量限制的条件下,生产这种部件的总耗费工时数达到最小。,问题举例,例4 不定步数的最短路线问题 给定M个点p1,p2,, pM, 其中任意两点pi和pj (1iM, 就1jM)间的距离cij是已知的,从一点直达另一点称为一步。要求在不限定步数的条件下,找出由pi 到达pM的最短路线。,动态规划的基本概念和基本方程,例1 最短路线问题 给出一个线路网络, 从A点要铺设一条管道到G点,其两点之间连线上的数字表示两点间的距离; 要求选择一条由A到G的铺管线路,使总距离为最短。 如图,A,3,3,
14、6,6,2,5,5,3,3,4,3,2,1,2,2,3,3,5,3,8,6,6,3,1,4,8,5,7,6,8,最短路线问题,最短路线问题,从A到G可以分为6个阶段。各个阶段的决策不同,铺管路线就不同。 明显地,当某段的始点给定时,它直接影响着后面阶段的引进路线和整个路线的长短,而后面各阶段的路线的发展不受这点以前各段路线的影响。 问题的要求是:在各个阶段选取一个恰当的决策,使由这些决策组成的一个策略所决定的一条路线,其总路程最短-最优策略 穷举法: 共有2 * 3 * 2 * 2 * 2 * 1=48 条路线,动态规划的基本概念,阶段(Stage) 把所给问题的过程,恰当地划分成若干个相互联
15、系的阶段,以便于求解。通常用k表示阶段变量。 例中第一阶段为AB,包含2条支路:A B1和A B2 状态(State) 状态表示某段的出发位置。它既是该段某支路的始点,同时也是前一段某支路的终点。通常一个阶段包含若干个状态。 描述过程状态的变量,称为状态变量。常用xk表示在第k段的某一状态。第k段状态集合可表示为 Xk = xk(1), xk(2), , xk(i) , , xk(r) 故例中第三阶段的状态集合就可记为 X3 = x3(1), x3(2), x3(3) , x3(4)=1, 2, 3, 4 或 X3 = C1, C2, C3, C4,动态规划的基本概念,决策(Decision)
16、 决策就是某阶段状态给定以后,从该状态演变到下一阶段某状态的选择。 描述决策的变量,称为决策变量。 常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。通常以Dk(xk)表示第k段的允许决策集合。 uk(xk) Dk(xk),动态规划的基本概念,决策(Decision) 决策就是某阶段状态给定以后,从该状态演变到下一阶段某状态的选择。 描述决策的变量,称为决策变量。 常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。通常以Dk(xk)表示第k段的允许决策集合。
17、uk(xk) Dk(xk) 例中第二阶段状态集合X2=B1,B2; 则从B1出发的允许决策集合D2 ( B1 )=C1,C2, C3; 若选择点C2, 则u2 ( B1 )=C2。,A,3,3,6,6,2,5,5,3,3,4,3,2,1,2,2,3,3,5,3,8,6,6,3,1,4,8,5,7,6,8,最短路线问题,动态规划的基本概念,策略(Policy) 由过程的第1阶段开始到终点为止的过程,称为问题的全过程。 由每段的决策ui(xi)(i=1,2,n)组成的决策函数序列就称为全过程策略,简称策略,记为p1,n。 即 p1,n(xk)= u1(x1), u2(x2), , un(xn) 由
18、第k段开始到终点的过程称为原过程的后部子过程(或称为k子过程)。 其决策函数序列 uk(xk),, un(xn)称为k子过程策略,简称子策略。即 pk,n(xk)=uk(xk), uk+1(xk+2), , un(xn) 在实际问题中,可供选择的策略有一定的范围,此范围称为允许策略集合,用P表示。从允许策略中找出达到最优效果的策略称为最优策略。,动态规划的基本概念,指标函数 在多阶段决策过程最优化问题中,指标函数是用来衡量所实现过程的优劣的一种数量指标,它是一个定义在全过程和所有后部子过程上的确定数量函数,常用Vk,n表示。即 Vk,n= Vk,n(xk ,uk ,xk+1 ,xn+1) k=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- AlgoDALectureNotesW6
链接地址:https://www.31doc.com/p-2976127.html