Research Space for Linear Algebra & Discrete Mathematics
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也不唯一), 反例很好找
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也不唯一), 反例很好找