作者noodleT (麵T)
看板Prob_Solve
標題[問題] 最長成語接龍
時間Sat Oct 29 16:19:56 2016
給定 n 個不重複的成語，
如何在這些成語中找出一個最長的成語接龍？
如果有多組答案，只要輸出其中一組即可。
請問複雜度降到多項式時間的可能嗎？
實在沒有什麼想法…
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.9.252
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1477729199.A.406.html
1F：→ pttworld: LIS方向可能。 10/29 16:35
2F：→ sifmelcara: 最長路徑是NP-hard 10/29 16:38
3F：→ noodleT: 如何證明 NP hard 10/29 17:03
4F：→ yr: 轉成 directed graph ， longest path problem 為 NP-hard 10/29 20:34
5F：→ FRAXIS: 最長的定義是什麼？ 可以用重複成語的話可以無限長吧 10/29 21:55
6F：→ noodleT: 不能重複使用、利用最多成語為最長 10/29 23:14