魔方吧·中文魔方俱乐部

标题: 连接正四边形四个顶点 [打印本页]

作者: 刚吃完 时间: 2008-9-11 19:42:55 标题: 连接正四边形四个顶点

请教一问题，过去看书，有一问题
连接正四边形四个顶点，最短线路应该怎样连。
现实中，可想像成连接正四边形顶点上的四个城市的电话线。
怎样布线最短。X型肯定不对。
更进一步连接多个城市，怎样布线最短。
后一问题我也不知道答案。
不知道说明白了吗？

作者: flwb 时间: 2008-9-11 20:29:15

有点意思,先顶了再说!

作者: yama523 时间: 2008-9-11 21:01:09

好像是听过这个，但不记得了

作者: bbshanwei 时间: 2008-9-11 21:18:43

问题是明白了，正在考虑中！

作者: 金眼睛 时间: 2008-9-11 21:26:34

之前没考虑到加点之后能够更短，说得不对，其实对于长方形也得视情况而定，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> 
 
设长方形的长为1，宽为X，X取值范围为0~无穷，比较五种连接方法，如附件图中所示：
1：红实线—两长一宽
2：蓝实线—两宽一长
3：绿实线—两对角线和
4和5是他们的混合，可以不看
当x的取值不同的时候，最小值不同。
 
欣然说得很好啊！！可以证明四边形内如果取一点，到四个顶点距离之和最小，就是对角线交点。但如果取两个费马点并合理布置，可以做到更短。
 
点数继续增加，问题将更加复杂，没思路啊，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> 
 
回复6#的帖子
 
6#说的是Dijkstra算法吧？用到了图论，不过跟这个问题有些区别吧？那个要固定一个源点的，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> 
让源点遍历N点，用N次Dijkstra算法，然后比较N个结果，找出最小值，应该也行的。
 

[ 本帖最后由金眼睛于 2008-9-12 18:37 编辑 ]

附件: [长方形的情况] 长方形四点最短连通线.JPG (2008-9-12 15:49:25, 20.43 KB) / 下载次数 77
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUyMTh8MzI5YzMwMWN8MTczMzE1NjUxNXwwfDA%3D

作者: 刚吃完 时间: 2008-9-11 21:34:28

补充一句如果是随机分布的多点，难度出了这里的范围了吧？

作者: kexin_xiao 时间: 2008-9-12 08:40:07

LZ是后起之秀啊，最近频发问题

看看，考虑一下。

作者: kexin_xiao 时间: 2008-9-12 08:43:11

这个问题和“费马点”问题有相似的地方。

作者: kexin_xiao 时间: 2008-9-12 08:44:08

简单介绍一下：法国著名数学家费尔马曾提出关于三角形的一个有趣问题：在三角形所在平面上，求一点，使该点到三角形三个顶点距离之和最小，人们称这个点为“费马点”。

作者: 北方闲人 时间: 2008-9-12 09:02:42 标题: 回复 5# 的帖子

我用最笨的办法验算了一下,发现四边形也不能一概而论的如您所说那样,有一个分界线,那就是长短边之比为勾股比,这时一长边加两短边之和等于两斜边之和;长短边比大于勾股比时,一长边加两短边之和小于两斜边之和;长短边比小于勾股比时,一长边加两短边之和大于两斜边之和.不知道我说的对不对?

作者: sl888000 时间: 2008-9-12 09:04:21

我好像没看明白。。。。。+

作者: 刚吃完 时间: 2008-9-12 09:05:31

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

作者: flwb 时间: 2008-9-12 09:35:32 标题: 回复 1# 的帖子

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

作者: 北方闲人 时间: 2008-9-12 09:42:40 标题: 回复 13# 的帖子

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

作者: 刚吃完 时间: 2008-9-12 10:41:06

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

作者: Cielo 时间: 2008-9-12 10:59:46

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

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

作者: 魔鱼儿 时间: 2008-9-12 11:05:25

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

作者: 刚吃完 时间: 2008-9-12 11:09:13

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

作者: 刚吃完 时间: 2008-9-12 11:12:48

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

作者: zxl0714 时间: 2008-9-12 12:25:55

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

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

作者: 刚吃完 时间: 2008-9-12 12:49:32

电线省了，电钱废了。
好像不容易证明，一定是最短。
有没有，简单点的方法，蚁群算法。可以吗？
可我想不出如何编码。好像中间还要混合，遗传算法，
再拼接一下。晕了，计算代价也不小。

作者: 刚吃完 时间: 2008-9-12 13:06:56

百度刚查了“费马点”
http://baike.baidu.com/view/184329.htm
原来知道答案，不知道为什么，现在知道了。欣然真厉害。

作者: flwb 时间: 2008-9-12 13:09:36

"O"是费马点,AO+BO+CO<AB+AC我开始随便算了一下,今天一看,原来算错了!

[ 本帖最后由 flwb 于 2008-9-19 22:11 编辑 ]

附件: Drawing1.JPG (2008-9-12 13:09:36, 23.25 KB) / 下载次数 38
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUxODR8YWJhNzI0OWV8MTczMzE1NjUxNXwwfDA%3D

作者: 刚吃完 时间: 2008-9-12 13:25:04

想的太复杂，
提示：
(1).三内角皆小于120°的三角形，分别以 AB,BC,CA，为边，向三角形外侧做正三角形ABC1,ACB1,BCA1,然后连接AA1,BB1,CC1,则三线交于一点P,则点P就是所求的费马点.
(2).若三角形有一内角大于或等于120度,则此钝角的顶点就是所求.
(3)当△ABC为等边三角形时,此时外心与费马点重合
来自百度。
我看完知道为什么了，正四边形。

