看板 Grad-ProbAsk 關於我們 聯絡資訊
Unweighted longest simple path problem : Find a simple path from u to v consisting of the most edges. Prove or disprove : unweighted longest simple path problem exhibits optimal substructure. 請問這題跟證明longest simple path problem為NP-Complete有關係嗎? 前幾年成大也是出這題,只是他是問有沒有polynomial time的演算法可解,若是這樣問 ,答案就可以用NP-Complete來想了 請各位解答~謝謝!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.22.18.101
privatewind:這跟NP-Complete應該沒關,他只是要問你 01/12 18:26
privatewind:有沒有最佳子結構…如果我沒記錯 I2A有這題 01/12 18:26
boy5548:請問I2A是什麼?? 01/12 18:29
privatewind:Introduction to algorithm 聖經本 0.0 01/12 18:32
privatewind:這題我看了一下 答案是要Disprove 有興趣就翻翻看吧 01/12 18:57
boy5548:不好意思 因為我們學校沒有用聖經本 可以請你說明一下嗎 01/12 19:02
boy5548:謝謝你 01/12 19:02
skill91002:借問在I2A哪一部分 01/12 19:05
christianSK:這題應該找個反例說明一下就可以了吧 01/12 20:04
privatewind:I2a 293頁 前後 01/13 06:45
sneak: 這題我看了一下 答案是 https://daxiv.com 09/11 14:08