[求助]关于斯坦纳树的算法

adiehe · 发表于 2003-8-7 09:21:29

现在分两步做，一个是虚拟站点的个数和位置，一个是加上虚拟站后的最小生成树。请教一下各位除了穷举法之外的可以推广的有效算法。

懵懂 · 发表于 2003-8-13 03:49:29

我怎么看都看不懂啊

路过 · 发表于 2003-8-13 03:52:05

什么是斯坦纳树啊？

飞云0616 · 发表于 2003-8-13 04:14:29

不知道啊

chinabuddy · 发表于 2003-9-20 18:45:14

斯坦纳树问题属于NP-hard Problem,只有一些近似算法或启发式算法,很难找到可以推广的有效算法,具体算法可参考关于数学规划的相关资料.

veve · 发表于 2003-9-20 23:52:07

adiehe MM，什么是斯坦纳树？能不能讲具体一点咧？
NP难问题虽然很难找到多项式算法，不过这种问题才有意思，有足够的发挥空间。

wswswst · 发表于 2003-9-21 01:32:19

我也很想知道耶！能否帮我们解惑？多谢！

adiehe · 发表于 2003-9-21 03:49:44

多谢各位关心了！
所谓斯坦纳树，就是可以在两点之间不能用欧式距离连接，而只能用平行与x和y轴的直线连接，且可以加入虚拟站点，以缩短距离。这个要画图才说得清楚。现在终于找到参考书了，在重庆邮电大学编的那本《数学实验》里头有介绍。

veve · 发表于 2003-9-21 04:50:59

adiehe在做什么问题咧？

		自动登录	找回密码
密码			注-册-帐-号