PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] longest path

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間14年前 (2010/11/01 01:01)推噓1(1推 0噓 3→)

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

※ 引述《CMturtle (傑尼龜)》之銘言： : 是說~~~一般最短路的演算法為什麼不能處理最長路阿？？ : 我的想法是 : 在無相圖中會出現正環的關係 : 但是如果再「有向無環圖」（DAG）中 : 是不是就可以套用最短路的算法來寫最長路？ : 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？最短路徑演算法(不管哪一個)的核心概念是動態規畫 Dynamic Programming 而要能夠做 DP 的題目必須要有「最佳子結構」或「重疊子問題」這代表我可以把一個題目拆成比較「小」的數個類似題前者是這些小問題的最佳解可以構成我們的最佳解後者則是這些小問題會一再地重覆計算這裡的小並不一定是數字上的小也許是數量上的少等等 (和遞迴的概念幾乎相同只不過計算方向上遞迴是 top-down 而 DP 是 bottom-up 而已) 最短路徑問題上單源非負最短路徑的「小」問題是起始點到稍近一點的點的距離這是「重疊子問題」其他的最短路徑的「小」問題則是只經過 k 號以前中介點的最短距離這是「最佳子結構」但最長路徑這個問題並沒有如此的性質我們並不能找到一些「小」的最長路徑問題的結果能夠拿來構築原來的最長路徑因此必須另尋他法來解決這個問題而這些其他方法中也許需要其他演算法來偵測正圈但解題的演算法主體並不會是它們 -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」実琴：「難道你沒有男人的尊嚴了嗎?!」亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」－－プリンセス・プリンセス第二話 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92