这礼拜的内容好像可以在期末考考古题找到一些参考资料 由於大家对reduce的工作不熟悉 所以先说明reduce Reduction是甚麽? Ti演算法 给A的input ----------> 给B的input | | A | B | 演 | 演 | 算 | 算 | 法 | 法 | V To演算法 V 给A的output <---------- 给B的output A,B是两个不同的问题,原本的情况应该是如此: A问题输入A的input用A演算法可以得到A的output B问题输入B的input用B演算法可以得到B的output 假如说A can be reduced to B.(以上的关系图) 意思是解决A问题的方法变成(黄色路径): A问题输入一组input用Ti演算法转变成B问题的input 使用B演算法算出B的output 将B的output用To演算法转变成A问题的output p.s.实际上A,B演算法是甚麽不重要,而且跟reduction无关 只要知道A,B的output所具备的特性是甚麽就好 说明这件事情是对的必须要具备条件 1.找出Ti,To演算法 2.证明Ti,To演算法在多项式时间之内 3.证明Ti,To演算法是对的 以下是这礼拜的问题 -------------------------- 1.名词解释NP, NP-hard, NP-complete, reduce的定义 2.reduction问题 a."champion problem" can be reduced to "convex hull problem". b."hamiltonian problem" can be reduced to "longest path problem". c."vertex cover" can be reduced to "max independent set". && "max independent set" can be reduced to "vertex cover". (http://ppt.cc/O!n5 )<-含有简单易懂的证明 d."3-SAT" can be reduced to "max independent set". 定义clause, literal, CNF 定义k-SAT 3.approxmation alogorithm a.vertex cover 叙述近似方法 此方法必须要是多项式时间 说明这方法是理想答案的几倍 --------------------------------- 我先做1., 2.c, 2.b --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.7.59 ※ 编辑: ajnightmare 来自: 140.112.7.59 (05/24 15:26) ※ 编辑: ajnightmare 来自: 58.114.208.7 (06/18 22:25)