连接正四边形四个顶点 [复制链接]

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

12^#

发表于 2008-9-12 09:05:31 |只看该作者

Dijkstra算法，不知道。刚去百度查了一下，他解决的是有路，如何选路的问题。
这题是修路的问题。朴素的解释。欣然，说的比较对路。三角形的答案我不知道。
我说的这题，简单地说就是，修条电话线把全国的大城市连起来。不考虑地形。
尽量缩短距离，降低造价。很朴素吧？

flwb

蓝魔

Rank: 2

积分: 519
帖子: 467
精华: 0
UID: 22856
性别: 男

13^#

发表于 2008-9-12 09:35:32 |只看该作者

回复 1# 的帖子

为什么X形不对?就应该是星形连接!设正四边形边长为1,顺序连接长度为3,星形连接总长为0.707x4=2.828。

北方闲人

Rank: 1

积分: 97
帖子: 82
精华: 0
UID: 35002
性别: 保密

14^#

发表于 2008-9-12 09:42:40 |只看该作者

回复 13# 的帖子

是啊，按我上边验算的结果，应该是X形啊，为什么不对？

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

15^#

发表于 2008-9-12 10:41:06 |只看该作者

我一开始和你想的一样，看答案后，才知道有更短的路线。究竟是不是最短路线，不知道
不会证明。

Cielo

透魔

有空了学学4D二阶

Rank: 6 Rank: 6

积分: 5924
帖子: 3936
精华: 0
UID: 1290
兴趣爱好: 结构
理论

16^#

发表于 2008-9-12 10:59:46 |只看该作者

确实有比X形更短的。
 
把正方形用两条对角线分成4个等腰直角三角形，找到上面的和下面的两个三角形的费马点，这样连起来就比X形要短！
 
因为等腰直角三角形的直角顶点不是费马点！
 
算出来是1+√3=2.732
 
不知道有没有更短的啊。

[ 本帖最后由 Cielo 于 2008-9-12 11:08 编辑 ]

魔鱼儿

铜魔

鱼儿

Rank: 8 Rank: 8

积分: 20516
帖子: 19704
精华: 0
UID: 28712
性别: 男

17^#

发表于 2008-9-12 11:05:25 |只看该作者

欣然研究的正多,呵呵, 这个都明白.

你即使是一条搁浅在沙滩上的鱼，也必须要学会行走。QQ:351796610已满,请加MSN:sun-shine-yu@live.cn
http://shop65338937请勿打广告com/晨曦魔方空间全场特价

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

18^#

发表于 2008-9-12 11:09:13 |只看该作者

请教一下“费马点”咋找。找出的角度是多少，

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

19^#

发表于 2008-9-12 11:12:48 |只看该作者

解决了这问题，再推广装修省钱了。嘿嘿

zxl0714

Rank: 1

积分: 171
帖子: 132
精华: 0
UID: 30495
性别: 保密

20^#

发表于 2008-9-12 12:25:55 |只看该作者

如果是正方形的应该是找到2个费马点就可以，但是如果扩展到任意多边形。。。。如果让我用编程解决的话我只会用近似算法，我说说我的思路。首先找到这些点阵的凸包，我可以肯定新加入的点肯定在凸包内，然后在凸包内随机加入几万个点，然后求一下这张图的最小生成树，再删去无用的边，然后重复多次取最好结果，这样出来的结果应该是比较令人满意了。。。。。。

[ 本帖最后由 zxl0714 于 2008-9-12 12:41 编辑 ]