作者: 刚吃完 时间: 2008-9-12 13:44:01

忘了说，欣然的算法不正确。

作者: 刚吃完 时间: 2008-9-12 18:13:42

我说错了欣然真厉害。
答案：>-<120度

作者: ggglgq 时间: 2008-9-12 20:01:35

                如果按楼主说的“ X 型肯定不对”，那么我估计多半是楼主记错原题了！         连接多个地点（城市）的地铁线，往往是采用“环路”，其造价最省的   方案往往就是找到一个周长最小的“环路”。        找到的这个周长最小的“环路” 必然满足 “ X 型肯定不对” ！                下面给出一个软件说明这个问题：

周长最小环路问题.rar (3.2 KB, 下载次数: 15)             软件中按数值 N ，将随机产生一个节点为 N ，并且周长最小的环路。

附件: 周长最小环路问题.rar (2008-9-12 20:01:35, 3.2 KB) / 下载次数 15
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUyNTh8NjNmY2Y1OGV8MTczMzE1NjUxNXwwfDA%3D

作者: zxl0714 时间: 2008-9-12 22:37:28

楼上的估计理解错了，毕竟电话线不是地铁，不需要成为一个环，或者说有环的图一定不是最短的。

作者: 刚吃完 时间: 2008-9-12 23:40:02

就是这形状>-<两个钝角120度，如上图所示角boc120度，原来计算过，动一点都不行。想不明白为什么，不知道费马点，“(2).若三角形有一内角大于或等于120度,则此钝角的顶点就是所求. ”，主要是看了这句话明白了，为什么是120度。如果小于120度，费马点在三角形内部。如上图所示，费马点在o点下边，所以是错的。因为费马点够成的三条线段最短。
如果大于120度，他所向上的线段还要经过120度钝角点，所以，120度构成的是最短路线。不知道我这外行解释的通吗？还是欣然的方法解释的简练，反正是经过中点，两个费马点完成。可计算有点麻烦。外行的初级解释。很费劲啊！多谢各位的指教。周长最小环路下载不了。多点问题同意20＃的观点虽然我编不出这种程序，意思理解了。反正够难，还是近似解。

作者: 真知不易 时间: 2008-9-13 16:32:17

如果只是一个点，那就是对角线交点，如果加一个点，那就是两个费马点，两个方案长度相差3.5%而已，形状就象蜂窝型。

作者: 刚吃完 时间: 2008-9-14 10:09:32

再次回27#又想了一下，修公路和修电话线有较大区别，电话线10公里和100公里使用上差别不大，考虑总长就行了。属于单目标规划。修公路可就麻烦了。属于多目标规划。地铁线好像属于面之间的联系了。我只能想到这一步了，智商不够啊。

作者: 甜甜私房猫 时间: 2008-9-14 14:32:52

到底咋连的啊，没一个说清楚的

作者: ggglgq 时间: 2008-9-18 10:30:00

原帖由 刚吃完 于 2008-9-12 23:40 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=237667&ptid=13634" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 
 
周长最小环路下载不了。

今天论坛可以下载了！

原帖由 刚吃完 于 2008-9-11 19:42 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=236656&ptid=13634" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 
 
<DIV class=t_msgfont id=postmessage_236656>请教一问题，过去看书，有一问题连接正四边形四个顶点，最短线路应该怎样连。现实中，可想像成连接正四边形顶点上的四个城市的电话线。怎样布线最短。X型肯定不对。更进一步连接多个城市，怎样布线最短。后一问题我也不知道答案。不知道说明白了吗？</DIV>

满足 “ X 型肯定不对”，应该是指连接 N 节点“环路”的最小周长问题。

作者: flwb 时间: 2008-9-19 19:42:44

[attach]25593[/attach]

[ 本帖最后由 flwb 于 2008-9-19 19:59 编辑 ]

作者: Cielo 时间: 2008-9-19 21:29:59

原帖由 甜甜私房猫 于 2008-9-14 14:32 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=238849&ptid=13634" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
到底咋连的啊，没一个说清楚的

我在16楼说了，但可能说的不清楚吧。 借用23楼的图，就是说找到下面的等腰直角三角形的费马点O，将它与那个三角形的三个顶点分别相连，也就是OA、OB、OC； 类似地，对上面那个等腰直角三角形也同样连三条线，这样所有的四个顶点就都连起来了。 由于O是△ABC的费马点，而A不是，所以OA+OB+OC＜AB+AC，所以像上面那样连比X形要短。

作者: ares_g 时间: 2008-9-21 21:46:54

为什么X肯定不对呢？正4边形既是轴对称又是中心对称的，我认为对称中心是与4个顶点连线总和最短的的。

作者: Cielo 时间: 2008-9-22 00:12:57

原帖由 ares_g 于 2008-9-21 21:46 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=245996&ptid=13634" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
为什么X肯定不对呢？正4边形既是轴对称又是中心对称的，我认为对称中心是与4个顶点连线总和最短的的。

是啊，正方形的这种情况确实有点奇怪。 但是没办法，有事实在啊，你可以算一下，23楼的图里，OA+OB+OC 和 AB+AC 哪个更短。

作者: flwb 时间: 2008-9-22 08:38:43

实际上好理解,从正方形的中心到费马点的连线是共享的,如果是互联网,这样最省线,如果是电话线,不能共享,还是X形省线。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)