算 法 复 习.

Presentation on theme: "算 法 复 习."— Presentation transcript:

1 算 法 复 习

2 本学期所学的算法 蛮力法 分治法 减治法 动态规划 贪心算法 回溯法 分支限界法

3 课程总结 目的与任务： 本课程覆盖了计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度。
通过学习知道计算机领域中解决不同问题的一系列标准算法； 具备设计新算法和分析其效率的能力，锻炼逻辑思维能力和想象力，并了解算法理论的发展。 运用算法知识解决各自学科的实际问题，培养独立科研的能力和理论联系实践的能力。

4 考试形式 考勤 平时成绩----------------40% 期末考试-----------------------60%
填空题 （20分） 选择题 （20分） 计算题 （10分） 算法填空 （10分） 算法理解题 （20分） 算法设计题 （20分）

5 算法的概念 算法是完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过有限次运算，能够得出所要求或期望的终止状态或输出数据。 特征 确定性：每一步都有精确的（无歧义）定义，以保证算法的执行结果是确定的。 有限性：算法必须在有限步骤内实现。 输入：即问题的实例。零个或多个，由外部提供，从特定的对象集合中抽取，作为算法开始执行前的初始值。 输出：至少一个，是输入的某种函数，是算法计算的结果。 算法和方法有什么不同？ 5

6 分治法的基本思想 将一个问题划分成若干个规模较小的相同子问题（理想的情况是划分成相同规模）；当问题规模缩小到一定程度就很容易求解。
子问题被递归地解决。 必要的话，子问题的解可以合并为原问题的解。

7 分治法的适用条件 问题的规模缩小到一定程度就很容易解决。 问题可以分解成若干个规模较小的相同问题。
各个子问题是相互独立的，即子问题之间不包含公共的子问题。 利用子问题的解可以合并为原问题的解。 例如排序，当n=1时不需任何计算；n=2时只需要一次比较；n=3时需要3次比较。 2!=1*1!, 3!=3*2! 反例：fibonacci(5) = fibonacci(4) + fibonacci(3);fibonacci(4) = fibonacci(3) + fibonacci(2);

8 分治法时间复杂度 将规模为n的问题划分成a个规模为n／b的子问题去解。设分解阈值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及将a个子问题的解合并为原问题的解需用f(n)个单位时间。

9 分治算法实例 二分搜索 合并排序 快速排序 棋盘覆盖 循环赛日程表 线性时间选择 最接近点对问题

10 动态规划的基本思想 动态规划的实质是分治思想和解决冗余。它将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题。 最优子结构 原问题的最优解包含了子问题的最优解。 重叠子问题 有些子问题被反复计算多次（前一阶段的状态带到当前阶段，当前阶段的状态带到下一阶段）。 测验1棋盘覆盖 10

11 动态规划算法分析 T(n) = 计算最优值（填表）的时间 + 构造最优解的时间 空间复杂性：表格大小

12 动态规划算法实例 多阶段图最短路径 最长公共子序列 0-1背包问题 最优二叉查找树 近似串匹配问题 测验1LCS

13 贪心算法的基本思想 在对问题求解时，总是做出在当前看来最好的选择，也就是说，不从整体最优上加以考虑，期望通过所作的局部最优选择产生出一个全局最优解。 由此产生的全局解有时不一定是最优的。 动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。

14 贪心算法的基本要素 贪心选择性质 最优子结构性质 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法与动态规划算法的主要区别。 最优子结构性质 原问题的最优解包含其子问题的最优解。 这是贪心算法和动态规划算法的共性。

15 贪心vs.动态规划 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行。
在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。 动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。 　　因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

16 贪心算法实例 背包问题 活动安排问题 Dijkstra单源最短路径 Prim & Krusal最小生成树 哈夫曼编码 多机调度问题

17 典型的解空间树 子集树 当所给的问题是从n个元素的集合s中找出满足某种性质的子集时。例如0-1背包问题。这类子集树通常有2n个叶结点，其结点总个数为2n+1-1。遍历子集树的任何算法均需Ω(2n)的计算时间 排列树 当所给的问题是确定n个元素满足某种性质的排列时。例如TSP问题。这类排列树通常有n！个叶结点，遍历排列树需要Ω(n！)的计算时间

18 回溯法的基本思想 按照深度优先的策略搜索解空间树。
算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先策略进行搜索。 用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

19 剪枝 在搜索解空间树时，用剪枝函数来避免无效搜索。 用约束函数在扩展结点处剪去不满足约束的子树（剪去不可行）
用限界函数剪去不能得到最优解的子树（剪去非最优） 预估结点的上/下界 已确定的（从根到当前结点）状态之和 + 未确定的状态的上/下界

