Re: [理工] [資結] 99年成大資工

[FRAXIS (喔喔)]

※ 引述《boy5548 (小YO)》之銘言：
: 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??）。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
→ aoqq12:應該是沒有沒錯..  會重複到共同頂點
→ privatewind:差不多是這樣，但是事實上…這題有暇疵…這只是以目前
→ privatewind:人們的思維想不到最佳子結構而已，天知哪個神人可以
→ privatewind:突然想出來呢 ??
推 boy5548:感謝~~
推 genius945:01 knapsack 也是npc