作者TEPLUN (mihanami)
看板Grad-ProbAsk
标题[理工] 100交大资演
时间Sun Dec 16 20:48:11 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1544964494.A.35D.html
1F：推 Dora5566: 你自己把D选项算出来不就已经矛盾了吗 12/16 21:18
2F：→ TEPLUN: 哪里矛盾？ 12/16 21:42
3F：推 olen0622: D选项只能是n 12/17 03:10
4F：→ TEPLUN: 请问原因是？如果设定成n(1+e/2) 找出来若为true 必定是 12/17 10:59
5F：→ TEPLUN: 长度为n的cycle吧？ 12/17 10:59