作者noodleT (面T)
看板Prob_Solve
标题[问题] 最长成语接龙
时间Sat Oct 29 16:19:56 2016
给定 n 个不重复的成语，
如何在这些成语中找出一个最长的成语接龙？
如果有多组答案，只要输出其中一组即可。
请问复杂度降到多项式时间的可能吗？
实在没有什麽想法…
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.9.252
※ 文章网址: https://webptt.com/cn.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