[演算](2008/06/18修正) 05/15上課內容 slide 10,11
這禮拜的內容好像可以在期末考考古題找到一些參考資料
由於大家對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)