[問題] 最長成語接龍

看板Prob_Solve作者 (麵T)時間9年前 (2016/10/29 16:19), 編輯推噓0(0推 0噓 6→)
留言6則, 5人參與, 最新討論串1/1
給定 n 個不重複的成語， 如何在這些成語中找出一個最長的成語接龍？ 如果有多組答案，只要輸出其中一組即可。 請問複雜度降到多項式時間的可能嗎？ 實在沒有什麼想法… -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.9.252 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1477729199.A.406.html
→
10/29 16:35, , 1F
LIS方向可能。
10/29 16:35, 1F
→
10/29 16:38, , 2F
最長路徑是NP-hard
10/29 16:38, 2F
→
10/29 17:03, , 3F
如何證明 NP hard
10/29 17:03, 3F
→
10/29 20:34, , 4F
轉成 directed graph ， longest path problem 為 NP-hard
10/29 20:34, 4F
→
10/29 21:55, , 5F
最長的定義是什麼？ 可以用重複成語的話可以無限長吧
10/29 21:55, 5F
→
10/29 23:14, , 6F
不能重複使用、利用最多成語為最長
10/29 23:14, 6F
‣ 更多 noodleT 的文章
文章代碼(AID): #1O55klG6 (Prob_Solve)