[資工] 交大100-97 DS&Algo數題

看板Grad-ProbAsk作者qoojordon (穎川琦)時間11年前 (2015/01/23 21:51)推噓5(5推 0噓 5→)

留言10則, 5人參與討論串1/1

幾個觀念請教 http://ppt.cc/9uZQ http://ppt.cc/2jHQ [NCTU 100 19題組(54)] Problem I 是 constraint TSP Problem III 是 H.C. (Hamilton Cycle) 題幹的敘述是 III reduce到 I , 印象中, 兩個問題之間證明reduce關係需要說明兩個問題能再多項式複雜度內的轉換下,彼此互相對應　　G有H.C. 　←→　G'在constraint n(1+e)內有TSP 註: G'是加入題幹中D[i,j]修正後的圖不知道我這樣解釋正確嗎 ? [NCTU 99] 想找反例解釋是因為只增加某根capacity仍無確保多出來的flow可以透過augment path 到達t嗎? [NCTU98] 我自己標了幾個比較噁心的複雜度 , 好奇他們之間的比序關係是? a < e < b < d < c < f [NCTU 97 4(7)] 查版上之前分享的答案是T , 不過好像爭議不多 , 沒有太多討論 WIKI上的weight-balance tree的敘述和題幹說明不太類似?? http://en.wikipedia.org/wiki/Weight-balanced_tree [NCTU 97 6] 版上之前的分享答案是 (c,d)增加到4 , max flow=5 不過我直接把附圖當成沒有作完的 residual network不用增加(c,d)得到也是5 min cut在(s,a),(s,c),(s,e) 不曉得2,3小題之間是不是我誤會了甚麼主要的概念 ? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.25.63 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422021068.A.58E.html

→

kather

01/23 22:07, , 1^F

01/23 22:07, 1^F

推

FRAXIS

01/23 22:11, , 2^F

01/23 22:11, 2^F

→

FRAXIS

01/23 22:11, , 3^F

01/23 22:11, 3^F

→

FRAXIS

01/23 22:12, , 4^F

01/23 22:12, 4^F

→

FRAXIS

01/23 22:13, , 5^F

01/23 22:13, 5^F

F大在請教一下,如果要正式的證明reduce 我看到的手法幾乎都同一個套路 1.先想出一個轉換的方式 2.證明(==>) , 在原問題上取出條件成立情形(此例即為G具有H.C.) , 會mapping到轉換後的某個條件成立情形 (此例為G'滿足n ~ n(1+e)+1 TSP之限制) 故得證(==>) 3.證明(<==) , 我每次證這一步都會像在說廢話,以此題為例就只是把(==>)反過來講於G'中存在滿足n ~ n(1+e)+1 constraint的TSP時 G會具有H.C. 故得證(<==) 我上述的 2 , 3有犯錯嗎? , 感覺幾乎1的轉換方式想到了就等於證明完了.... ※ 編輯: qoojordon (111.251.25.63), 01/23/2015 23:02:11

推

killerw74

01/23 23:39, , 6^F

01/23 23:39, 6^F

推

FRAXIS

01/24 01:50, , 7^F

01/24 01:50, 7^F

→

FRAXIS

01/24 01:52, , 8^F

01/24 01:52, 8^F