[问题] 最长成语接龙 noodleT PTT批踢踢实业坊

[问题] 最长成语接龙

楼主: noodleT (面T) 2016-10-29 16:19:56

给定 n 个不重复的成语，
如何在这些成语中找出一个最长的成语接龙？
如果有多组答案，只要输出其中一组即可。
请问复杂度降到多项式时间的可能吗？
实在没有什么想法…

作者: pttworld (批踢踢世界) 2016-10-29 16:35:00

LIS方向可能。

作者: sifmelcara (sifmelcara) 2016-10-29 16:38:00

最长路径是NP-hard

楼主: noodleT (面T) 2016-10-29 17:03:00

如何证明 NP hard

作者: yr (Sooner Born Sooner Bred) 2016-10-29 20:34:00

转成 directed graph ， longest path problem 为 NP-hard

作者: FRAXIS (喔喔) 2016-10-29 21:55:00

最长的定义是什么？可以用重复成语的话可以无限长吧

楼主: noodleT (面T) 2016-10-29 23:14:00

不能重复使用、利用最多成语为最长

继续阅读

[问题] 数量方法求救ucc1050 [问题] Maximum Independent Set(Greedy method)cutekid [问题] google搜寻3个以上关键字的复杂度?pizzafan [问题] 请问更好的解法allen7812 [问题] SPOJ VFDIVpttworld Re: [问题] Maximum Productcutekid Re: [问题] Maximum Productpttworld Re: [问题] Maximum Productdibery [问题] Maximum Productcutekid [问题] krsukal 跟 prim's algorithmjohnny94

Contact Us: admin [ a t ] ucptt.com