討論串(共5篇) - [問題] longest path - 看板Prob_Solve

看板 [ Prob_Solve ]

討論串[問題] longest path

共 5 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

[問題] longest path

推噓2(2推 )留言2則，0人參與作者CMturtle (傑尼龜)時間14年前 (2010/11/01 00:19)資訊

內容預覽:

是說~~~一般最短路的演算法為什麼不能處理最長路阿？？. 我的想法是. 在無相圖中會出現正環的關係. 但是如果再「有向無環圖」（DAG）中. 是不是就可以套用最短路的算法來寫最長路？. 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？. --. ※ 發信站: 批踢踢實業坊

Re: [問題] longest path

推噓1(1推 )留言4則，0人參與作者LPH66 (-858993460)時間14年前 (2010/11/01 01:01)資訊

內容預覽:

最短路徑演算法(不管哪一個)的核心概念是動態規畫 Dynamic Programming. 而要能夠做 DP 的題目必須要有「最佳子結構」或「重疊子問題」. 這代表我可以把一個題目拆成比較「小」的數個類似題. 前者是這些小問題的最佳解可以構成我們的最佳解. 後者則是這些小問題會一再地重覆計算. 這裡

(還有435個字)

Re: [問題] longest path

推噓6(6推 )留言8則，0人參與作者tkcn (小安)時間14年前 (2010/11/01 01:02)資訊

內容預覽:

因為最短路徑演算法是使用 Dynamic Programming，. 而 DP 能解的問題必須具備 optimal substructure 特性。. 以最短路徑來說，一條最短路徑隨意拆成兩段，. 這兩段也會是最短路徑 (否則我們大可把原來路徑對應的一段替換為現在更短的這條). 但是最長路徑並沒有這

(還有714個字)

Re: [問題] longest path

推噓0(0推 )留言0則，0人參與作者DJWS (...)時間14年前 (2010/11/02 00:21)資訊

內容預覽:

回答一：. 因為最短路和最長路的性質不同。. 最核心的差異是：最短路隨便截一段還是最短路，最長路隨便截一段通常不是最長路。. 最短路的演算法，就是用上述性質推導出來的。. 這個性質就是前面板友所說的 optimal substructure！. 最長路之所以很難算，就是因為我們找不到它的 optim

(還有153個字)

Re: [問題] longest path

推噓2(2推 )留言2則，0人參與作者SuBaRaSi (dddddddd)時間14年前 (2010/11/02 16:57)資訊

內容預覽:

補充一下. 在允許負邊, 比較general的graph上, 最長路和最短路的性質其實是一樣,對稱的. 在這樣的graph上. longest 'simple' path和 shortest 'simple' path同樣是np-hard. longest path和shortest path(不要

首頁

尾頁