→ wolfswolfs:就是說 u~m的最長可能途經一點k m~v的最長也可能經過k 02/10 22:01
→ wolfswolfs:所以不是simple 02/10 22:02
※ 引述《FRAXIS (喔喔)》之銘言：
: : Unweighted longest simple path problem :
: : Find a simple path from u to v consisting of the most edges.
: : Prove or disprove : unweighted longest simple path problem exhibits optimal
: : substructure.
: : 請問這題跟證明longest simple path problem為NP-Complete有關係嗎?
: : 前幾年成大也是出這題，只是他是問有沒有polynomial time的演算法可解，若是這樣
: : ，答案就可以用NP-Complete來想了
: : 請各位解答~謝謝!!
: 如果他說的optimal substructure是說任一最長路徑，其子路徑也是最長路徑，
: 那就是沒有。
: 一最長Simple路徑u ~ m ~ v，u ~ m和m ~ v未必都是最長Simple路徑，
: 因為這兩條最長路徑可能都使用到共同的頂點，
: 導致合併起來成為u~v的路徑時不是Simple。
: 但是或許會有其他optimal substructure，只是我太笨想不出來而已..
: 此外，有沒有optimal substructure跟NP-Complete沒有關係，NP-Complete
: 的問題可以有optimal substructure（TSP??）。
關於這題 感覺還不是很清楚..請問一下"可能都使用到共同的頂點，導致合併起來
成為u~v的路徑時不是Simple。" 這句話的意思嗎 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.6.117
※ 編輯: boy5548 來自: 114.39.6.117 (02/10 10:54)