大家好，欢迎来到IT知识分享网。
一、归约
Reducing A(已知的） to B（要证明的）
难点：转换函数f(x)的设计必须要保证问题B的输出结果和相应的问题A上的答案保持一致。
可视化归约
即A<=B ，B比A难，如果B能解决，即知道B的解集，那么A一定可以被解决。
二、基本归约
-
简单的恒等归约：比如最大独立集和最小点覆盖。
（最大独立集）
概念：在n个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。
性质：顶点数 = 最大独立集 + 最小点覆盖
说明：最小点覆盖的相反就是最大独立集。
（最小点覆盖）
概念：用最少的点，让每条边都至少和其中一个点关联
性质：最小点覆盖 = 最大匹配
说明：在二分图中，求出了最大匹配后，容易得出，合理分配最大匹配的点去覆盖，未匹配的点一定与覆盖的的某个点有边。
（最小边覆盖）
概念：用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点
性质：最小边覆盖 = 顶点数 – 最小点覆盖
说明：二分图中，最大匹配为m，未匹配的点为x，则总点数n = 2 * m + x，未匹配的点需要x条边去关联x个点，则覆盖边至少为m + x，满足“最小边覆盖 = 顶点数 – 最小点覆盖”。
二分图中的最大独立集，最小点覆盖，最小边覆盖概念 – SummerMingQAQ – 博客园
显然最小点覆盖{2, 3, 7}恰好跟最大独立集 {1, 4, 5, 6}互补。
这是因为在independent set中，任意2个结点<u,v>都不会有一条边相连，所以与u,v相连的结点一定在集合外面，所以independent set的补集一定是vertex cover的。
2. 从特殊情况到一般情况：比如 顶点覆盖 ≤p 集合覆盖。
最小顶点覆盖问题：
（最少的点覆盖所有的边)
是否存在V的一个最小的子集V’，使得|V’|<=|V|，并且G中的每条边e，至少有一个顶点在V’中？
最小集合覆盖问题：
并且这n个集合的并集恰好等于A集合，即：B1UB2UB3U…UBn=A。
step1.找到类比，
问题
最小顶点覆盖问题（已知）<= 最小集合覆盖问题（要证明的）
对象
最小顶点覆盖问题中的 边 —–最小集合覆盖问题中的 元素
最小顶点覆盖问题中的 点——最小集合覆盖问题中的 子集合
目的
覆盖所有边—-覆盖所有元素
输入
一些点–一些子集合
输出
这些点是否覆盖所有边–这些子集合是否覆盖所有元素
step2. 以A问题的输入构造B问题的输入
3. 要求掌握同一个问题的最优问题如何多项式时间归约到该问题的判断问题（自身归约）；
三、NP和NPC
1. 证明方法
证明NP问题。
这个容易，即给你一个结果，你能在polynomial的时间内验证该结果的正确性。
NP(non-deterministic polynomial-time)
证明NP-hard问题。
我们要证明一个问题是NP-hard的时候，我们通常要做的是找到一个已被证明了的NPC问题，并把这个NPC问题归约到该问题上去（即NPC<=NP-hard）。即比NPC更难求解
证明NP-Complete问题。
所有的NP问题都可以规约到SAT(即NP<=SAT)，也就是说SAT至少与NP问题一样难，或者如果解决了3SAT问题，所有的NP问题就解决了。
2. NP-Complete间的规约例子
1. 3SAT<=Independent Set
2.Vertex Cover <=Independent Set
9. Independent Set <= Clique problem
3. 证明一个问题是NP-hard
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/125092.html
