算法课程复习

最小生成树（MST/Minimum-cost Spanning Tree）

问题：任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通).

实现最小生成树的算法常用的是Prim,Kruskal。韩军老师W2PPT上只讲到了prim算法，W3讲了Kruskal算法。

MST就是一种贪心算法，每一步选择都是选取当前候选中最优的一个选择, 算法的证明省略。

`Prim`算法

基本思想

设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树， T的初始状态为T={u0}（u0∈V），TE={ }，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

伪代码
- (Prim)Algo_B算法：
 
 0: 初始化一个顶点集合VT和边权值集合ET
 1: 随机选择G中的一个顶点 U 放入VT,并将其标注为已加入(MST).
 2: 当G中有未加入顶点时：
 $\quad$\quad$ 在ET中 select G中已加入顶点和未加入顶点间权值最小的边(U, V); $\quad$\quad$ V标记为已加入, (U,V)标记为已加入;
 3: stop
 
 复杂度 $O(n^2)$
- (Prim)Algo_C算法：
0: 初始化一个顶点集合U，随机加入任一顶点 u_0; 初始化一个未加入顶点列表V_UN[N-1];
1: 初始化一个数组Light[N-1]存储未加入的每个顶点与已加入顶点之间的最短距离;
Light[i]表示第i个未加入顶点与已加入顶点的最短边距离
2: 当G中还有未加入顶点时：
$\quad$\quad$在Light[]里搜索最轻的边，如Light[k]; $\quad$\quad$在 U 中加入新顶点 k;
$\quad$\quad$在未加入顶点列表中删去 k，并记录新加入的边 (u,k); $\quad$\quad$通过比较Light[i]和weight(i, k)之间的大小更新Light[].
3:stop

`Kruskal`算法

基本思想

首先构造一个只含n个顶点(不含边，各顶点分别属于一个连通分量)的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，其中各个顶点都分别属于一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量(若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路)，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

Kruskal算法图示参考维基百科

伪代码

初始化一个空集U;
for 顶点 v in V;
$\quad$\quad$makeset(v); sort 集合 E 中的边 for edge (u, v) in E $\quad$\quad$if find_set(u) 和 find_set(v)不相同
$\quad$\quad$\quad$\quad$A = A$\cup${(u, v)}; $\quad$\quad$\quad$\quad$UNION(u, v);
return U;

C++代码实现如果天空不死最小生成树算法介绍

分治算法（Divide and Conquer）

概念：将原始问题分解为若干子问题，在逐个解决各个子问题的基础上，得到原始问题的解。

MINMAX(极小化极大)算法

问题

在一个整数组A[1…n1]中，同时寻找最大值和最小值。一种直接的算法如下面所示，它返回一个数对(x,y),其中是最小值，y是最大值。
直接求解

复杂度是 $2n-2$
分治方法求解

基本思想是在数组的每一半中寻找最大值和最小值，并返回两个最小值中的最小值和这两个最大值中的最大值。

复杂度是 $\frac{3n}{2}-2$.(注意：PPT上在这里有一个递推公式，最后推导后的结果是$\frac{3n}{2}-2$)

二分搜索（BINARYSEARCHREC）

问题

输入：按非降序排列的 n 个元素的数组 A [1,…,n] 和元素x.。输出：如果x = A[j] , 则输出j; 否则输出0。
分治法（递归）求解二分搜索问题

最坏情况下由递推式

\[\begin{aligned} C(n) &=1 & & \text { 若 } n=1 \\ & \leq 1+C(\lfloor n / 2\rfloor) & & \text { 若 } n \geq 2 \end{aligned}\]

推导得到算法所执行的比较次数不超过 $\lfloor logn \rfloor + 1$即算法时间复杂度为$O(\log{n})$.

PPT页码：Page.W3.96

分治法（非递归）求解二分搜索问题

算法需要比较次数和前面的递归相同，时间复杂度为 $O(\log{n})$

合并排序

问题介绍

给定一个待排序数组，先将其对半分成两个子数组分别进行排序，再将两个已排序的数组进行合并。
递归求解

算法复杂度为 $O(n\log{n})$

寻找第k小元素

问题介绍

输入 $n$ 个元素的数组 $A[1,…,n]$ 和整数 $k$, $1 \leq k \leq n$,

输出 $A$ 中的第 $k$ 小元素。

算法最坏情况下的复杂度为 $O(n)$

第k小元素分治算法求解

划分算法