20 回溯算法实例 0-1背包问题 哈密顿回路问题 批处理作业调度问题 图的m着色问题 n后问题

21 分支限界法的基本思想 分支限界法以广度优先或最小耗费/最大效益优先的方式搜索解空间树。
在扩展结点处，先生成其所有的儿子结点（分支），在每一个活结点处，估算目标函数的界（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进。当一个叶结点成为扩展结点时，该叶结点相应的解即为问题的最优解。

22 剪枝 优先队列中结点的优先级 用约束函数在扩展结点处剪去不满足约束的子树（剪去不可行） 用限界函数剪去不能得到最优解的子树（剪去非最优）
预估结点的上/下界 已确定的（从根到当前结点）状态之和 + 未确定的状态的上/下界 优先队列中结点的优先级 结点上/下界的值 左右儿子结点均需限界（回溯法左儿子结点无需限界） bestn随着向左搜索而更新；和回溯法比较

23 活结点的所有可行子结点被遍历后才被从栈中弹出 找出满足约束条件的一个解或使得目标函数取得极值的最优解
回溯法vs.分支限界法 解空间树的搜索方式 数据结构 结点存储特征 应用 回溯 深度优先 堆栈 活结点的所有可行子结点被遍历后才被从栈中弹出 找出满足约束条件的所有解 分支限界 广度优先或最小耗费优先 队列/优先队列 每个结点只有一次成为活结点的机会 找出满足约束条件的一个解或使得目标函数取得极值的最优解

24 分支限界算法实例 0-1背包问题 TSP问题 多段图的最短路径问题 任务分配问题 批处理作业调度问题

25 算法运行的有多快 = 全部语句的执行时间之和
算法复杂度 输入分布：最坏情况、最好情况、平均情况 算法分析 = 分析算法复杂度 算法运行的有多快 = 全部语句的执行时间之和 假设每条语句的执行时间均为单位时间。 = 全部语句的执行次数之和 （问题规模n的运行时间函数） 算法运行中主要影响运行时间的语句是基本操作，即占有最多比例的语句。 = 基本操作的执行次数 （问题规模n的运行时间函数） 为了简化算法分析过程，并易于对不同算法的运行时间进行对比，只考虑问题规模充分大时的情况。 = （渐近）阶 = 算法的时间复杂度

26 f(n) = O( g(n)) n n0 f(n) cg(n) f(n) = ( g(n)) n n0 cg(n) f(n)
Ο：当对算法的最坏情况运行时间限界时，隐含地给出了对任意输入的运行时间的上界，即算法的上界。 Ω：当对算法的最好情况运行时间进行限界时，也隐含地给出了在任意输入下运行时间的下界，即算法的下界。 f(n) = O( g(n)) n n0 f(n) cg(n) f(n) = ( g(n)) n n0 cg(n) f(n) f(n) = ( g(n)) n n0 c1g(n) c2g(n) f(n)

27 时间复杂度只需考虑基本操作执行次数的最高阶，忽略其系数、低阶项和常数项
f(n) = an2+bn+c = (n2) f(n) = an3+bn2+cn+d = (n3)

28 常见的时间复杂性 1 ：几乎不存在 logn：不能考虑全部输入，二分搜索 n：遍历、扫描全部输入 nlogn：许多分治算法 n2 ：两层循环

29 算法分析步骤 确定用来表示问题规模的变量； 确定算法的基本操作； 写出基本操作执行次数的函数（运行时间函数）；
如果函数依赖输入实例，则分情况考虑：最坏情况、最好情况、平均情况； 只考虑问题的规模充分大时函数的增长率，用渐近符号O 、Θ、Ω 来表示。

30 NP完全理论 P类问题：可以用多项式时间的确定性算法来进行判定或求解；
NP完全问题：除非P=NP，否则不可能找到多项式时间的确定性算法的一类问题

31 尽管理论上没有证明，但大量研究表明，P似乎不等于NP，所以，一旦一个问题被证明是NP完全的，则基本可以断定，它不可能在多项式时间内求解

32 NP完全(NPC)问题举例 SAT问题（Boolean Satisfiability Problem）
TSP问题（Traveling Salesman Problem） 0-1背包问题（ 0-1 Knapsack Proble) 哈密顿回路问题（Hamiltonian Cycle Problem） 给出旅行商问题的图， 请大家思考直接解法，并给出 给出0，1背包问题问题描述，请思考直接解法，并给出 近似算法：找到最好的算法的近似值 随机算法：蒙特卡罗：算法不一定能找到正确解，但概率很小 拉斯维加斯：算法运行时间是随机的，运行时间非常长的概率很小 问：蒙特卡罗和拉斯维斯是什么，有什么共同特点？