Re: [理工] 103 交大資演 NP問題

看板Grad-ProbAsk作者joeboy (揪立)時間7年前 (2017/01/15 15:48)推噓1(1推 0噓 20→)

留言21則, 3人參與討論串2/2 (看更多)

http://i.imgur.com/kbciU1u.jpg

同樣是第二個問題有關下面編輯的話我複製一遍 "因為 longest path problem 可以 reduce 到這個問題的 decision 版本: 在限制 instance graph 含有正 cycle 的情形下, longest path problem 仍為 NP-complete 所以將 LP 問題之 problem instance G 中所有邊的 weight 皆取負則可成為此問題的一個 problem instance G' 這樣找到 G' 的 shortest simple path 就相當於找到 G 的 longest simple path" 這個已經是在是在證明NP-HARD了吧？網路上也有查到，可以用longest path reduce過去，如果是simple path的話不知道有沒有其他人有更好的解釋呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.11.240 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484466532.A.DC3.html ※ 編輯: joeboy (42.73.11.240), 01/15/2017 15:49:45 ※ 編輯: joeboy (42.73.11.240), 01/15/2017 15:50:37

→

joeboy

01/15 20:07, , 1^F

01/15 20:07, 1^F

→

HEroKuma

01/15 20:38, , 2^F

01/15 20:38, 2^F

→

joeboy

01/15 20:47, , 3^F

01/15 20:47, 3^F