划分(partition)算法思想是首先从无序数组中选出枢轴点 pivot (一般是数组的第一个元素)，然后通过一趟扫描，以 pivot 为分界线将数组中其他元素分为两部分，使得左边部分的数小于等于枢轴，右边部分的数大于等于枢轴（左部分或者右部分都可能为空），最后返回枢轴在新的数组中的位置。

中间需要 $n-1$ 次排序。

快速排序

利用了划分算法进行排序。

xxxx

算法的平均复杂度为 $O(n\log{n})$.

最坏情况下的复杂度为 $O(n^2)$

大整数乘法

问题介绍

计算两个 $n$ 位的整数(二进制)的乘法, 传统的乘法需要($n^2$)次数字相乘。

利用分治思想可以简化为 $O(n^{\log{3}})$。

$\begin{array}{l} \mathrm{uv}=\left(w 2^{\mathrm{n} / 2}+\mathrm{x}\right)\left(y 2^{\mathrm{n} / 2}+\mathrm{z}\right)=w y 2^{n}+(w \mathrm{z}+\mathrm{x} y) 2^{\mathrm{n} / 2}+\mathrm{xz} \end{array}$ 进一步通过转换可得： $\begin{array}{l} u v=w y 2^{n}+((w+x)(y+z)-w y-x z) 2^{n / 2}+x z \end{array}$ 这样对 $n/2$规模的乘法只需要进行3次乘法和6次加法运算。

矩阵乘法

传统的矩阵乘法时间复杂度为 $O(n^{3})$,

利用分治算法并没有提高运算效率！$T(n)=mn^3+an^3-an^2$，其中$a,m$分别表示加法和乘法的耗费。

STRASSEN 算法

算法的基本思想在于以增加加减法的次数来减少乘法次数.

时间复杂度由递推关系式可以导出为 $O(n^{\log{7}})$

博客介绍

凸包（快包）

首先，什么是凸包？

假设平面上有 $p_0,…, p_{12}$ 共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。

分治法的时间复杂度为$O(n\log{n})$.

更多介绍

减治算法(Decrease and Conquer)

减治法是一种一般性的算法设计技术，它利用了一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，我们既可以自顶至下(递归)也可以自底至上地运用它(非递归)。

减治法有3种主要的变种：

减一个常量，常常是减1(例如插入排序)。
减一个常因子，常常是减去因子2(例如折半查找)。
减可变规模(例如欧几里得算法).

欧几里得算法

gcd(m,n)=gcd(n, m mod n)

//mod求余符号

插入排序

插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 $O(n^2)$

实现思路是这样的：

认为第一个元素是排好序的，从第二个开始遍历。
拿出当前元素的值，从排好序的序列中从后往前找。
如果序列中的元素比当前元素大，就把它后移。直到找到一个小的。
把当前元素放在这个小的后面（后面的比当前大，它已经被后移了）。

拓扑排序

问题介绍

若用一个图来建模，它的顶点代表课程，有向边表示先决条件，该问题为：是否可以按照这种次序列出它的顶点，使得对于图中每一条边来说，边的起始顶点总是排在边的结束顶点之前，这个问题称为拓扑排序。
- 在余下的有向图中求出一个源，它是一个没有输入边的顶点。
- 然后把该源和所有从它出发的边都删除。（如果有多个这样的源，可以任意选择一个；如果这样的源不存在，算法停止，因为该问题是无解的）。
- 顶点被删除的次序就是拓扑排序的一个解。

生成排列

问题介绍

将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。
减治思路

该问题的规模减一就是要生成 {1…n-1} 的所有(n1)!个排列。假设这个较小的问题已经解决了，我们可以把 n 插入到n-1个元素的每一种排列中的n个可能位置中去，来得到较大规模问题的一个解
Johnson-Trotter Algorithm

如下：

算法复杂度$O(n \times n!)$

生成子集

和生成排列比较类似。用到减治的减一思想。

比特串方法

假币问题(减常因子的案例)

减常因子是减治方法的第二种主要变种：在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。（在大多数应用中，这个常数因子等于二）
折半查找假币(假币较轻)
复杂度为 $O(\log{n})$

俄式乘法

待补

约瑟夫斯问题

插值查找(减可变规模)

减可变规模是减治方法的第三种主要变种：算法在每次迭代时，规模减小的模式都和另一次迭代是不同的。

具体问题思路还不太清楚…?

时间复杂度 $O(logn)$.最差情况下是 $O(n)$.

插值查找

二叉查找树

介绍

是一种节点包含可排序项集合中元素的二叉树，每个节点一个元素，并使得对于每个节点来说，所有左子树的元素都小于树根节点的元素，所有右子数的元素都大于树根节点的元素。

