[問題] 最長成語接龍 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