[理工] 演算法TSP問題

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