在算法的每次迭代中，查找一棵二叉查找树的问题，简化为查找一棵更小的二叉查找树。显然，在二叉树的查找中，从一次迭代到另一次迭代，树的高度减少通常都不相同.

最坏的情况：树严重歪斜，时间复杂度$O(n)$, 平均时间复杂度为$O(\log n)$

变治（Transform and Conquer）

根据对问题实例的变换方式，变治思想有三种主要类型：

变换为同样问题的一个更简单或者更方便的实例—实例化简(Instance simplification)
变换为同样实例的不同表现—改变表现 (Representation Change).
变换为另一个问题的实例，这种问题的算法是已知的——问题规约(Problem reduction).

实例化简预排序

检验数组元素的唯一性。
模式计算

实例化简高斯消去法

LU分解

实例化简 AVL树

二叉查找树赢得了查找、插入和删除的时间效率，这些操作都属于Θ(lgn) 。但这仅仅在平均情况下成立，在最差情况下，这些操作属于O(n) ，因为这种树可能会退化成一种严重不平衡的树，树的高度等于n-1。

解决方案

AVL树（变治之实例化简）

一棵AVL树要求它的每个节点的左右子树的高度差不能超过1。（实例化简：红黑、分裂）

AVL树定义

一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么为0，要么为+1或者-1。

如果插入一个新节点使得一颗AVL树失去了平衡，则用旋转对此AVL树进行变换。
在最差情况下，查找和插入操作的效率属于O(log n)。
在平均情况下，查找一棵AVL树需要的比较次数和用折半查找查找一个有序数组是几乎相同的。

2-3树（变治之改变表现）

2-3 树允许一棵查找树的单个节点中不止包含一个元素。（改变表现）

2-3树是一种可以包含两种类型节点的树：– 2节点 – 3节点。

2-3树的效率

无论在最差情况还是在平均情况，查找、插入和删除的时间效率都属于 $O(\log n)$

堆排序（变治之改变表现）

霍纳法则（变治之改变表现）

二进制幂

问题规约

LCM(求解最小公倍数)

LCM—-»>gcd

计算图中的路径数量

0-1背包问题规约为线性规划问题

规约为—–»»»

思考最小生成树与`Element Uniqueness`规约问题

动态规划问题求解

阶段变量 表示分阶段去求解动态规划问题，阶段变量用 $k$ 表示，k=1,2,…,n

状态变量 表示每个阶段最初的情形或者说起始点位置，用状态变量 $s_k$ 表示，该变量具有无后效性 （这个阶段以后的过程演变就和这个阶段以前的状态和决策无关了，只和这个阶段的状态有关.）

决策变量 在每个阶段所确定的选择，也是从该状态(起始点)到下一阶段状态(起始点)的选择，决策变量用 $u_k(s_k)$ 表示。

状态转移方程 状态 $s_{k+1}$转变为状态 $s_{k}$的方程，记为 $s_{k+1}=T(s_{k}, u_k(s_k))$, T即 transform

阶段指标 每个阶段确定决策和选择后所产生指标变量值，记为 $v_k=V_k(s_k, u_k)$.

总的指标变量 记为$f_k(s_k)$，表示从第 $k$ 个阶段 $s_k$ 出发到最终结束点的最优指标。

最优策略 各个阶段的决策组成的序列，记为 $U_{kn}={u_k, u_{k+1}, …, u_{n}}$，表示从阶段 $k$ 到阶段 $n$ 的决策序列。

动态规划基本方程 $f_k(s_k)=min{V_k(s_k, u_k(s_k))+f_{k+1}(s_k)}$, k=1,2,3,…,N. 一般的有 $f_N(s_N)=0$

推论（Bellman 最优性原理）：如果 $U_{1N}$是针对动态规划问题的最优策略，则对任何 $1<k<N$，子策略都是以状态 $x_k$ 为起点， $x_N$ 为终点的最优策略。

动态规划最优化原理：

作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

最短路径问题

如图为一线路网络，现在要从起始点A到终点E，铺设线路，求使得总距离最短的铺管线路。两点之间的连线数字表示两点的距离。

解：

机器负荷分配问题

问题1

某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7;低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。

资源分配问题

设有某种资源，总数量为a，用于生产n种产品;若分配数量x;用于生产第i种产品，其收益为g(x)。问应如何分配，可使总收益最大?
背包问题

复合系统工作可靠性问题

设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有 x 个备用件时，其正常工作的概率为$p_i(x_i)$;每个部件 i 的备用件重量为 w ;，系统要求总重量不超过 W 。问应如何安排备用件可使系统可靠性最高?

