算法分析与设计AlgoDALectureNotesW6章节.pptVIP

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-3 树 堆和堆排序 霍纳法则 二进制幂 变治_问题化简 变换为另一个问题的实例， 这种问题的算法是已知的—问题化简(Problem reduction)。 Lcm 图中的路径数量 函数极值 综合除法 凸包，解析几何 线性规划 简化为图 MST vs. Element Uniqueness Dynamic Programming 动态规划 动态规划 动态规划是解决多阶段决策过程最优化的一种方法。 对于离散问题，解析数学无法施展，动态规划则成为一非常有效的工具。 两个弱点： 得出目标函数方程后，尚无统一的处理方法，必须根据具体问题的性质结合相应的数学技巧来求解； 维数障碍。 动态规划 动态规划模型的分类： 根据决策过程的时间参量是离散的还是连续的变量 离散（多段）决策过程 连续决策过程 根据决策过程的演变是确定性的还是随机性的 确定性决策过程 随机性决策过程 离散确定性 离散随机性 连续确定性 连续随机性 多阶段决策问题 由于它的特殊性，可将过程划分为若干互相联系的阶段； 在它的每一个阶段都需要作出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程的活动路线； 各个阶段所确定的决策就构成一个决策序列，通常称为一个策略； 每一个阶段可供选择的决策往往不止一个，对应于一个策略就有确定的活动效果； 多阶段决策问题，就是要在允许选择的那些策略中间，选择一个最优策略，使在预定的标准下达到最好的效果。 问题举例 例1 最短路线问题 给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离； 要求选择一条由A到G的铺管线路，使总距离为最短。 最短路线问题 问题举例 例2 机器负荷分配问题 某种机器，可以在高低两种不同的负荷下进行生产。 在高负荷下进行生产时，产品的年产量s1和投入生产的机器数量u1的关系为 s1 = g (u1) 这时，机器的年折损率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au, 0a1. 在低负荷下生产时，产品的年产量s2和投入生产的机器数量u2的关系为 s2= h (u2) 相应的机器的年折损率为b, 0b1. 假定开始生产时完好的机器数量为x1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。 例3 部件的生产计划问题 某车间需要按月在月底供应一定数量的某种部件给总装车间。 由于生产条件的变化，该车间在各月份中，生产每单位这种部件所耗费的工时不同。 各月份的生产，除供应该月的需要外，余下部分可存入仓库备用。但因仓库容量的限制，库存部件的数量不能超过某一给定值H。 已知半年期间的各个月份的需求量，以及在这些月份生产该部件每单位数量所需工时数如表所示。 设仓库容量限制H= 9， 开始库存量为2，期末库存量为0。 要求制定一个半年的逐月生产计划，使在满足需要和库存量限制的条件下，生产这种部件的总耗费工时数达到最小。 问题举例 例4 不定步数的最短路线问题 给定M个点p1，p2，……, pM, 其中任意两点pi和pj (1≤i≤M, 就1≤j≤M)间的距离cij是已知的，从一点直达另一点称为一步。要求在不限定步数的条件下，找出由pi 到达pM的最短路线。 动态规划的基本概念和基本方程 例1 最短路线问题 给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离； 要求选择一条由A到G的铺管线路，使总距离为最短。 如图 最短路线问题 最短路线问题 从A到G可以分为6个阶段。各个阶段的决策不同，铺管路线就不同。 明显地，当某段的始点给定时，它直接影响着后面阶段的引进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各段路线的影响。 问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个策略所决定的一条路线，其总路程最短----最优策略 穷举法： 共有2