数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 1715|回复: 4

一列距离为 a 的 n 个点,逐步作两两有方向的连接,最后连接到末端点,求最短连接距离

[复制链接]
发表于 2022-5-12 20:15 | 显示全部楼层 |阅读模式
在做一个工程课题时,发现这个,总觉得背后有种数学关系,但是作为一个工科生,数学知识的储备着实可怜,请教一下各位

假设有8个点(在一列上),每个点之间的距离相同(假定为a)
两个点之间进行具有方向的连接,两个点连接的方向终点,再与其余的方向终点进行具有方向的连接,最终对所有点完成连接,并把连接的最终点与最低点进行连接(若最终点就是最低点,便无需进行此操作),计算最终的所有连接线长度总和的最小值及最长的连接线长度最小值。

以1为例:
        从上到下相邻两点之间进行有方向的连接,连接后的终点再次进行有方向的连接,如图最终对所有点完成连接。
        此时,所有的连接线长度总和为12a;最长的连接线长度为4a;

我在尝试画时,发现其余的方式,见例2:
        此时,所有的连接线长度总和为11a;最长的连接线长度为2a;此方式在总和和最长长度上都比方式1小。

ps:可以不是相邻之间两点进行连接,也可以是第一个点和第三个点连或是其他,只要是两点相连就行。
        我给出的例子是8个点,要是扩展到16个点和32个点时,又是如何的状态呢?





本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2022-5-12 21:57 | 显示全部楼层
会编程这个就不是问题了。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-5-13 09:21 | 显示全部楼层
本帖最后由 boxs 于 2022-5-13 09:22 编辑
Nicolas2050 发表于 2022-5-12 21:57
会编程这个就不是问题了。


确实,我也在尝试用python折腾,想的要对其进行遍历,然后得到最优结果。刚开始学,小问题不断,一直在调试。想的是要是有个数学关系,或是公式之类,能更有说服力。
回复 支持 反对

使用道具 举报

发表于 2022-9-23 11:03 | 显示全部楼层
能跳多少跳多少,要有贪心算法的思路。比如4个点,1连3,2连4,3连4,最长2,总长5,怎么会需要总长多那么多呢。再比如你这里的8个,1连3,2连4,3前面有了先放一放,4也有了,完了5连7,7连8,剩下6跟5连一下不就都连起来了,总长2+2+2+1+1=10,怎么会需要12呢。一定要有个贪的思路。
回复 支持 反对

使用道具 举报

发表于 2022-9-23 11:14 | 显示全部楼层
上面这个有瑕疵,不对,6还需要和4连。

还是8个。1连3,2连4,4先连一下5有个基础,再有个4连6,接下来6连8,5连7就可以了都连上了,4、5相当于中间结点。总长2+2+1+2+2+2=11和你算的一样,最短也是2。就这样就可以了,不是唯一解肯定。总之贪就行了,能跨多少跨多少,完了有个中间结点的概念,因为跨度2最多不能超过2个跨度也就是4。假设你跨度是3,那你就不能超过6,差不多就是这个意思。

原则1:为了总长和最长最小,跨度必须充分利用;
原则2:为了总长最小,孤立点不能太多,比如前帖的6,那个解法虽然答案也是11和2,但方式不好;
原则3:最低点最好一次覆盖,即跨度能一次跨到就跨,实在不行比如4个点的那3和4连一下就可以了,一般都是像8那样直接6连8(所以4要作为中间结点先提前做铺垫)。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 19:07 , Processed in 0.076172 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表