诗龛雪 发表于 2007-7-24 11:09

请教如何求解有障碍区域的最小生成树

请教一下，关于有障碍区域的最小生成树问题。
      本来题目很简单的，但是数据很多，一百多个点，要求算出一个最小生成树，关键是要避开一些障碍区域。
      如果人为地把会跨越障碍区的边 权值改为无穷大的话很不现实。如果把障碍区的边表示出来，用邻接矩阵接的话，计算量更大。虽然是用计算机求解，可是也感觉不妥。
      哪位高手可以提供一些相应的办法啊,谢谢了！

[ 本帖最后由 诗龛雪 于 2007-7-24 11:30 编辑 ]

无水1324 发表于 2007-7-24 22:18

很抱歉，对你这个问题完全不懂，希望有高手来帮你解答！
顺便问一下，你这个生成树是由分形产生的分形树吗？

诗龛雪 发表于 2007-7-26 17:48

回复 #2 无水1324 的帖子

那个~~这个题目我做出来了，还是用求的邻接矩阵。好像真没什么好方法了。
这个最小生成树就是最一般的树了，没有要求。
原题是已知一些点，要求算出一个最小生成树，但必须绕过一些障碍区。障碍区是很普通的凸多边形。
还是谢谢回复哦！呵呵~~

无水1324 发表于 2007-7-26 17:51

回复 #3 诗龛雪 的帖子

恩
我不懂，数学涉及的东西太多了。

诗龛雪 发表于 2007-7-27 22:00

回复 #4 无水1324 的帖子

也是呢，不过我不是学数学的~有些可惜阿，呵呵

无水1324 发表于 2007-7-27 22:26

回复 #5 诗龛雪 的帖子

哈哈，但是你还是很强的，我数学太差了
页: [1]
查看完整版本: 请教如何求解有障碍区域的最小生成树