---
layout: post
title: 算法设计与分析-课后总结8
date: 2015-10-26
categories: 笔记
tags: 算法
onewords: 第十二节课继续讲近似算法。
---
> 近似算法第二讲，主要讲了基于组合优化和贪心选择的近似算法，又主要以子集覆盖这个题目为重点。
> 序言：一上课老师好像很没有精神啊...应该是很难受，然后喝了点水之后开始讲。当时觉得好压抑啊，一下子觉得，老师生病影响讲课啦，一定要串课啊~~[哈哈]\[哈哈\]。还是觉得不应该自己勉强自己，自己难受，别人知道了也会很难受的。当然啦，自己要是能够装着OK，那也不错的！当然不是在责怪老师啦，其实很感动啦~~ 不过已经过了无脑感动的年纪了。
### 基于组合优化的近似算法
包含3个问题，分别是 顶点覆盖问题 ， 装箱问题 和 旅行商问题。以下分别叙述。
1. 顶点覆盖 (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完全问题。
我们基于组合优化给出近似算法：
近似算法描述：
1. 任取图中一条边，将边中的两个顶点放入集合C中
2. 将两个顶点所能cover的所有边从图中去掉
3. 如果边不为空， 重复1
近似算法近似度： Ratio Bound = 2
证明关键：
1. 设每次选择的边构成的集合为A ， A中的边必然是不邻接的 —— 因为每次找到一条边后，都把边的两个顶点所能cover的边全部去掉了，即去掉了所有邻接边。故以后加入的都不可能与其邻接。不邻接的结果就是，每条边的顶点都不会相同。
由上，我们知最后近似解的集合C与选择的边机A的大小关系： $\|C\| = 2 \|A\|$ 。
2. 再考虑优化解集合$C^*$ ， 优化解是cover所有边的，所以必然cover边集合A；
又A中顶点都不相同，则A中每条边的顶点，至少有一个在$C^*$中。
即满足关系： $\|A\| \le \|C^*|\ $
3. 由上，通过A ，就找到了优化解与近似解的关系，满足$\frac{\|C\|}{\|C^*\|} \le 2$
ratio bound = 2
2. 装箱问题 （Bin-Packing Problem）
问题描述：
输入： （1） 体积依次为$a\_1 , a\_2 , \cdots , a\_n \in (0,1]$的n个物品 (2) 无穷个体积为1的箱子
输�
