《算法分析与设计AlgoD&ALectureNotesW6章节》由会员分享，可在线阅读，更多相关《算法分析与设计AlgoD&ALectureNotesW6章节（63页珍藏版）》请在金锄头文库上搜索。
1、Last Section,减 治,插入排序: n2, n, n2/4 快速排序+插入排序 拓扑排序: 减一 生成排列+ Johnson-Trotter 生成子集+比特串方法 假币问题 俄式乘法 约瑟夫斯问题 欧几里德算法 插值查找 二叉查找树,变治_实例化简,预排序 检验数组中元素的惟一性： n(n-1)/2, nlogn+n 模式计算： n(n-1)/2+n-1, nlogn+(n) 高斯消去法 Partial pivoting LU 分解 矩阵的逆 AVL树: 1.39logn, 1.01logn,变治_改变表现,变换为同样实例的不同表现改变表现(Representation Change
2、) 2-3 树 堆和堆排序 霍纳法则 二进制幂,变治_问题化简,变换为另一个问题的实例， 这种问题的算法是已知的问题化简(Problem reduction)。 Lcm 图中的路径数量 函数极值 综合除法 凸包，解析几何 线性规划 简化为图 MST vs. Element Uniqueness,Dynamic Programming,动态规划,动态规划,动态规划是解决多阶段决策过程最优化的一种方法。 对于离散问题，解析数学无法施展，动态规划则成为一非常有效的工具。 两个弱点： 得出目标函数方程后，尚无统一的处理方法，必须根据具体问题的性质结合相应的数学技巧来求解； 维数障碍。,动态规划,动态规
3、划模型的分类： 根据决策过程的时间参量是离散的还是连续的变量 离散（多段）决策过程 连续决策过程 根据决策过程的演变是确定性的还是随机性的 确定性决策过程 随机性决策过程 离散确定性 离散随机性 连续确定性 连续随机性,多阶段决策问题,由于它的特殊性，可将过程划分为若干互相联系的阶段； 在它的每一个阶段都需要作出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程的活动路线； 各个阶段所确定的决策就构成一个决策序列，通常称为一个策略； 每一个阶段可供选择的决策往往不止一个，对应于一个策略就有确定的活动效果； 多阶段决策问题，就是要在允许选择的那些策略中间，选择一个最优策略
4、，使在预定的标准下达到最好的效果。,问题举例,例1 最短路线问题 给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离； 要求选择一条由A到G的铺管线路，使总距离为最短。,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,最短路线问题,问题举例,例2 机器负荷分配问题 某种机器，可以在高低两种不同的负荷下进行生产。 在高负荷下进行生产时，产品的年产量s1和投入生产的机器数量u1的关系为 s1 = g (u1) 这时，机器的年折损率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为
5、au, 0a1. 在低负荷下生产时，产品的年产量s2和投入生产的机器数量u2的关系为 s2= h (u2) 相应的机器的年折损率为b, 0b1. 假定开始生产时完好的机器数量为x1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,例3 部件的生产计划问题,某车间需要按月在月底供应一定数量的某种部件给总装车间。 由于生产条件的变化，该车间在各月份中，生产每单位这种部件所耗费的工时不同。 各月份的生产，除供应该月的需要外，余下部分可存入仓库备用。但因仓库容量的限制，库存部件的数量不能超过某一给定值H。 已知半年期间的各个
6、月份的需求量，以及在这些月份生产该部件每单位数量所需工时数如表所示。 设仓库容量限制H= 9， 开始库存量为2，期末库存量为0。 要求制定一个半年的逐月生产计划，使在满足需要和库存量限制的条件下，生产这种部件的总耗费工时数达到最小。,问题举例,例4 不定步数的最短路线问题 给定M个点p1，p2，, pM, 其中任意两点pi和pj (1iM, 就1jM)间的距离cij是已知的，从一点直达另一点称为一步。要求在不限定步数的条件下，找出由pi 到达pM的最短路线。,动态规划的基本概念和基本方程,例1 最短路线问题 给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离
7、； 要求选择一条由A到G的铺管线路，使总距离为最短。 如图,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,最短路线问题,最短路线问题,从A到G可以分为6个阶段。各个阶段的决策不同，铺管路线就不同。 明显地，当某段的始点给定时，它直接影响着后面阶段的引进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各段路线的影响。 问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个策略所决定的一条路线，其总路程最短-最优策略 穷举法： 共有2 * 3 * 2 * 2 * 2 * 1=48 条路线,动态规划的
8、基本概念,阶段(Stage) 把所给问题的过程，恰当地划分成若干个相互联系的阶段，以便于求解。通常用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 = C
9、1, C2, C3, C4,动态规划的基本概念,决策（Decision） 决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。 描述决策的变量，称为决策变量。 常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。通常以Dk(xk)表示第k段的允许决策集合。 uk(xk) Dk(xk),动态规划的基本概念,决策（Decision） 决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。 描述决策的变量，称为决策变量。 常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内
10、，此范围称为允许决策集合。通常以Dk(xk)表示第k段的允许决策集合。 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。 即
11、p1,n(xk)= u1(x1), u2(x2), , un(xn) 由第k段开始到终点的过程称为原过程的后部子过程（或称为k子过程）。 其决策函数序列 uk(xk)，, un(xn)称为k子过程策略，简称子策略。即 pk,n(xk)=uk(xk), uk+1(xk+1), , un(xn) 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。从允许策略中找出达到最优效果的策略称为最优策略。,动态规划的基本概念,指标函数 在多阶段决策过程最优化问题中，指标函数是用来衡量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定数量函数，常用Vk,n表示
12、。即 Vk,n= Vk,n(xk ,uk ,xk+1 ,xn+1) k=1,2,n 不同的问题中，指标的含义也不同：距离、利润、成本、产量、资源消耗等。 例中， Vk,n表示第k阶段由点xk至终点G的距离； 第k阶段由点xk至uk(xk)的距离为阶段指标（阶段效益），可记为k(xk ,uk ) 。(E1, F1) 。,动态规划的基本概念,最优指标函数 指标函数Vk,n的最优值，称为相应的最优指标函数。记为fk(xk). 例中，fk(xk)表示从第k段xk点到终点G的最短距离。 如f4(D1)就表示从第4段中的D1点到G 点的最短距离。,动态规划的基本思想和基本方程,生活中平常的事例，即可深刻揭
13、示最短路线的重要特性： 如果最短路线在第K站通过点Pk, 则由点Pk出发到达终点的这条路线，对于从点Pk出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。 动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。,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,最短路线问题,最短路线问题,按照动态规划的方法，从最后一段开始计算，由后向前逐步推移至A点： 当k = 6 时，f6(F1)表示在第6段由F1至G的最短距离，故f6(F1)=4。同理，f6(F2)=3。 当k = 5 时，若从E1出发，则有两个选择
14、，一是至F1，一是至F2，则 f5(E1)=min = min = 7 这说明，由E1至终点G的最短距离为7，其最短路线是E1F1G，而相应的决策变量u5(E1)=F1.,最短路线问题,若从E2出发，也有两个选择，一是至F1，一是至F2，则 f5(E2)=min = min = 5 这说明，由E2至终点G的最短距离为5，其最短路线是E2F2G，而相应的决策变量u5(E2)=F2. etc.,动态规划的函数基本方程,在求解的各个阶段，我们利用了k阶段与k+1阶段之间的如下关系： k = 6,5,4,3,2,1 f7(x7)= 0 (或写成 f6(x6) = d6(x6, G),动态规划最优化原理
15、,动态规划最优化原理： 作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。,可逆过程,顺序解法：以G为始端，以A为终端的左行解法程序称为顺序解法 逆序解法 可以把段次颠倒过来求最优解的多阶段决策过程称为可逆过程。 顺序解法和逆序解法只表示行进方向的不同或始端的颠倒。但用动态规划方法求最优解时，都是在行进方向规定后，均要逆着这个规定的行进方向，从最后一段向前逆推计算，逐段找出最优途径。,与穷举法的对比,减少了计算量 穷举法： 要对48条路线进行比较，比较运算要进行47次； 求各条路线的距离（288次加法），即使使用逐段累加方法，也要进行0+6+12+32+48+48=146次加法运算。 动态规划方法： 比较运算（从k=5段开始向前算）共进行3+3+4+4+1=15次。 每次比较运算对应两次加法运算，再去掉中间重复两次（即B1C1， B2C4各多算了一次），实际只有28次加法运算。,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,最短路线问题,与穷举法的对比,丰富了计算结果 在逆序解法中，使我们得到的不仅仅是由A点出发到终点G的最短路线及相应的最短距离；而且得到了从所有各中