设备更新问题

某运输公司购进一批卡车投入运营,公司每年初需对卡车作出更新或继续使用的决定。假设第k年中，$r_k(t_k)$ 表示车龄为 $t_k$ 的车使用一年的收入，$u_k{t_k}$ 表示车龄为 $t_k$ 的车使用一年的维修费用，$c_k(t_k)$ 表示车龄为 $t_k$ 的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。

排序问题

设有n个工件需要在机床A、B 上加工，每个工件都必须经过先A而后B的两道加工工序。以 $a_i , b_i$ 分别表示工件 i (1 $\leq $i $\leq$ n) 在A、B上的加工时间。问：应如何在两机床上安排各工件加工的顺序，使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？

可基于动态规划思想求解的问题与算法

计算二项式系数

最长公共子序列

矩阵链相乘

所有点对的最短路径问题

0/1背包问题

计算有向图的传递闭包

最优二叉查找树

最优二叉查找树：在查找中的平均键值比较次数是最低的。（集合中元素的查找概率是已知的）

回溯

任何难问题，均可通过穷尽搜索数量巨大但有限多个可能性而获得一个解。
大多数难问题都不存在用穷尽搜索之外的方法来解决问题的算法。
产生了开发系统化的搜索技术的需要，并且希望能够将搜索空间减少到尽可能的小。
组织搜索的一般技术之一是回溯法。这种算法设计技术可以被描述为有组织的穷尽搜索，它常常可以避免搜索所有的可能性。

基本思想

针对所要做的选择构造一棵所谓的状态空间树，树的每一层节点代表了对解的每一个分量所做的选择。
用深度优先法搜索状态空间树。
在状态空间树中的任一节点，满足一定条件的情况下，搜索回溯。

3着色问题

问题介绍

给出一个无向图G=（V，E），需要用三种颜色之一为V中的每个顶点着色，三种颜色分别为1，2和3，使得没有两个邻接的顶点有同样的颜色。我们把这样的着色称为合法的；否则，如果两个邻接的顶点有同一种颜色就是非法的。

4皇后问题

N皇后问题

哈密顿回路问题

哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

　　与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关.

分支定界

整数规划

分支定界的主要思想

一般来说，对于一个分支定界算法的状态空间树来说，只要符合下面任一条件，我们就会中止它的在当前节点上的查找路径：该节点的边界值不优于目前最佳解的值。该节点无法代表任何可行解， 因为它已经违反了问题的约束。该节点代表的可行解的子集只包含一个单独的点（因此无法给出更多的选择）。在这种情况下，我们拿这个可行解在目标函数上的值和目前求得的最佳解进行比较，如果新的解更好一些的话，就用前者替换后者。

TSP问题

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

分配指派问题

匈牙利法

最小网络花费流问题

问题介绍

该类设计问题的目标是，在一组节点之间设计一最小耗费的网络以满足所有的流量需求。

设G表示在n个点上的所有无向图的集合，g是该集合中的一个元素。

该问题就是要找到一个g $\in $ G，使得在满足给定的边容量限制的前提下，实现传输所有源节点到目的节点的流量需求所用的花费最小。

取消流量限制的子问题为SMST问题。

分支定界法和回溯法的不同

分支界限法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。
但在一般情况下，分支界限法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解。
由于求解目标不同，导致分支界限法与回溯法在解空间树 T 上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支界限法则以广度优先或以最小耗费优先的方式搜索解空间树 T。

分支界限法的搜索策略是，在扩展结点处，先生成其所有儿子的结点(分枝)，然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（界限），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分枝推进，以便尽快地找出一个最优解。
从活结点表中选择下一扩展结点的不同方式导致不同的分支界限法。最常见的有以下两种方式。
- 队列式（FIFO）分支界限法
- 优先队列式分支界限法

NP完备理论

NP理论介绍

p问题

这里P指代Polynomial。P问题是指能够在多项式时间内解决的问题，这意味着计算机能够在有限时间内完成计算。整数排序问题就是P问题，不管你是采用冒泡排序还是快速排序，也无论你是对于10个整数排序还是10亿个整数排序。
NP问题

NP指的是(Nondeterministic Polynomial)，即非确定性多项式时间。NP问题是指我们能够在多项式时间内验证一个解的问题。

对于一个问题，如果我们能够在多项式时间内解决，那么我们肯定也能在多项式时间内验证某个猜测是否为这个问题的一个解，因此P问题也属于NP问题，或者说P问题是NP问题的一个子集。
NP完全问题

PREVIOUSpytorch常用函数

NEXTZSL数据集属性划分