算法复习_48273.ppt

算法复习 分治法时间复杂度 将规模为n的问题划分成a个规模为n／b的子问题去解。设分解阈值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及将a个子问题的解合并为原问题的解需用f(n)个单位时间。 分治算法实例 要求能够跟踪算法执行过程 二分有哪些信誉好的足球投注网站 合并排序 快速排序 大整数的乘法、Strassen矩阵乘法 棋盘覆盖 循环赛日程表 线性时间选择 最接近点对问题 写出采用分治法计算2101*1130的过程。 X=2101, Y=1130 a=21, b=01, c=11, d=30 X*Y= ac10n + ((a-b)(d-c)+ac+bd)10n/2 + bd ac=21*11, bd=1*30, (a-b)(d-c)=20*19 求ac: a’=2, b’=1, c’=1, d’=1, ac=a’c’10n + ((a’-b’)(d’-c’)+a’c’+b’d’)10n/2 + b’d’=200+30+1=231 求bd: a’’=0, b’’=1, c’’=3, d’’=0, bd=a’’c’’10n + ((a’’-b’’)(d’’-c’’)+a’’c’’+b’’d’’)10n/2 + b’’d’’=30 求(a-b)(d-c): a’’’=2, b’’’=0, c’’’=1, d’’’=9, (a-b)(d-c)=a’’’c’’’10n + ((a’’’-b’’’)(d’’’-c’’’)+a’’’c’’’+b’’’d’’’)10n/2 + b’’’d’’’=200+180=380 X*Y= ac10n + ((a-b)(d-c)+ac+bd)10n/2 + bd=2310000+64100+30=2374130 动态规划算法实例 要求能够跟踪算法执行过程 矩阵连乘、凸多边形最优三角剖分 最长公共子序列 0-1背包问题 最大子段和 多边形游戏 图像压缩 电路布线 例，5个矩阵连乘，行列数如下： 设给定的两个序列为X={x, y, x, z, y, x, y, z, z, y}, Y={x, z, y, z, x, y, z, x, y, z, x, y}，跟踪算法LCSLength的运行结果。 给定0-1背包问题的如下实例：n=5, c=10, w={2,2,6,5,4}, v={6,3,5,4,6}，跟踪Knapsack算法的运行结果。 贪心算法实例 要求能够跟踪算法执行过程 背包问题 活动安排问题 最优装载 Dijkstra单源最短路径 Prim Krusal最小生成树 哈夫曼编码 多机调度问题 给定一个带权有向图，跟踪Dijkstra单源最短路径算法。 Prim最小生成树 Kruskal最小生成树 回溯算法实例 要求能够跟踪算法执行过程 0-1背包问题 旅行售货商问题 装载问题 批处理作业调度问题 图的m着色问题 n后问题 连续邮资问题 解空间树：可以表示为树型，也可以用表格的形式来描述。 剪枝 用约束函数在扩展结点处剪去不满足约束的子树（剪去不可行） 用限界函数剪去不能得到最优解的子树（剪去非最优） 预估结点的上/下界 已确定的（从根到当前结点）状态之和 + 未确定的状态的上/下界 优先队列中结点的优先级 结点上/下界的值 左右儿子结点均需限界（回溯法左儿子结点无需限界） 回溯法vs.分支限界法 分支限界算法实例 要求能够跟踪算法执行过程 0-1背包问题 旅行售货商问题 布线问题 单源最短路经 最大团问题 找出满足约束条件的一个解或使得目标函数取得极值的最优解 每个结点只有一次成为活结点的机会 队列/优先队列 广度优先或最小耗费优先 分支限界 找出满足约束条件的所有解 活结点的所有可行子结点被遍历后才被从栈中弹出 堆栈 深度优先 回溯 应用 结点存储特征 数据结构 解空间树的有哪些信誉好的足球投注网站方式 A B C D E H I F G x[0]=1 ∞ 30 6 4 30 ∞ 5 10 6 5 ∞ 20 4 10 20 ∞ 初始化：bestc=NoEdge，产生第一个叶结点后更新 x[1]=2 x[1]=3 x[1]=4 B 活结点优先队列 E D C x[2]=2 x[2]=3 D F G C H F G I x[2]=2 x[2]=4 C J bestc=cc=25 F J G I C x[3]=3 cc=25 bestc=25 J G I C x[3]=4 叶结点的父结点作判断：回路？最优？ cc=0 rcost=18 cc=30 rcost=14 cc=4 rcost=14 cc=6 rcost=14 cc=11 rcost=9 cc=26 rcost=9 cc=24 rcost=10 cc=14 rcost=10 n=5, c=50, v=[12, 30, 44, 46, 50],