[理工] 100交大資演

作者: TEPLUN (mihanami)   2018-12-16 20:48:11
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應該可以應用
在其他領域)
作者: Dora5566 (咩休幹某)   2018-12-16 21:18:00
你自己把D選項算出來不就已經矛盾了嗎
作者: TEPLUN (mihanami)   2018-12-16 21:42:00
哪裡矛盾?
作者: olen0622 (hong)   2018-12-17 03:10:00
D選項只能是n
作者: TEPLUN (mihanami)   2018-12-17 10:59:00
請問原因是?如果設定成n(1+e/2) 找出來若為true 必定是長度為n的cycle吧?

Links booklink

Contact Us: admin [ a t ] ucptt.com