作者TEPLUN (mihanami)
看板Grad-ProbAsk
標題[理工] 演算法TSP問題
時間Mon Sep 24 16:10:19 2018
https://i.imgur.com/NfeMQNo.jpg
想請問有沒有大大能解釋一下如何證明tsp為npc
不太了解為什麼c function要令在原圖沒邊為1 有邊為0?然後還能令k為0
原題應該是給任意非負k都要能回答有沒有tsp吧？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.80.63
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1537776621.A.660.html
1F：推 eggy1018: 因為是要用tsp的問題解Hamilton cycle, 所以是由Hamilto 09/24 20:55
2F：→ eggy1018: n cycle reduce到 TSP，reduces 後的new graph G’一定 09/24 20:55
3F：→ eggy1018: 存在Hamilton cycle, 令原來Hamilton cycle 的問題為G(V 09/24 20:55
4F：→ eggy1018: ,E) -> G’(V,E’), 其中E是完全圖的邊。 因為Hamilton 09/24 20:55
5F：→ eggy1018: cycle 存在G中，所以令裡面的edge weight=0(即原來屬 09/24 20:55
6F：→ eggy1018: 於E的邊), 其他的為1。 因此解完TSP的同時，因為Hamilt 09/24 20:55
7F：→ eggy1018: on cycle 的邊在E中，又因為E的edge weight=0, 所以cost 09/24 20:55
8F：→ eggy1018: 為0， 若不為0則表示沒Hamilton cycle 09/24 20:55
9F：→ eggy1018: 因為可以用poly time Algo 驗證，加上可以由Hamilton cy 09/24 20:56
10F：→ eggy1018: cle reduced to TSP,所以TSP是NP complete 09/24 20:56
11F：→ TEPLUN: 感謝回答 我又回去看了一下定義 本來以為reduce是要兩邊 09/24 23:27
12F：→ TEPLUN: 都可以互相用演算法解 但應該實際上應該是單向關係 09/24 23:27
13F：推 eggy1018: 是可以互相reduce 因為那是NP hard的性質～也謝謝你上 09/24 23:30
14F：→ eggy1018: 次細心回答我的問題 09/24 23:30
15F：→ TEPLUN: 應該說reduce本身是單向的 但是證明reduce是證明對於「任 09/25 10:55
16F：→ TEPLUN: 何」A問題的instance可以轉換成一個B問題 兩個問題的轉換 09/25 10:55
17F：→ TEPLUN: 是雙向 我本來以為也要對於任何B問題的instance也成立才 09/25 10:55
18F：→ TEPLUN: 行qq 09/25 10:55
19F：→ FRAXIS: NP-Hard 不保證可以互相 polynomial-time reduce.. 09/25 10:57
20F：→ FRAXIS: NPC的問題是可以互相 polynomial time reduce 09/25 10:57
21F：→ FRAXIS: 證明是在說明G有HC若且唯若G'有0成本 TSP 09/25 11:03
22F：→ FRAXIS: 所以比較完整的證明法會分兩步 09/25 11:04
23F：→ FRAXIS: G 中有 HC 則 G' 中必有 0 成本 TSP 09/25 11:05
24F：→ FRAXIS: 再證 G' 有 0 成本 TSP 則 G 中必有 HC 09/25 11:05
25F：→ FRAXIS: （或是證明 G 中沒有 HC 則 G' 中必無 0 成本 TSP) 09/25 11:05
26F：→ FRAXIS: 雖然這邊看起來是在證明雙向 但是實際只是在證明單向.. 09/25 11:06
27F：推 eggy1018: 感謝點明觀念，我的意思可能沒表達清楚可以互相reduce 09/25 11:33
28F：→ eggy1018: 但不一定都是polynomial time, NPC則是一定可以在polyn 09/25 11:33
29F：→ eggy1018: omial time 互相reduces 09/25 11:33