作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 一个图论的问题
时间Mon Dec 24 02:16:46 2007
哈哈，原来是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