唐代诗人杜甫的诗望岳:《算法设计与分析基础》笔记3

第八章 动态规划

计算二项式系数： C(n,k) = C(n-1, k-1) + C(n-1, k)。边界C(n,0) = C(n,n) = 1

Warshall算法：计算有向图的传递闭包，也就是任意两个顶点之间是否可达。R(i,j,k)表示i和j之间是否连通，其中中间节点在集合{1,2,...k}里面
那么R(i,j,k) = R(i,j,k-1) || (R(i,k,k-1) && R(k,j,k-1))

Floyd算法：计算每对顶点之间的最短路径。思路同上，只不过把布尔值换成最短距离而已。

最优二叉查找树：给定每个key出现的概率，构造一棵二叉查找树，使得平均比较次数最少。假设键值从小到大为a1,a2,...an, 对应的概率分别为p1,p1,...pn。令C[i,j]表示由节点i到j构成的子树中的最少查找次数，那么树根k一定在i,i+1,...j中，并且两棵子树都是最优的。
可以推知 C[i,j] = min { C[i, k-1] + C[k+1, j] } + Σp[i,...j]

背包问题：物品重w1,w2,...wn， 价值v1,v2,...vn， 背包承重W。令V[i,w]为前i个物品中，总重量不超过w的物品集的最大价值。这个物品集要么不包括i，要么包括i。
那么V[i,w] = max{ V[i-1, w], vi+V[i-1, w-wi] }
如果 w - wi < 0，那么就只有V[i, w] = V[i-1, w]
时间和空间效率都是O(nW)，求最优解的具体组成的效率为O(n+W)

第九章 贪婪技术

最小生成树的Prim算法：从任意顶点出发，每次将到当前子树距离最近的顶点添加进来。证明：用数学归纳法证明，Prim算法的每一步得到的子树必然是某个最小生成树的一部分。

最小生成树的Kruskal算法：每次添加一条不会导致回路的最短边。Kruskal算法需要用到不相交子集的表示和查找、合并算法，可以通过若干个链表来表示，也可以通过有根树表示，其中有根树可以通过路经压缩来提高效率。

Dijkstra算法：略

哈夫曼树：用于哈夫曼编码，加权路径长度，决策树


第十章 迭代改进

单纯形法：
标准型：1)最大化问题 2)所有变量非负 3)等式约束。
假设有n个变量和m个约束，那么n>=m, 最优解是这样的：其中n-m个变量取值为0，剩下的m个变量则不为0，称为基本变量。把m个方程进行恒等变换，每次变换的结果是这样的：有m个变量是基本的，这m个变量对应的系数矩阵是一个单位对角阵，也就是每个方程里只有一个基本变量的系数为1，其余基本变量的系数全部为零。每次变换，选择一个非基本变量，将它变成基本变量，同时将一个基本变量变成非基本的。一开始的时候，随机选择m个变量作为基本变量，并且把目标函数列在最后一行，但是把系数取反（为什么？）。每次变换的时候，选择目标行里系数为负的一个变量（通常选最负的那个），将它变为基本的，称之为主元。下面就是要找到变为非基本变量的那个变量：将每个方程的值，除以该方程主元的系数，选结果最小的那个，称为分离变量。想办法把分离变量对应的那一个方程的主元系数变成1，其余方程的主元系数变成0，目标行也跟着变。直到目标行的系数全部非负为止，目标行右边的值便是最优结果。


最大流：可以通过线性规划来解，每条边对应一个变量，满足容量约束和流量守恒约束。也可以通过增益路径法来解。假设边i->j的容量为5，已有流量3，那么将存在i->j的容量为2的增益路径，以及j->i的容量为3的增益路径。每次找到一条从源点到汇点的增益路径，并改变流量，直至不再有增益路径为止。但是如果增益路径选择不当的话，将会导致效率低下，可以通过“最短增益路径法”来避免这种情况。最短增益路径法就是找到源点到汇点最短的一条增益路径，使用的是广度优先搜索。

最大流最小割定理：网络中的最大流量等于它的最小割的容量。(注意：割的容量只包括从源侧到汇侧的边)
通过这个定理可以证明增益路径法得到的一定是最大流：在增益路径法结束时，从源点仍然有正流量可达的边组成了割的左侧，剩下的点为右侧。

二分图的最大匹配：顶点集V和U，边集E。假设已匹配的边为红色，未匹配的边为绿色。对于结果M的改进可以通过两种方法：1）找到一条连接两个自由顶点的边，涂成红色。2）找到一条简单路径连接V和U中的一个顶点，路径上的边交替为绿色和红色，然后将边的颜色取反，这样的路径称为增益路径。 当不存在增益路径时，得到的便是最大匹配。可以通过类似广度优先搜索的方法来找到增益路径。

稳定婚姻问题：一开始所有的n个男士和n个女士都是自由的。然后进行以下循环：任选一个自由男士m，找到自己的优先列表上的下一位女士w，m向w求婚，如果w是自由的则接收求婚，如果w已有配偶但是更喜欢m，则接收m，当前配偶变成自由人。 在不超过n^2次迭代之后，将得到一个稳定解。 缺陷：更容易满足男士的偏好。

第十一章 算法能力的极限

决策树：可以用来证明排序算法的下界，有序数组查找算法的下界

数值算法的挑战：两个基本相等的浮点数相减会导致较大的相对误差，称为减法抵消。
比如一元二次方程的求根公式 x = (-b +/- sqrt(b^2-4ac))/2a
当b^2远大于4ac时, 将会得到一个解为0, 相对误差为100%
解决方案：
if b>0， 那么 x1= (-b-sqrt())/2a 导致较大的相对误差，而x2=(-b+sqrt())/2a会
可以将x2写成另一种形式 x2 = 2c/(-b-sqrt())

第十二章 超越算法能力的极限

回溯法解8皇后问题：略

回溯法解哈密顿回路问题：略

回溯法解子集和问题：找到一个子集，使其中元素之和等于给定的数。终止条件：加入某个数值后超过了，或者剩下的全加起来都不够。

分支界限法：和回溯法类似，用于求解最优化问题。以最小化为例，对某个分支的下界做出一个判断，如果这个下界比当前已知某个解还要高，那么这个分支就不用探索了。关键在于如何选择一个有效的界限判断方法。与回溯法不同的是，分治界限法每次优先选择最有希望的那条分支来进行探索。

分治界限法解分配问题：将n个任务分配给n个人，使总代价最小。界限的确定：从剩下的人中选择每个人代价最小的任务，允许重复。

分支界限法解背包问题：考虑剩下的物体里性价比最高的，用该物体装满背包时的价值作为上界。

分支界限法解旅行商问题：对某个城市i，计算i到最近的两个城市距离之和的平均值si，那么总路程的下界为Σsi。假设已经探索了城市a,b,c...i, 那么新加进来的城市j的sj为：dij与j到剩下的城市里最近距离的平均值。 注意：为了减少工作量，可以之探索那些b在c之前的线路（能减少一半）。

NP困难问题的启发式算法
精确率的定义：最小化问题，精确率r为近似解除以精确解；最大化问题为精确解除以近似解。精确率总是一个大于1的值。一个c近似算法是指 r <= c 的算法。

旅行商问题的近似算法：
定理：若P != NP， 那么对任意 c >= 1, 都不存在一个c算法。

最近邻居法：总是选择到当前城市最近的城市。结果很差。
多片段启发算法：每次选择一条最短的边加进来，使得不产生回路也不产生分叉。结果较差。
二选法：从任意解开始，每次选取路径中不相邻的两条边，改变这四个顶点的连接方式。类似还有三选法，以及更复杂的Lin-Kernighan算法（目前最好的算法）。

欧几里德类型的旅行商问题：可以通过最小生成树来求近似解。
绕树两周算法：产生最小生成树，然后从任意顶点开始，绕着这棵树散步一周（深度优先遍历），然后从路径中去掉重复顶点（走捷径）。绕树两周是一个2近似算法。


Christofides算法：和绕树两周算法类似，并且利用了一笔画原理。先生成最小生成树，然后想办法把这棵树变成一个欧拉回路，做法就是成对连接那些连通度为技术的顶点，当然连接时应该选最短的边来连接。然后沿回路行走一圈并走捷径即可。是一个1.5算法。

旅行商问题的研究进展：最优解下界的估计，用线性规划来估计，忽略整数约束，称为Held-Karp下界，一般和最优解相差不到1％。 Concorde软件包，能够在1分钟之内对1000个城市求出精确解。

背包问题的近似解法
贪婪算法：选性价比最高的物品。精确率没有上界。
贪婪算法的改进：从两个解里选较好的一个，其中一个就是贪婪解，另外一个就是能够放进背包里的最值钱的单个物品。此算法的性能比为2。

解非线性方程的算法
以一元二次方程为例。

平分法：略

试位法：取两点连线与x轴的交点。

牛顿法：在初始值离精确解比较近时收敛非常快，取该点的切线与x轴的交点。
计算平方根常用此算法， x(n+1) = (xn + a/xn)/2