近似算法第二讲，主要讲了基于组合优化和贪心选择的近似算法，又主要以子集覆盖这个题目为重点。
序言：一上课老师好像很没有精神啊…应该是很难受，然后喝了点水之后开始讲。当时觉得好压抑啊，一下子觉得，老师生病影响讲课啦，一定要串课啊
[哈哈][哈哈]。还是觉得不应该自己勉强自己，自己难受，别人知道了也会很难受的。当然啦，自己要是能够装着OK，那也不错的！当然不是在责怪老师啦，其实很感动啦不过已经过了无脑感动的年纪了。
基于组合优化的近似算法
包含3个问题，分别是 顶点覆盖问题 ， 装箱问题 和 旅行商问题。以下分别叙述。
-
顶点覆盖 (The Vertex-cover Problem )
问题描述：
输入： 一个图 G（V，E）
输出：一个顶点集合C ， 该集合C满足两个条件:(1) 该集合中的顶点能够覆盖所有的边。（2）满足条件1的最小点集合。
可以形式化的描述条件1：
$\forall (u , v ) \in E , u \in C $或者 $ v \in C$ 或者 $ \{ u , v \} \supseteq C $
已经证明，这是一个NP完全问题。
我们基于组合优化给出近似算法：
近似算法描述：
-
任取图中一条边，将边中的两个顶点放入集合C中
-
将两个顶点所能cover的所有边从图中去掉
-
如果边不为空， 重复1
近似算法近似度： Ratio Bound = 2
证明关键：
-
设每次选择的边构成的集合为A ， A中的边必然是不邻接的 —— 因为每次找到一条边后，都把边的两个顶点所能cover的边全部去掉了，即去掉了所有邻接边。故以后加入的都不可能与其邻接。不邻接的结果就是，每条边的顶点都不会相同。
由上，我们知最后近似解的集合C与选择的边机A的大小关系： $|C| = 2 |A|$ 。
-
再考虑优化解集合$C^*$ ， 优化解是cover所有边的，所以必然cover边集合A；
又A中顶点都不相同，则A中每条边的顶点，至少有一个在$C^*$中。
即满足关系： $|A| \le |C^* \ $ -
由上，通过A ，就找到了优化解与近似解的关系，满足$\frac{|C|}{|C^*|} \le 2$
ratio bound = 2
-
-
装箱问题 （Bin-Packing Problem）
问题描述：
输入： （1） 体积依次为$a_1 , a_2 , \cdots , a_n \in (0,1]$的n个物品 (2) 无穷个体积为1的箱子
输出： 装箱方案，使所需箱子数最少
装箱问题是注明的NP完全问题。
实例： 将n中奖券印刷到一些具有标准尺寸的纸张上。归一化后就是装箱问题。
近似算法：
First-Fit算法：
-
依次处理每个物品
-
对每个物品，从前往后找已经装了东西的箱子，如果找到能够放下的箱子，则放入，更新箱子剩余容量；如果都找不到，则新开一个箱子放该物品。
近似比： ratio bound = 2
证明关键：
-
设优化解需要箱子个数为$k^*$ 。
优化解中需要的箱子数，与所有物品的体积和，必然满足： $k^* \ge \sum_{i=1}^{n}a_i$
-
近似解需要的箱子数为$k$ 。
由鸽洞原理，近似解中，至少$k-1$个箱子是超过半满的！ 否则，两个未超过半满的箱子物品可以合在一起。
则 $\frac{1}{2}(k-1)$是小于这$k-1$个箱子装的物品体积的，则也必然小于所有物品的体积，即有
$\frac{1}{2}(k-1) \lt \sum_{i=1}^{n}a_i$
-
由所有物品的体积和这一个桥梁，找到优化解与近似解的关系： $\frac{1}{2}(k-1) \lt k^*$
求出的实际结果为 ： $\frac{k}{k^*} \lt 2 + \frac{1}{k^*}$ ， 这里似乎直接忽略了后面的$\frac{1}{k^*}$项，取2。
故ratio bound = 2
-
-
旅行商问题（The Traveling-Salesman Problem , TSP）
问题描述：
输入 ： 一个完全无向图$G(V , E)$ ; 代价函数$C : E \to $ 非负整数集合 ， C满足三角不等式： $C(u,v) le C(u,w) + C(w , v)$
输出 ： 具有最小代价的哈密顿环。
哈密顿环，就是不重复经过所有顶点一次回到起点的环。
不满足三角不等式的TSP问题不存在具有常数Ratio Bound的近似算法，除非 NP=P 。
TSP问题是组合优化中一个NP-H问题，是NP完全问题。TSP在企划、物流、芯片制造中都有应用。可以使用线性优化来表示即求解。（即为每条边的权值乘以一个0/1系数，是该表达式最小。）
近似算法：
-
首先在完全无向图上选择一个起点，构建一个最小生成树。
-
先序遍历最小生成树，得到遍历序列。
-
按此序列访问，并最终回到起点，该路径即是TSP的近似解。
近似比： Ratio Bound = 2
证明关键：
-
从优化解$H^*$中去掉一条边，即得到一颗生成树$T^*$，该生成树代价必然大于等于最小生成树$T$代价。即
$C(T) \le C(T^*) \lt C(H^*)$
-
定义一个关于最小生成树的fullwalk，即在先序遍历最小生成树时，第一次访问节点和栈回退时的访问都算上，则该fullwalk W 代价为$C(W) = 2C(T)$ （因为会每条边会访问两次。）
-
我们将先序遍历的序列变为哈密顿环，即近似解$H$，就是将fullwalk的回退路径变为直线到达，连续应用三角不等式即可。即
$C(H) \le C(W) $
-
$C(H) \le 2C(T) \lt 2C(H^*)$ , 即 $\frac{C(H)}{C^*} \lt 2$
-
基于贪心选择的近似算法
-
最小并行时间调度问题 (Minimun Makespan Scheduling)
输入： 计算时间分别为$t_1 , \cdots , t_n$的n个任务； m台相同的机器。
输出： 最少并行时间。
是一个NP完全问题。
贪心思想： 每次选择具有最短任务队列的机器放入任务。
算法：
-
依次分配任务1到n
-
每次选择队列时间最短的机器，放入该任务，更新该机器的队列时间。
近似比： Ratio Bound = 2
证明关键：
-
优化解并行时间$T^* \ge \frac{1}{m} \sum_{i=1}^{n}t_i$ ，且
$T^* \ge t_i , i = 1 , \cdots , n$
的确是如此的。
-
设近似解$T$中最后一个任务为$t_h$，将会在第$j$台机器上执行。设其起始时间为$T_{start}$ ， 则近似解并行时间$T = T_{start} + t_h$ 。 其中$T_{start}$满足关系
$T_{start} \le \frac{1}{m} ( \sum_{i=1}^{n} t_i - t_h )$
则 $T \ge \frac{1}{m}( mT^* - T^* ) + T^*= 2T^* - \frac{1}{m} T^*$
为什么$T_{start}$满足这个关系： 因为$t_h$开始时其他任务还没有结束或者极端情况下同时结束，且这段时间内机器全部是连续处理没有空闲，故并行的起始时间是满足上述关系的。
-
-
集合覆盖
问题描述：
输入： 集合X ；集合X的子集族F。
输出：集族$C \subseteq F$，使得（1）$X = \cup_{S \in C}S$ （2）$|C|$最小
最小集合覆盖问题是很多实际问题的抽象。该问题是NP完全问题。
贪心选择： 每次选择能够包含未被覆盖元素最多的子集。
近似算法：
-
初始化包含所有未覆盖点的集合U，初始化近似解C
-
从子集族F中选择子集S ， 使得 $S \cap U$最大
-
将子集S添加到C中，从U中减去$S \cap U$
近似比： Ratio Bound 是$p(n)$的多项式近似算法，$p(n) = H(~ max({|S| | S \in F }) ~)$ , 其中$H(d) = \sum_{i=1}^{d}\frac{1}{i}$ (推论： 由不等式$H(d) \le \ln(d) $ , 有 H(max({|S| | S \in F})) \le H(|X|) \le \ln |X| + 1)
即是求近似解中包含的子集中，元素最多的集合的元素个数X，求其H（X）值。
证明 ：
没有看太明白。
-
-
边不相交路径覆盖问题
问题描述：
输入 ： 图$G(V , E)$ ， 源点集$S \subseteq V$ ，汇点集$ T\supseteq V$
输出 ： $A \subseteq S \times T $ , 满足（1）A中所有顶点对在G中存在无公共边的路径；（2）A最大。
NP完全问题。
贪心思想：每次选择$(u , v ) \in S \times T $使得该顶点对间路径最短。
近似算法：
-
初始全部候选解集合 $ C = S \times T$ ， 初始近似解集合$A = \emptyset$
-
从C中算出所有顶点对在图G中的最短路径集合P
-
从P中选择具有最小值的路径对应的顶点对$(u , v)$，将顶点对加入到A，将路径从G中移除。重复2，直到G中不再连通。
则求得的A即为近似解。
近似比：Ratio Bound 为 $O(\sqrt(m))$ ， 其中m为G中边数，即$m = |E|$
证明：
没有看太明白。
-