作者boy5548 (小YO)
看板Grad-ProbAsk
標題[理工] [資結] 交大99資訊聯招
時間Mon Jan 24 16:28:02 2011
Given a weighted graph and two vertices s and t, we want to find a longest
path from s to t. Which of the following statements are WRONG about this
problem?
(i)This problem has a polynomial time algorithm.
(ii)This problem can be solved by transforming it into shortest path problem.
(iii)This problem can be solved by using Dynamic Programming.
(iv)For a connected weighted graph the longest path has at least 3 edges.
(v)For a graph with n vertices, if the longest path has n-1 edges,then it
passes through each vertex exactly once.
答案是(i)(ii)(iv)
我的問題是第(iii)，我記得longest problem是NP-Complete吧?他可以用DP解嗎...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.122.17
→ jameschou:會不會是因為平常的longest path problem是找整張圖裡面 01/24 17:02
→ jameschou:最長的 可是這題是已給起點終點呢? 01/24 17:03
推 cakeboy:我想會不會是0/1背包問題也是NPC,可是可以用DP解 01/24 17:54
→ jameschou:其實我剛剛也是想講樓上這句XD 所以其實NPC跟是否可用DP 01/24 18:06
→ jameschou:沒有這個絕對的關係 不過現在這題可能有cycle的情況所以 01/24 18:07
→ jameschou:我還想不太出來DP的演算法 如果是acyclic感覺就可以用類 01/24 18:09
→ jameschou:似Dijkstra的演算法下去跑了 01/24 18:09
→ privatewind:wiki有說 如果 weighted directed acyclic 那可以用DP 01/24 18:35
→ boy5548:謝謝樓上幾位 01/24 21:06