[数据结构与算法]算法分析与设计期末复习

第一章 ?算法概述

1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。

2.算法的性质：

1. 输入：有零个或多个输入
2. 输出：有至少一个输出
3. 确定性：每条指令是清晰的、无歧义的
4. 有限性：每条指令的执行次数和时间都是有限的

3.算法与程序的区别

• 程序是算法用某种程序设计语言的具体实现
• 程序可以不满足算法的有限性

4.算法复杂性分析

1. 算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性
2. 三种时间复杂性：最坏情况、最好情况、平均情况
3. 可操作性最好且最有实际价值的是最坏情况下的时间复杂性

5.f(N)<=Cg(N), f(N)为上界，反之下界；

6.P类问题：所有可以在多项式时间内求解的判定问题

? NP问题：所有非确定性多项式时间可解的判定问题；

7.主定理

?

?

第二章 ?递归与分支策略

1.递归概念：直接或间接调用自身的算法

2.递归函数：用函数自身给出定义的函数

3.递归要素：边界条件、递归方程

4.递归的应用

• 汉诺塔问题

void Hanuo(int n,int a,int b,int c)

{

??? if(n==1) return;

??? Hanuo(n-1,a,c,b);

??? move(a,b)

??? Hanuo(n-1,c,b,a);

}

• 全排列问题

void Perm(Type list[],int k,int m)

{?? //产生list[k,m]的所有排列

??? if(k == m)

??? {

?????? for(int i = 0;I <= m;i++) cout<<list[i];

?????? cout<<endl;

}

else

{

??? for(int i = j; i<=m;i++)

??? {??

?????? Swap(list[k],list[i]);

?????? Perm(list,k+1;m);

?????? Swap(list[k],list[i])

}

}

???

}

5.分治法的基本思想（简答题）：将一个规模较大的问题分成若干个规模相同的较小的子问题，这些子问题互相独立且与原问题相同，一般递归地解决这些子问题，可以将各个子问题的解合并得到原问题的解。

6.分治法的使用条件：

• 问题的规模缩小到一定程度可以容易地解决
• 问题可以分解为若干个规模较小的相同问题
• 利用原问题分解出的子问题的解可以合并为原问题的解
• 各个子问题是相互独立的

7.分治法的时间复杂度

8.分治法的应用

• 二分搜索

1. 时间复杂度 O(logn)
2. 参考算法

• 快速排序：（步骤：分解、递归求解、合并）

1. 快排的运行时间与划分是否对称有关
2. 时间复杂度O(nlogn)

• 合并排序

1. 基本思想：将待排元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最总将排序好的子集合合并成所要求的排序好的集合。
2. 时间复杂度O(nlogn)

• 棋盘覆盖
• 大整数乘法
• Strassen矩阵乘法
• 最接近点对问题：O（nlogn）

9.斐波那契数列算法

int fibonacci（int n）{

if(n<=1)

? return 1;

return fibonacci(n-1)+ fibonacci(n-2);

}

10.时间复杂度计算：

?

?

?

?

?

?

第三章 ?动态规划

1.基本思想：将待求解问题分解成若干个子问题，先求解子问题，再从这些子问题的解得到原问题的解。

2.动态规划与分治法的区别：

??? 与分治法不同，适合于动态规划求解的问题，经分解得到的子问题往往是不独立的。

3.动态规划算法求解步骤

1. 找出最优解性质，并刻画其结构特征
2. 递归地定义最优值
3. 自底向上求最优值
4. 构造最优解

4.基本要素：

• 最优子结构性质：问题的最优解包含子问题的最优解
• 子问题重叠性质：在递归法自顶向下求解问题时，每次产生的子问题并不总是新的问题，有些子问题被反复计算多次。

5.动态规划、递归、备忘录的区别

• 备忘录的递归方式是自顶向下的，动态规划的递归方式是自底向上的
• 备忘录与直接递归的控制结构相同，区别在于备忘录给子问题的解建立了备忘录，以备查看。

6.算法应用

• 矩阵连乘
• 最大字段和
• 最大公共子序列
• 0-1背包

第四章 ?贪心算法

1.基本思想：总是做出当前看来最好的选择

?????????? 即使贪心算法不能得到整体最优解，但最终结果却是最优解的很好的近似解

2.基本要素

贪心选择性质

所求问题的整体最优解可以通过一系列局部最优解的选择即贪心选择来达到。

• 最优子结构性质

一个问题的最优解包括子问题的最优解。

3.分治、贪心和动态规划

• 动态规划以自底向上的方式求解，贪心选择以自顶向下方式求解
• 贪心和动态规划都有最优子结构性质
• 背包问题可以用贪心算法，而0-1背包问题不能用贪心算法求解

4.算法应用

• 活动安排问题

结束时间早的优先

• 背包问题

为什么0-1背包用贪心算法不能求得最优解？

??? 主要原因在于无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。

????? 事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。

• 最优装载问题
• 哈夫曼编码问题

计算平均码长

• 单源最短路径问题（Dijkstra：设置顶点集合S，并不断地做贪心选择来扩充这个集合）
• 最小生成树问题

Prim和Kruskal算法

• 多机调度问题

第五章 ?回溯法

1.基本思想：以深度优先方式系统搜索问题解的算法

2.解题步骤：

1. 针对所给问题，定义问题解空间
2. 确定解空间结构
3. 以深度优先搜索解空间，并在搜索过程中剪枝

