算法分析与设计
考试题型及分值
一、选择题（共 9 小题，每小题 2 分，共 18 分）
二、判断题（共 5 小题，每小题 2 分，共 10 分）
三、填空题（共 6 小题，每空1分，共 14 分）
四、解答题（共 5 大题，共 58 分）
重点
动态规划（关键）
动态规划的要素（填空）：==最优结构，重叠子问题==
动态规划的原理、思想
多段图规划
0-1背包问题
贪心算法
和动态规划区别
最短路径：迪杰斯特算法！
Prim和Kruskal算法
回溯法
关于0-1背包问题的算法，思想
分支限界法！
随机算法（了解，什么时候使用）
第一章 基础知识+排序
一、背景
1.算法由操作、控制结构、数据结构三要素组成
2.算法是什么：问题的程序化解决方案
3.算法特征：有限性/有穷性：对算法的每一次输入，算法都必须在有限步骤（即有限
时间）内结束
- 算法与程序区别：
(1)一个程序不一定满足有穷性（操作系统）。
(2)程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
(3)算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
5.算法的描述（流程图、自然语言、程序语言、伪代码）
伪代码约定：利用i←j←e 来表示多重赋值，等价于 j←e 和i←j
6.算法的设计要求：
(1)正确性（对输入、输出和处理过程等有明确的无歧义的描述；有正确的输出结果并停止）
a) 不正确的算法：如果算法的错误率可以控制，也是有用的。
b) 程序调试不能证明程序无错误
(2)可读性
(3)健壮性（对于非法的输入数据，能适当地做出反应或进行处理(异常中断)）
(4)效率与低存储等需求
二、算法分析基础
1.算法分析的基本框架
(1)算法分析是指对一个算法所需要的资源进行预测，通常是对计算时间和空间的预测，采用随机存取机（RAM）计算模型。
算法运行时间是指在特定输入时，所执行的基本操作数。
输入数据的规模和分布是影响算法运行时间的两个主要因素。
对于大规模输入，通常只关注运行时间效率函数的增长率
度量算法效率的方法：
事后统计 事前分析估算 算法的存储量（输入数据所占、程序本身所占和辅助变量所占）
(2)空间复杂度：通常指辅助变量所占空间 （S(n)=O(f(n))）
若额外空间相对于输入数据量是常数，该算法原地工作，频度=重复
(3)时间复杂度：（嵌套最深层语句）
语句的频度之和构成运行时间。
对于规模为n的任何输入，一般考察算法的最坏运行时间
O(1)——常量阶 O(logn) ——对数阶 O(n) ——线性阶 O(nlogn) ——线性对数阶
O(n2) ——平方阶 O(n3) ——立方阶 O(nk)——多项式阶 O(2n) ——指数阶
==Ο是渐进上界，Ω是渐进下界。Θ需同时满足大Ο和Ω，称为确界(必须同时符合上界和下界)。Ο表示了最差性能==
三、算法设计策略：分治法
1.递归与分治法
分治策略: 将原问题划分为n个规模较小而结构与原问题相似的子问题,递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
2.归并排序算法：
① 分解：把n个元素分成各含n/2个元素的子序列；D(n)=Θ(1)
② 解决：用归并排序算法对两个子序列递归地排序；2T(n/2)
③ 合并：合并两个已排序的子序列以得到排序结果。C(n)=Θ(n)
3.分治法分析
D(n)分解时间 C(n)合并时间 T(n)是一个规模为n的问题的运行时间
总共层数是lgn+1层，每一层代价都是cn，所以总代价为：cn(lgn +1) =cnlgn+cn=Θ(nlgn)
第二章 排序
一、排序问题
稳定排序算法：相同的数据，排序后仍维持原有的相对次序
二、冒泡排序 & 选择排序
1.冒泡排序
基本思想：
① 比较相邻的两个元素。如果第一个元素比第二个大，就交换它们；
② 对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对，则最后的元素是最大的数；
③ 针对所有的元素重复以上的步骤，除了最后一个元素；
④ 重复步骤1~3，直到排序完成。
2.选择排序
基本思想：
① 初始状态：无序区为R[1..n]，有序区为空；
② 第i趟排序(i=1, 2, 3, …, n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n
）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1
个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录
个数减少1个的新无序区；
③ n-1趟结束，数组有序化了
n个记录的直接选择排序，可经过n-1趟直接选择排序得到有序结果
算法分析：唯一的好处是不占用额外的内存空间
三、插入排序 & 希尔排序
原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。一般来说，插入排序采用in-place基于数组进行实现
算法分析：插入排序的实现，通常采用in-place基于数组排序 (即只需O(1)的额外空间)，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 希尔排序（缩小增量排序）：优先比较距离较远的元素
先将整个待排序的记录序列，分割成为若干组待排序的子序列，分别进行直接插入排序。
出发点：插入排序在元素基本有序的情况下，效率很高。
gap：初始值设为 n/2，然后不断减半。
算法分析：希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。
四、快速排序 & 堆排序
1.快速排序（前面的比选定元素小，后面的大，然后对两边递归）
基本思想: 采用分治策略把未排序数组分为两部分，然后分别递归调用自身进行排序：
① 分解：数组A[p…r]被划分为两个（可能空）子数组A[p…q-1]和A[p+1..r]，使得A[p…q-1]中每个元素都小于或等于A[q]和A[q+1..r]中的元素。下标q在这个划分过程中进行计算；
② 解决：递归调用快速排序，对子数组A[p…q-1]和A[q+1..r]排序；
③ 合并：不需要任何操作。
如何防止出现最坏情况发生？
策略1：显示地对输入进行排列使得快速排序算法随机化
策略2：采用随机取样的随机化技术：从子数组A[p…r]中随机选择一个元素作为主元，从而达到可以对输入数组的划分能够比较对称
2.堆排序
(1)堆排序（Heapsort）是指利用堆该数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子结点的键值或索引总是小于（或者大于）它的父节点
(2)基本思想：
① 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
② 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn- 1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
③ 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
(3)堆数据结构是一种数组对象，可以被视为一棵完全二叉树。树中每个节点与数组中存放该结点值的元素对应。树的每一层都是填满的，最后一层可能除外（从一个结点的左子树开始填）
在堆排序算法中，如果使用大根堆，堆中最大元素位于树根；
小根堆通常在构造优先队列时使用
是一种in-place原地排序算法
堆排序算法与插入排序算法设计策略关系是否类似？
（减治法：不断减小被处理的问题规模）
五、线性排序算法 (计数排序、桶排序、基数排序)
比较排序：排序结果中各元素的次序基于输入元素间的比较，这类算法是比较排序。最好的时间复杂度为O(nlogn)
线性排序: 时间复杂度为 O(n)（突破了比较排序的最好时间复杂度）, 达到线性，排序不基于比较。
线性排序有三种：计数排序、桶排序、基数排序。
排序算法正确工作的必要条件：n个元素的n!中排列都要作为决策树的一个叶子。
定理1 任意比较排序算法在最坏情况下，都需要做Ω(nlogn)次比较。堆排序和合并排序是渐近最优的排序算法，快速排序执行效率平均较堆排序和合并排序好。
计数排序（不是比较排序算法）基本思想：对每一个输入元素x，统计出小于x的元素的个数。然后，根据这一信息直接把元素x放到它在最终输出数组中的位置上。
- 桶排序
基本思想：
- 把区间[0,1)划分成n个相同大小的子区间（称为桶）
- 将n个输入数分布到各个桶中去
- 先对各桶中元素进行排序，然后依次列出各桶中的元素
- 基数排序
假设所有待排序元素均为整数，至多d位。先按最低有效位进行排序，再按次低有效位排序，重复这个过程，直到对所有的d位数字都进行了排序。
基数排序关键是按位排序要稳定
总共花费O(d(n+k))的时间。如果 d是常数，k = O(n)，基数排序能在线性时间内完成排序
==六、排序算法比较==
1.比较排序：排序结果中，各元素的次序基于输入元素间的比较，这类算法成为比较排序。
任何比较排序算法，排序n个元素时至少耗用Ω(nlgn)次比较，其时间复杂度至少为Ω(nlgn)
2.当数据规模n较小时，n2和nlog2n的差别不大
当文件的初态已基本有序时，可选择简单的排序方法,如直接插入排序或起泡排序等
当数据规模n较大时，应选用速度快的排序算法
快速排序法最快，被认为是目前基于比较的排序方法中最好的方法当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，则快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)
插帽龟，统计鸡走的稳（希尔快速选择堆不稳）
选帽插，全恩方，冒插最好没有方
统计鸡，加减乘除
恩老哥，快归堆
快桶最坏是恩方
第三章 递归和分治策略
一、 递归的定义、总体思想、特点；
1.递归(Recursion)基本思想：把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数直接或间接调用它自身的情况。这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况
- 总体思想：如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。（自底向上）
3.两个要素：边界条件、递归函数
二、 通过具体例子理解递归策略与设计（ N的阶乘、Fibonacci数列、全排列、整数划分问题、Hanoi塔问题）
1.N的阶乘：
n! = 1(n=0) n=0
n(n-1) n>0
2 Fibonacci数列
F(n)= 1 n=0
1 n=1
F(n-1)+F(n-2) n>1
3.全排列 ：(从n个元素中取出m个元素进行排列)
4. 整数划分问题
q(n****，m)= 1 m=1,n=1
q(n,n) n<m
q(n****，m)=1+q(n,n-1) n=m
q(n,m)=q(n,m-1)+q(n-m,m) n>m>1
**n:**待拆分的整数 m：拆分出的最大值不超过m
5. Hanoi塔问题:
第n-1个盘子由a移到c；第n个盘子由a移到b；第n-1个盘子由c移到b；
public static void hanoi(int n, int a, int b, int c)
{
if (n > 0)
{
hanoi(n-1, a, c, b);
move(a, b);
hanoi(n-1, c, b, a);
}
}
三、 分治法的概念、步骤、复杂度分析；
使用条件：
(1)问题的规模缩小到一定的程度就可以容易地解决
(2)分解为若干个规模较小的相同问题，**==具有最优子结构==**
(3)分解出的子问题的解可以合并为该问题的解
(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
如果具有前两个特征未有第三个可以考虑动态规划和贪心算法
分治法基本步骤
==① 分解② 解决③ 合并==
平衡子问题：最好使子问题规模大致相等
divide-and-conquer(P)
{// P****是问题的规模，n0是阈值
if ( |P| <= n0) adhoc(P); // 基本子算法，解决小规模的问题
divide P into smaller subinstances P1,P2,…,Pk****；// 分解问题
for (i=1; i<=k; i++) // k****通常为2
yi=divide-and-conquer(Pi); // 递归的解各子问题
return merge(y1,…,yk); // 将各子问题的解合并为原问题的解
}
**3.**优缺点
能简单地求解复杂的问题
并行性 (并行计算、多处理器系统)
内存访问 (利用内存缓存机制，不需要访问存取速度较慢的主存)
分治法不能适应于所有问题
递归的效率较慢 (具体的实现方式)
分治法比迭代方法更复杂 (例子：n个数求和)
四、 通过几个范例学习分治策略的设计技巧（二分搜索、归并排序、乘法问题、找最大最小值问题、循环赛日程表等）
1. 二分搜索（最坏情况下时间复杂性为O(logn)）
应用场景及局限性
o 二分查找依赖顺序表结构，如数组
o 二分查找针对的是有序数据
o 数据量太小太大不适合二分查找
public static int binarySearch(int [] a, int x, int n)
{
// 在 a[0] <= a[1] <= … <= a[n-1] 中搜索 x
// 找到x时返回其在数组中的位置，否则返回-1
int left = 0; int right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; // 未找到x
}
2. 归并排序
将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序
3. 乘法问题
(1) 整数相乘问题【分治法：O(n1.59)】
(2) 矩阵相乘问题【分治法：O(n2.81)】
- 最大最小值问题
- 循环赛日程表
第四章动态规划
一、 理解动态规划算法的由来、概念、定义
1.多阶段决策过程（最优决策序列）：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关
- 多阶段决策问题的求解策略（枚举法、动态规划（最优化原理、多阶段->单阶段））
- 最优决策序列性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
4.状态无后效性（马尔科夫性）未来与过去无关
5.多阶段决策模型：自然状态、策略、益损值（准则函数/指标函数）
6. 动态规划求解问题的前提：最优性原理（前提）、递推关系式与边界条件。
- 动态规划的设计技巧：阶段划分、状态表示、存储表
- 动态规划法的优缺点
与非线性规划相比，动态规划的优点：
（1）易于确定全局最优解。把原问题化为一系列结构相似的最优化子问题
（2）能得到一簇解
（3）动态规划方法反映了过程逐段演变的前后联系
不足之处：
（1）没有一个统一的标准模型可供应用。
（2）应用的局限性。状态变量要满足“无后效性”条件
（3）在数值求解中，存在“维数障碍”。每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。
==基本思想==
动态规划的思想实质是分治思想和解决冗余
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
但是经过分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
三、掌握动态规划算法的要素：
✓ ==最优子结构==（自底向上）：最优解是由其子问题的最优解来构造的，则具有最优子结构。
动态规划算法问题解的代价 = 子问题的代价 + 选择带来的开销
与贪心算法的不同：贪心算法适用的问题也具有最优子结构，但它是先做选择再求解一个结果子问题（自顶向下）
利用反证法判断问题满足最优性原理，不能应用最优子结构的时候，不能假设它能够应用
✓ ==重叠子问题==（子问题的空间小、不被反复计算）
自顶向下的做备忘录算法：为每一个子问题的解在表中记录一个表项
如果某些子问题没有必要求解，做备忘录方法具有只需要求解那些肯定要求解的
子问题的优点。
四、掌握设计动态规划算法的步骤
① 划分子问题：找出最优解的性质，并刻划其结构特征。
② 最优解的递归式：递归地定义最优解的值。
③ 按自底向上的方式计算最优解的值。
④ 由计算出的结果构造一个最优解。
四、通过范例学习动态规划算法的设计策略
**1.**矩阵连乘
2. 最长公共子序列（LCS）
2. 多段图规划
3. 最大子段和
4.0-1****背包
5. 备忘录动态规划算法
第5章 贪心算法
相关概念
最优化问题
最优化问题求解分类：根据描述问题约束条件和目标函数的数学模 型的特性和问题的求解方法的不同，可分为：线性规划、整数规划 、非线性规划、动态规划、分支限界法等精确算法。
贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些 问题方便地求解，属于近似算法。
最优子结构性质：
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
贪心算法
贪心选择不一定等于整体最优解：由问题是否具有贪心选择性质决定
==基本思想：==
从问题的某一个初始解出发，通过一系列的贪心选择，即当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。
在贪心算法(Greedy Method)中采用逐步构造/分级最优解的方法 。在每个阶段，都作出一个按某个评价函数最优的决策，该最优 评价函数称为贪心准则(Greedy Criterion)
==基本步骤：==
① 决定问题的最优子结构；
② 设计出一个递归解；
③ 证明在递归的任一阶段，最优选择之一总是贪心选择, 那么做 贪心选择总是安全的。
④ 证明通过做贪心选择，所有子问题(除一个以外)都为空, 即只产 生一个子问题。
⑤ 设计出一个实现贪心策略的递归算法。
⑥ (性能角度) 将递归算法转换成迭代算法。
贪心策略设计：
策略1：按价值最大贪心，是目标函数增长最快。
策略2：按重量最小贪心，使背包增长最慢。
策略3：按价值率最大贪心，使单位重量价值增长最快。
==贪心算法 vs 动态规划==
贪心算法和动态规划算法都要求问题具有最优子结构性质，但是两者 存在着巨大的差别。
(1) 动态规划是先分析子问题，再做选择。而贪心算法是先做贪心选择，做完选择后，生成了子问题，然后再去求解子问题；
(2) 动态规划每一步可能会产生多个子问题，而贪心算法的每一步只会产生一个子问题；
(3) 从特点上看，动态规划是==自底向上==解决问题，而贪心算法则是==自顶向下==解决问题。
可解决问题：
活动安排问题、小数背包问题、最优装载问题、找钱问题、单源最短路径、最小生成树
==最小生成树—Prim算法==
==最小生成树—Kruskal算法==
时间复杂度：==O(Elog E)== V为顶点数，E为边数
当 E>V^2^ 时，Kruskal算法比Prim算法差；
当E<V^2^ 时，Kruskal算法却比Prim算法好得多。
==单源最短路径–迪杰斯特拉(Dijkstra)算法==
==基本思想==：设置顶点集合S并不断地作==贪心选择==来扩充这个集合。 一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
第6章 回溯法
方法概述
定义：
回溯法 (Backtracking) 又称为试探法： — 回溯法是一个既带有**==系统性==又带有==跳跃性==**的搜索算法；
— 它在包含问题的所有解的解空间树中，按照深度优先的策略，从 根结点出发搜索解空间树。—— 系统性
— 算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索， 逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略 进行搜索。——跳跃性
— 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法， 它适用于解一些组合数较大的问题。许多复杂的、规模较大的问题都可以使用回溯法，有“通用解题方法”的美称
二叉树遍历方法
方法：
二类常见的解空间树：
子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时。子集树通常有2 ^n^个叶子 结点，其总结点个数为2 ^n+1^ -1，遍历子集树时间为==Ω(2^n^ )== 。
排列树：当所给问题是确定n个元素满足某种性质的排列时。排列树通常有n!个叶子结点，因此，遍历排列树需要==Ω(n!)==的计算时间。例如TSP
可以解决的问题：
排列生成问题：给定正整数n，生成1, 2, …, n所有排列
TSP问题：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。
n皇后问题：在n*n棋盘上放上n个皇后，使皇后彼此不受攻 击，即条件是彼此不在同行(列)、斜线上。求出全部的放法。
0-1背包问题、符号三角形问题
图的m着色问题：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。
回溯法效率分析
子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时。子集树通常有2 ^n^个叶子 结点，其总结点个数为2 ^n+1^ -1，遍历子集树时间为==Ω(2^n^ )== 。例如0-1背包问题
排列树：当所给问题是确定n个元素满足某种性质的排列时。排列树通常有n!个叶子结点，因此，遍历排列树需要==Ω(n!)==的计算时间。例如TSP
通过上述实例的讨论，回溯法的效率在很大程度上依赖于以下因素：
(1) 产生x[t]的时间；（生成解空间的时间）
(2) 满足显约束的x[t]值的个数；
(3) 计算约束函数constraint的时间；
(4) 计算上界函数bound的时间；
(5) 满足约束函数和上界函数约束的所有x[k]的个数。
好的约束函数能显著地减少所生成的结点数，但这样的约束函数往 往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
第7章 分支限界法
方法概述
与回溯法区别：
求解目标不同： 一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解， 而分支限界法的求解目标则是尽快地找出满足约束条件的一个解；
搜索方法不同： 回溯法使用深度优先方法搜索，而分支限界一般用宽度优先或最佳优先方法来搜索；
对扩展结点的扩展方式不同： 分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成 为扩展结点，就一次性产生其所有儿子结点；
存储空间的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法解决问题成功的可能性更大。
==基本思想==：
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜 索问题的解空间树。i) 对已处理的各结点根据限界函数估算目标 函数的可能取值，ii) 从中选出目标函数取得极大(极小) 值的结 点优先进行广度优先搜索, iii) 不断地调整搜索方向，尽快找到 解，裁剪那些不能得到最优解的子树以提高搜索效率。
求解步骤：
① 定义解空间(对解编码)；
② 确定解空间的树结构；
③ 按BFS等方式搜索：
a. 每个活结点仅有一次机会变成扩展结点；
b. 由扩展结点生成一步可达(即宽度搜索)的新结点；
c. 在新结点中，删除不可能导出最优解的结点； // 限界策略
d. 将剩余的新结点加入活动表(队列)中；
e. 从活动表中选择结点再扩展； //分支策略
f. 直至活动表为空；
常见的两种分支限界法：
**==队列式 (FIFO)分支限界法==**：从活结点表中取出结点的顺序与加入 结点的顺序相同，因此活结点表的性质与队列相同；
==优先队列(代价最小或效益最大)分支限界法==：每个结点都有一个对 应的耗费或收益，以此决定结点的优先级
具体方法：
分支限界法首先确定一个合理的限界函数，并根据 限界函数确定目标函数的界[down, up]；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点 的目标函数的可能取值 (注意：对于最小化问题，估算结点的down，对最大化问题，估算结点的up)。 如果某孩子结点的目标函数值超出目标函数的上界或下界，则将其丢弃(即基于该结点生成的解不会比目 前已得的更好)，否则入待处理表。
第8章 随机算法（了解，什么时候使用）
概述
随机算法是指在算法中执行某些步骤或某些动作时，所进行的选择 是随机的。
三要素：输入实例、随机源和停止准则。
特点：简单、快速和易于并行化。
常见的随机算法分为4类：
① 数值随机化算法：常用于数值问题的求解，所得到的往往是近似解， 近似解的精度随着计算时间增加而不断提高；
② 蒙特卡罗算法：用于求问题的准确解。对于许多问题来说，近似解毫 无意义或者不存在。该方法总能得到问题的解，但该解未必是正确的 。求得正确解的概率依赖于算法所用的时间。难以判断解是否正确；
③ 拉斯维加斯算法：不会得到不正确的解，但是有时会找不到解。找到 正确解的概率随着所用的计算时间的增加而提高。对任一实例，反复 调用算法求解足够多次，可使求解失效的概率任意小； 核心思想：随机生成答案并检测答案正确性。
④ ==舍伍德算法==：总能求得问题的一个解，且所求得的解总是正确的。当 一个确定性算法最坏情况下的计算复杂性与其在平均情况下的计算复 杂性有较大差别时，可在这个确定性算法中引入随机性将它改造成一 个舍伍德算法，消除或者减少这种差别。核心思想：设法消除或减少最坏情况与特定实例之间的关联性。利用随机算法改造已有算法，使 得算法的性能尽量与输入数据无关，即平滑算法的性能。
==随机算法应用==
1.多种洗牌算法
2.s-t连通性：无向图G = (V,E), s, t为G上两点。令n = |V|， m = |E|。希望确定是否存在一条连接s和t的路。S到T有路吗？
随机算法：从s开始随机游动，如果在4n^3^步之内到达t，则返 回存在一条路；否则，返回不存在路。
3.最小割随机算法：每次随机选一条边，合并该边对应的顶点。 重复该过程n-2次。最后剩下两点之间的边，就是一个割集。
第9章 NP完全性理论
（感觉非重点，选择判断填空）
相关概念
Polynomial Time (多项式时间)
定义：一个称为多项式时间的算法(Polynomial-time Algorithm) 必须 符合：在合理的输入大小 (input size)下，该算法在最差情況 (Worst-case)的时间复杂度以==多项式函数==为限。
Intractability (难解问题)
在计算机科学领域，若無法在==最差情況==(Worst-case)下，以多项式时 间的算法來解决某个问题，则该问题被称为难解 (Intractable)问题
✓ 一个难解的问题，必須沒有任何多项式时间的算法可以解它
Deterministic Algorithm (决定性算法/确定性算法)
定义: 这类算法在做任何事时，该算法的下一步只有一件事可以做。 (Permitting at most one next move at any step in a computation)
✓ 是指算法中每一个步骤的运算都需要被唯一定义，因此产生的结果也是 唯一的。
✓ 能夠执行决定性算法的机器，称为决定性的机器 (Deterministic Machine)。电脑就是一种决定性的机器。
图灵机
P 、NP及NPC类问题
P 、NP及NPC定义
==P类问题==：一类问题的集合，对其中的任一问题，都存在一个确定型图灵 机M和一个多项式p，对于该问题的任何(编码)长度为n的实例，M都能在 p(n)步内，给出对该实例的回答。即：==多项式时间内可被解决的问题==
==NP类问题==：一类问题的集合，对其中的任一问题，都存在一个非确定型 图灵机M和一个多项式p，对于该问题的任何(编码) 长度为n的实例，M都 能在p(n)步内，给出对该实例的回答。==多项式时间内可验证问题(指验证其解的正确性)==
多一归约：假设L1和L2是两个判定问题，f将L1的每个实例I变换成L2的实 例f(I)。若对L1的每个实例I，I的答案为“是”当且仅当f(I)是L2的答案为 “是”的实例，则称f是从L1到L2的多一归约，记作L1 ≤ mL2 (传递关系) 直观意义：将求解L1的问题转换为求解L2的问题，而问题L1不会难于L2
==多项式时间多一归约==：若f是多项式时间可计算，则上述归约称为多项式 时间多一归约，也称多项式时间变换。记作：
==NPC问题==：对于一个(判定性)问题q，若 (1) q ∈ NP; (2) NP中任一问题均可 多项式时间多一归约到q，则称问题q为NP-完全的(NP-complete，NPC)
==NP-hard问题==：若问题q仅满足条件(2)而不一定满足条件(1)，则问题q称 为NP-难的(NP-hard，NPH)。显然：NPC ⊆ NP-hard
==P、NP、NPC和NP-hard之关系==
NP完全问题的求解
方法
减少搜索量：
简单算法是穷举搜索，时间为指数
减少搜索量：分枝限界法，隐枚举法、动态规划等。可以提高效率， 但时间复杂度不变
优化问题
降低优化要求，求近似解，以得到一个多项式时间的算法。即：找 寻在容许的时间内得到容许精度的近似最优解的算法
==近似算法==
近似算法放弃求最优解，用近似解代替最优解，以换取算法设计 上的简化和时间复杂性的降低。
近似算法通常采用两个标准来衡量性能：
✓ 算法的**==时间复杂性==**
✓ 解的==近似程度==
• 近似比 • 相对误差λ • 相对误差界ε(n)