作者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/cn.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