推 Dora5566: 你自己把D選項算出來不就已經矛盾了嗎 12/16 21:18
→ TEPLUN: 哪裡矛盾？ 12/16 21:42
推 olen0622: D選項只能是n 12/17 03:10
→ TEPLUN: 請問原因是？如果設定成n(1+e/2) 找出來若為true 必定是 12/17 10:59
→ TEPLUN: 長度為n的cycle吧？ 12/17 10:59
https://i.imgur.com/uzNUAp8.jpg
想請問54題
為何不能這樣設定
如果有一邊不在原圖代表至少有一邊權重是2+ne
所以不符合條件的話權重會大於等於(n-1)+(2+ne)= n+ne+1
D選項的n(1+e/2)還是小於n+ne+1
所以這樣設定應該跟設定成n結果應該是一樣的？
不過看講義上寫TSP定義為”給定非負整數k“，問是否有長度至多為k的path
不知道是不是這個原因？（不知道這定義從何而來，有點狹隘的感覺，TSP應該可以應用
在其他領域）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.42.74
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1544964494.A.35D.html