Re: [問題] 一個圖論的問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間17年前 (2007/12/24 02:16)推噓0(0推 0噓 0→)留言0則, 0人參與討論串6/6 (看更多)
哈哈，原來是NP-Complete問題，難怪特別難想。 :)
是我太孤陋寡聞了，真是不好意思。
既然有關鍵字了，我就可以自己上網查點資料了。
謝謝你啦！
另外再請教一個問題，
如果這個圖是位在二維平面上，且cost都滿足距離的定義，
當距離分別為 Euclidean distance 和 city block distance 時，
這個問題會不會有多項式時間解？
※ 引述《tkcn (小安)》之銘言：
: http://en.wikipedia.org/wiki/K-minimum_spanning_tree
: This problem is known to be NP-complete.
: 看來只能用 heuristic 囉
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.90.81
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
