一、請問unweighted longest simple path可以用DP在polynomial time完成嗎? why?
二、(不是題組.. 假設是無向圖)
請問下面這個演算法可以找到最長路徑嗎? 該怎麼 prove or disprove it呢
Step1:任意選取G=(V,E)上點u，然後找距離u最遠之點v
Step2:再由v找距離它最遠之點w，則(v,w)包含最長路徑
謝謝~
Research Space for Linear Algebra & Discrete Mathematics
1 則留言:
1. 這個問題不能用 DP 來解大概的想法是因為他不具有 optimal substructure 的性質, 細節請參考演算法的書; 不過在 graph 上找 longest path 是一個 NP-hard 的問題, 所以其實和D不DP也不是很有關係
2. 這並不是正確的演算法, 我不太清楚原題是怎麼寫的, 但這邊寫"(v,w)包含最長路徑"並沒有描述的很清楚這是什麼意思; 如果題目有寫的詳盡一些, 這個演算法應該就是一般在 tree 上找 longest path 的 linear time 解法, 他寫的找距離最遠的點可以用 BFS 做, 最後找出來的 v 和 w 他們之間的那條路徑就會是tree上的longest path, 但這個方法並不適用於 general graph (畢竟兩點間的path也不唯一), 反例很好找
張貼留言