【算法设计与分析】期末复习
文章目录
- 复习大纲
- 第一章算法概述
- 1.1算法与程序
- 1.2 算法复杂性分析
- 第二章递归与分治策略
- 分治法的基本思想
- 递归与分治的关系：
- 用分治法解决的问题的几个特征：
- 例题：
- 第三章动态规划
- 动态规划的基本思想：
- 分治与动态规划算法的异同：
- 理解动态规划算法的基本要素：
- 动态规划算法求解问题的步骤：
- 例题：
- 第四章贪心算法
- 理解贪心算法的基本要素：
- 贪心算法与动态规划算法的异同点：
- 0-1背包问题能不能用贪心算法求解？为什么？
- 例题：
- 第五章回溯法
- 回溯法的基本思想：
- 回溯法解题步骤
- 用回溯法解题的特征：
- 回溯法的算法框架：
- 影响回溯法的效率因素：
- 例题（看PPT）：
- 第六章分支限界法
- 分支限界法的基本思想：
- 分支限界法与回溯法的异同：
- 分支限界法的实现方式：
- 例题：
- 复习题库
- 选择题
- 填空题
- 算法填空
- 简答题
- 1.分治法的基本思想：
- 2.设计动态规划算法的主要步骤为：
- 3. 分治法与动态规划法异同
- 4. 分支限界法与回溯法异同
- 5.贪心算法与动态规划算法的主要区别
- 6. 分治法所能解决的问题一般具有的几个特征是：
- 7. 用分支限界法设计算法的步骤是：
- 8. 常见的两种分支限界法的算法框架
- 9. 回溯法中常见的两类典型的解空间树：
- 10. 分支限界法的搜索策略是：
- 11、回溯法的基本思想
- 算法设计题
复习大纲
第一章算法概述
1.1算法与程序
算法：是解决问题的一种方法或一个过程，是由若干条指令组成的有穷序列。
算法性质：
1.输入：有零个或多个
2.输出：至少一个
3.确定性：组成算法的每条指令清晰无歧义
4.有限性：算法中每条指令的执行次数和执行时间是有限的
5.算法与程序的区别：程序是算法用某种程序设计语言的具体实现，可以不满足有限性。
1.2 算法复杂性分析
1.算法的复杂性分时间复杂性和空间复杂性。
2.三种情况下的时间复杂性，可操作性最好最有实际价值的是最坏情况下的时间复杂性。
3.算法复杂性的渐进分析：O，o，Ω，ω，Θ
第二章递归与分治策略
分治法的基本思想
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
递归与分治的关系：
由分治法产生的子问题往往是原问题的较小模式，反复应用分治法，可以使子问题与原问题类型一致且规模不断缩小，最终使子问题缩小到很容易求解，因此用递归求解。
用分治法解决的问题的几个特征：
•问题的规模缩小到一定的程度可以容易地解决；
•问题可以分解为若干个规模较小的相同问题；
•利用原问题分解出的子问题的解可以合并为原问题的解；
•问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。如果子问题不是相互独立的，可以用动态规划法。
例题：
深刻理解算法的设计并能够进行时间复杂度分析
排列问题（包括有重复元素的情况），二分搜索，大整数乘法和矩阵乘法的分治思想，合并排序，快速排序，棋盘覆盖的思想。
第三章动态规划
动态规划的基本思想：
将待求解问题分解成若干个子问题，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，为避免大量的重复计算，用一个表记录所有已解决的子问题的答案，而在需要的时候再找出已求得的答案。
分治与动态规划算法的异同：
分治法与动态规划法的相同点是:将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
两者的不同点是:适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。而用分治法求解的问题,经分解得到的子问题往往是互相独立的。
理解动态规划算法的基本要素：
- 最优子结构性质：问题的最优解包含了其子问题的最优解。
- 重叠子问题性质：有些子问题被反复计算多次。
动态规划算法求解问题的步骤：
- 找出最优解的性质，并刻画其结构特征
- 递归地定义最优值
- 以自底向上的方式计算出最优值
- 构造最优解
例题：
深刻理解矩阵连乘问题、最长公共子序列问题、最大子段和问题和0-1背包问题的动态规划算法，并进行时间复杂度和空间复杂度分析。
第四章贪心算法
理解贪心算法的基本要素：
- 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
- 最优子结构性质。
贪心算法与动态规划算法的异同点：
（1）共同点：都需要最优子结构性质，都用来求最优化问题。
（2）不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上或自顶向下（备忘录方法）求解；
贪心方法：自顶向下求解。
0-1背包问题能不能用贪心算法求解？为什么？
对于部分背包问题,依照贪心选择策略,可以得到最优解。而0-1背包问题,贪心选择之所以不能得到最优解,是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。因而我们选择的判断标准出现了误差。
例题：
重点：活动安排、背包问题、最优装载
单源最短路径、哈弗曼编码、最小生成树问题，重点理解贪心策略
第五章回溯法
回溯法的基本思想：
在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法解题步骤
- 针对所给问题，定义问题的解空间；
- 确定易于搜索的解空间结构；
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
用回溯法解题的特征：
在搜索过程中动态产生问题的解空间。问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点的路径。
回溯法的算法框架：
递归回溯、子集树与排列树算法框架
影响回溯法的效率因素：
- 产生x[k]的时间；
- 满足显约束的x[k]值的个数；
- 计算约束函数constraint的时间；
- 计算上界函数bound的时间；
- 满足约束函数和上界函数约束的所有x[k]的个数。
例题（看PPT）：
装载问题、n后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题。
对每一个问题深刻理解以下几点：
- 解的表示形式
- 解空间表示成什么样的树型结构
- 约束条件是什么？
- 限界条件是什么（如果有的话）？
- 如何构造并输出解。
第六章分支限界法
分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
分支限界法与回溯法的异同：
1)求解目旳:回溯法旳求解目旳是找出解空间树中满足约束条件旳所有解,而分支限界法旳求解目旳则是找出满足约束条件旳一种解,或是在满足约束条件旳解中找出在某种意义下旳最优解。
2)搜索方式旳不同:回溯法以深度优先旳方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先旳方式搜索解空间树。
分支限界法的实现方式：
队列式和优先队列式
例题：
单源最短路径、装载问题（重点）、0-1背包问题、旅行售货员问题。对于优先队列式分支限界法，重点理解堆元素的优先级怎么定，结点的上界或下界如何确定。
复习题库
选择题
1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
5. 回溯法解旅行售货员问题时的解空间树是（B ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
7、衡量一个算法好坏的标准是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题
9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
13.备忘录方法是那种算法的变形。（ B ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法
14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆 B、最大堆 C、栈 D、数组
16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
17．实现棋盘覆盖算法利用的算法是（ A ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
18.下面是贪心算法的基本要素的是（ C ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
19.回溯法的效率不依赖于下列哪些因素（ D ）
A.满足显约束的值的个数 B. 计算约束函数的时间
C. 计算限界函数的时间 D. 确定解空间的时间
20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）
A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数
21、下面关于NP问题说法正确的是（B ）
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
24. （D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
25. 矩阵连乘问题的算法可由（ B）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
A、最小堆 B、最大堆 C、栈 D、数组
27、Strassen矩阵乘法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
29、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的
B 子问题不能够重复
C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
30、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题 B N皇后问题
C 最小花费生成树问题 D 背包问题
31、下列算法中不能解决0/1背包问题的是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
34．实现合并排序利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
35．下列是动态规划算法基本要素的是（ D ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
37．采用广度优先策略搜索的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
38、合并排序算法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
40、背包问题的贪心算法所需的计算时间为（ B ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
41．实现大整数的乘法是利用的算法（ C ）。
A、贪心法 B、动态规划法 C、分治策略 D、回溯法
42．0-1背包问题的回溯算法所需的计算时间为（ A ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
43．采用最大效益优先搜索方式的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
44．贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解
45. 实现最大子段和利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
46.优先队列式分支限界法选取扩展结点的原则是（ C ）。
A、先进先出 B、后进先出 C、结点的优先级 D、随机
47.背包问题的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
48、广度优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
52. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
54. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
55. 实现最长公共子序列利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
填空题
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2、程序是 算法 用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
6、算法是指解决问题的 一种方法 或 一个过程 。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法 。
11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。
14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。
16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
17、矩阵连乘问题的算法可由 动态规划 设计实现。
19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。
21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
22.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。
23、大整数乘积算法是用 分治法 来设计的。
24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。
26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
27.快速排序算法是基于 分治策略 的一种排序算法。
28.动态规划算法的两个基本要素是. 最优子结构 性质和 重叠子问题 性质 。
30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
31.分支限界法主要有 队列式（FIFO） 分支限界法和 优先队列式 分支限界法。
32．分支限界法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
33．回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。
34.任何可用计算机求解的问题所需的时间都与其 规模 有关。
35.快速排序算法的性能取决于 划分的对称性 。
算法填空
1.背包问题的贪心算法
void Knapsack(int n, float M, float v[], float w[], float x[]) { Sort(n, v, w);//排序 int i; for (i = 1; i if (w[i] c) break;//如果物品的重量大于剩余背包容量，跳出循环 x[i] = 1;//否则改变物品状态为1 表示已经选择 c - = w[i];//背包剩余容量改变 } if (i int sum = 0, b = 0; //sum用来表示最大值 b用来当做目前的子段和 for (int j = 1;j if(b 0) b += a[j]; //如果b大于0，那么就加上当前的 else b = a[j];//否则就等于当前的 if (b sum)//如果b比sum大的话 那么sum就赋值为b sum = b; } return sum; } int *t = new int[n + 1]; Sort(w, t, n) for (int i = 1; i x[t[i]] = 1; c -= w[t[i]]; } } A[1] = true; int j = 1; for (int i = 2; i if (s[i] = f[j])//如果开始时间大于上一个的结束时间 { A[i] = true;//选择这个活动 j = i;//更新上一个活动的标记 } else A[i] = false;//不选这个活动 } } if (p
