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