3.回溯法是一个既带有系统性又带有跳跃性的搜索算法。

4.特征：在搜索过程中动态产生问题的解空间。问题的解空间树是虚拟的，并不需要算法运行时构造一个真正的树结构，在任何时刻，算法只保存从根结点到当前扩展结点的路径。

5.扩展结点：一个正在产生儿子的结点。

6.活结点：一个自身已生成但儿子结点还没有全部生成的结点。

7.死结点：不能再向纵深方向移动的扩展结点。

8.避免无效搜索策略——剪枝函数

• 约束函数：用约束函数在扩展结点处剪去不满足约束的子树
• 限界函数：用限界函数剪去得不到最优解的子树。

9.算法框架

• 递归回溯和迭代回溯
• 子集树：当从n个元素的集合中找出满足某种性质的子集时，相应的解空间叫子集树，2^n个叶节点，总节点2^(n+1)-1。遍历时间O(2^n)
• 排列树：确定n个元素满足某种性质的排列时，相应的解空间树称为排列树,n!个叶节点。

遍历时间O(n!)

10.算法应用

• 装载问题

1. 解空间树：子集树
2. 右儿子剪枝：当前载重量+剩余集装箱重量<=当前最优载重量

• 0-1背包问题

1. 解空间树：子集树
2. 右儿子剪枝：当前结点处上界Bound

• 最大团问题

1. 解空间树：子集树
2. 右儿子剪枝：确认有足够多的可选择顶点使得算法有可能在右子树中找到更大 ?????

的团。

• n后问题

1. 解空间树：完全n叉树

• 图的m着色问题

1. 解空间树：完全m叉树(m为颜色数)

• 旅行售货员问题

1. 解空间树：排列树
2. 递归遍历

11.递归回溯（写代码）:

viod Backtrack(int t){

if(t>n)

?? Output(x);

else{

??? for (int i=f(n,t);i<=g(n,t);i++){

x[t]=h(i);

if(Constraint(t)&&Bound(t))

Backtrack(t+1):

第六章 ?分支限界法

1.基本思想：以广度优先或最小耗费（最大效益）优先的方式搜索解空间树，搜索过程中，每一个活结点只有一次机会称为当前扩展结点。活结点一旦成为扩展结点，就一次性产生所有儿子结点。

2.回溯法与分支限界法的异同

1. 求解目标不同：

回溯法更适合找出解空间树中满足约束条件的所有解；

分支限界法更适合找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

1. 对解空间搜索方式不同：

回溯法以深度优先方式搜索解空间树，每个活结点有多个机会成为扩展结点

分支限界法以广度优先或最小耗费优先方式搜索解空间树，每个活结点只有一次机会成为扩展结点，一旦成为扩展结点就一次性产生所有儿子结点。

1. 都是在问题的解空间上搜索问题解的算法

3.分支限界法算法框架

• 队列式分支限界法

将活结点表组织成一个队列，按队列先进先出的原则选取下一个结点为当前扩展结点。不搜索已不可行结点为根的子树，因为搜索时结点的处理是跳跃式的，所以无法递归。

• 优先队列式分支限界法

将活结点组织成一个优先队列，按优先队列式中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

4.算法应用

• 单源最短路径

1. 最小堆
2. 优先级是结点所对应的当前路长
3. 约束条件：一种是下界不小于当前最短路径则剪去以该节点为根的子树

另一种是利用结点间的控制关系进行剪枝。两条路径到达同一结点，剪去较长路径所对应的树中的结点为根的子树。

• 装载问题

• 队列式

1. 右儿子剪枝：当前结点对应重量+剩余集装箱重量<=当前最优解
2. 搜索到第一个叶结点之前，总有当前最优解为0，上式总成立，右子树测试不起作用。为确保右子树成功剪枝，应该在算法每一次进入左子树的时侯就更新当前最优值。

• 优先队列式

1. 优先级：从根结点到结点x的路径所相应的载重量再加上剩余集装箱重量之和。
2. 最小堆
3. 最优解的构造：需要保存已构造出的部分解空间树

• 0-1背包问题

1. 最大堆
2. 优先级：已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。
3. 上界：背包问题的最优解

• 最大团问题

1. 最大堆
2. 优先级：

??un(见上界)

1. 上界：

用变量cn表示与该结点相应的团的顶点数；

level表示结点在子集空间树中所处的层次；

cn +n-level+1作为顶点数上界un的值。

1. 算法的终止条件：遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。

• 旅行售货员问题

1. 最小堆
2. 优先级：堆中每个结点的子树费用的下界
3. 下界：

以剩余的所有顶点最小出边费用和作为依据。计算图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。

第七章 随机化算法

1.分类：

数值随机化算法：常用于数值问题的求解，得到的是近似解，精度随运行时间增加而提高；

蒙特卡罗算法：求问题的准确解；

拉斯维加斯算法：不会得到不正确的解；

舍伍德算法：总能求得问题的一个正确解。

2.产生伪随机数最常用的方法：线性同余法

a0=d

an=(ban-1+c) mod m n=1,2,3……

d称为种子，如何选取b、c和m直接关系到随机性能；

3.蒙特卡罗算法：高概率（1/2<p<1）给出正确解(p-1/2,算法的优势)，但无法判断具体解是否正确；对于同一个实例，不给出两个不同的正确解答称为该算法是一致的；（p231~233）

?

?

?