Download presentation
Presentation is loading. Please wait.
1
NPC问题与近似算法 林衍凯
2
Definition of NP-Completeness
定义: 如果一个问题Y可以通过调用问题X且通过poly-time的时间转化得到，我们称：
3
Definition of NP-Completeness
If X is P, then Y is P IF Y is NP, then X is NP
4
Definition of NP-Completeness
Example1： Independent Set & Vertex Cover IS: If there is IS of G in size of >=k VC: If there is IS of G in size of <=k
5
Definition of NP-Completeness
Observation: S V is IS if and only if V\S is VC of the graph G Conclusion： IS VC & VC IS
6
Definition of NP-Completeness
Example2： Vertex Cover Set Cover SC: Given a set U of elements,a collection M of subset of U S1,S2…Sn,and a integer k,ask if
7
Definition of NP-Completeness
8
Definition of NP-Completeness
定义： 如果问题X满足以下条件，那么X属于NPC。 对于任意
9
Reducibility of NP-Completeness
10
Reducibility of NP-Completeness
证明： The Clique Problem is Np-complete Show that a given clique can be checked in poly-time Show that 3-CNF-SAT Clique
11
Reducibility of NP-Completeness
令 为一个k子句的 3-CNF ，且 我们如何构建一幅图G(V,E)将图的团和3-CNF问题联系起来？
12
Reducibility of NP-Completeness
13
Reducibility of NP-Completeness
对于每个子句 ，我们在图中添加3个结点 ，如果结点 满足以下两个条件，就连边：
14
Approximation Algorithm
例1：Load Balancing Problem 问题描述： 给定ｎ个工作，工作ｊ需要时间tj，同时拥有m台机器。 定义机器i的负载为： 定义总负载： 目标：最小化总负载
15
Approximation Algorithm
近似算法1 每次任意选择一个未安排的工作，将它安排在当前负载最小的机器上 这是一个2倍近似算法
16
Approximation Algorithm
证明： 假设Mi 是负载最大的机器，工作j是机器i最后一个工作，我们有：
17
Approximation Algorithm
近似算法2 每次选择一个未安排的工作中用时最多的，将它安排在当前负载最小的机器上 这是一个1.5倍近似算法
18
Approximation Algorithm
例2：K-Center Problem 问题描述： 给定一张图G(V,E)满足 G 是metric 要求选择k个点作为图的中心 目标：最小化
19
Approximation Algorithm
近似算法1 每次假设图的radius（至多|E|个），然后执行以下算法: S=V C=empty While S!=empty choose an arbitary v in S CC+v 3. if |C|<=k succeed else increase radius
20
Approximation Algorithm
近似算法2 C1 ={v} v 为图中任意点 for i=2 to k choose vi s.t. Dist(vi,Ci-1) is largest CiCi-1+Vi
21
Approximation Algorithm
例3：Set Cover 算法：
22
Approximation Algorithm
例4：Weighted Set Cover 问题描述： Set Cover的加强，每个subset从花费都是1变为花费为Wi
23
Approximation Algorithm
近似算法 每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法 （Ps：Hn=1+1/2+1/3+…+1/n)
24
Approximation Algorithm
贪心近似算法 每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法 （Ps：Hn=1+1/2+1/3+…+1/n)
25
Approximation Algorithm
证明： 假设我们选择的subset为 根据我们算法选择subset的规则，我们有： 为第t次后未被覆盖的结点数）
26
Approximation Algorithm
证明（续）：那么我们有
27
Approximation Algorithm
例5：Edge Disjoint Path(EDP) 问题描述： 给定一个无向图G(V,E) 给定一组二元组T={(s1,t1),…(sk,tk)} 目标：寻找尽可能多的不相交道路使得这些道路起终点为给定二元组。
28
Approximation Algorithm
算法 网络流？ 不行网络流无法保证Si以Ti为终点 寻找近似算法
29
Approximation Algorithm
近似算法 repeat pick an index i s.t. the shortest path Pi from si to ti is shortest delete Pi from the graph THM：这个算法是一个 近似算法
30
Approximation Algorithm
例5：背包问题 算法：对于给定的常数c, k= 在改变价值的情况下用DP解决（polytime），得到Soltuion
31
Approximation Algorithm
在未改变的情况中选择Solution中的元素得到我们的近似解 THM：这是一个（1+c）近似算法
32
Thank you
33
Approximation Algorithm
更多的问题： 旅行商问题 最大割问题 斯特林树问题
Similar presentations
