5. 贪心算法

每一步选择都是最优的局部解，最后发现是全局最优。

活动选择问题

很像最优二叉子树。选择一个中间的活动，然后求前后两段的最优解。实际上是一个动态规划问题。

但是没有必要动归。可以按照结束实际排序。子问题中，结束最早的肯定在最大兼容活动中；且s[i..k]为空。

所以用一个递归就可以解决；当然也可以用迭代来消除尾递归。

贪心算法的本质是通过一系列的选择来达到一个最优解。

贪心基本策略

贪心选择性质：

  1. 全局最优解，可以通过局部最优解的选择来达到。
  2. 最优子结构：如果最优解包含了子问题的最优解。称该问题具有最优子结构。

和动态规划的区别在于能否贪心地选择局部最优解。经典的例子就是0-1背包问题和分数背包问题。前者不可贪心，后者可以。

赫夫曼编码

考虑：

  1. 不能有前缀关系。也就是说，在构成搜索树的时候，所有的值必须在叶子节点上。这种编码称为前缀编码。
  2. 前缀编码可以直接连起来存在文件中。解析唯一。

编码二叉树：

  1. 最优编码总是满的二叉树。
  2. 恰有|C|个叶子和|C|-1个内部节点。

算法很简单，略。

有趣的是节点管理是用一个最小二叉堆来实现的。所以插入和换出的复杂度都是lgn。整个循环需要nlgn的时间。

正确性的证明：

  1. 贪心选择：最小的两个字符x，y，存在一种最优编码，二者长度相同，最后一位不同。（思路是找到一个最优的树，里面最深的两个点a，b，置换x，y和a，b）
  2. 替换x，y为z，构成新的字符集，生成一棵最优编码树；再替换回来，也是一棵最优编码树。

拟阵

非空集合和非空子集族（独立子集）组成的序对：

  1. 遗传性，子集肯定也在l里面
  2. 交换性，存在元素 B-A U A 也在l里面 ，注意存在即可！

扩张：加入元素之后保持独立性；最大：没有任何扩张称为最大的。

定理：最大独立子集一定是相同的；否则用交换性可以扩展出一个更大的。

加权拟阵：每个元素有权值；每个子集的权值为各个元素的权值之和。

6. 单源最短路

最短路径树，不一定唯一。

松弛：测试是否通过u，找到一条更短的到v的路径。

路径松弛定理：如果最短路是v[0,1,2,3…k]，沿v[0],v[1],v[2]。。。依次松弛，最终得到的v.d一定是最短路

Bellman-Ford算法

1
2
3
4
5
6
7
8
initlize-single-source(G, s)
for i=1 to |G.V|-1
	for each edge (u, v) in G.E
		RELEASE(u, v, w)
for each edge (u, v) in G.E
	if v.d > u.d + w(u, v)
		return false
return true

总结来说就是进行|V|-1次松弛，肯定可以松弛掉所有的点。

有向无环图

先求拓扑排序，然后依照顺序进行松弛，O(V+E)

Dijkstra算法

核心是分为确定的点和未确定的点；每次从未确定的点中找出最小值，松弛出边，并加入确定的点集。
性能主要看优先队列的实现，有insert（V）、extract-min(V)、decrease-key(E)三个操作。

7. 平摊分析

聚合分析

最坏情况下，n个操作的时间代价总和为T(n)，再求平均。
例子：multi_pop、二进制计数器

核算法

对不同操作赋予不同的费用，某些操作费用比实际多或者少。如果多了，差值作为信用（类似于银行里的存钱）。要求总存款大于0，即摊还代价总和大于实际代价。

比如栈的实际代价push为1，可以设摊还代价为0，pop或者multipop的摊还代价为0。push多了1个的信用是用来支付pop时候的代价的。

同理，计数器里，置1的时候摊还代价为2，用来支付将来置回0的操作。

势能法

势能和核算法很像。摊还代价为实际代价加上势能的增加量。

比如栈上的势能函数为栈的高度（元素个数），每次push操作，实际代价为1，势能增加1，所以摊还代价为2；pop的时候，势能减少1或者k，摊还代价为0.

计数器的例子，可以认为1的个数为势能。所以不管什么操作，摊还代价都是2.

动态表

很多数据结构，开始的时候并不知道需要分配多大的空间；所以当满的时候，扩容一倍；当只有1/4的时候，缩小一倍。我们看每次插入删除的平摊代价。

聚合分析：算期望的时间代价
核算法：每次插入支付代价为3：自己的插入；自己将来的插入；表中旧的元素的插入
势能： 2num(T) - size 大于1/2
size(T)/2 - num(T) 小于1/2

8. NP

确定性算法：
判断问题：
非确定性算法：

P类问题可以用多项式时间的确定性算法来进行判定或求解
NP类问题可以用多项式时间的非确定性算法进行判定或求解

哈密顿回路是NP问题，是因为给出一个排列，可以在n方的时间内判断是否合法。

问题的归约

问题A的输入转化为B的输入，B的输出再转化为A的输出。

比如配对问题，I’是一个排序问题，I是一个配对问题，两个排列中最小值与最小值配，次小值与次小值配，依次类推。所以I的方法是先将两个排列通过I’排序，再进行配对。

因为输入输出转化都是多项式的，如果排序本身是多项式的，那么配对算法一定有一个多项式的上界。由此给出定义：

  1. NP完全问题：NP类每一个问题都可以多项式转为NP的A问题，该问题为NP完全问题，NPC。NP问题包含P问题和NPC问题，但是NPC和P关系不定。有的NP问题甚至不能归到其中一类：线性规划问题、图的同构问题。
    2.NP难问题：NP问题都能转为该问题，但是这个问题本身不是被证明是NP问题。一般而言，NPC的判定问题，其对应的最优化问题为NPH问题。NPC属于NPH，只要属于NP就可以。

NPC问题的证明：

  1. 该问题属于NP问题，即可以找到多项式的验证算法。
  2. NP类的每一个问题都可以转化为该问题。

归约

如果一个问题A可以归约为问题B，那么A并不比B难。所以证明NPC的问题，如果已知一个问题A为NPC，那么A如果能归为B，那么B也是NP难；如果B再是NP,那么B就是NPC.

电路可满足性

（默认已经证明）判定一个电路是否是可满足电路是NPC问题。

NPC问题

3-CNF-SAT
团问题
顶点覆盖问题
哈密顿回路问题