找回密码
 欢迎注册
查看: 1737|回复: 6

[原创] N维空间里K对虫洞的最佳安装位置

[复制链接]
发表于 2024-7-7 09:39:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

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

×
本贴考虑的空间是一个N维的、平坦的、周期性边界的单位超立方体。

例如:
精华


当N=1时,本贴考虑的空间是一条长度为1的线段

“周期性边界”的意思是:

线段的左端点和线段的右端点是相互连通的,到了左端点还继续往左走,就会出现在右端点上,反之亦然

当N=2时,本贴考虑的空间是一个1*1的正方形

“周期性边界”的意思是:

正方形的左右两边是相互连通的:到了左边界还继续往左走,就会出现在右边界上,反之亦然;
正方形的上下两边是相互连通的:到了上边界还继续往上走,就会出现在下边界上,反之亦然。

问题1:给定N,问空间中两点的平均距离是多少?

(即以均匀分布在空间中随机抽取两个点,求这两个点的距离的期望值)

问题2:如果允许在这个N维空间里安装K对虫洞,问这K对虫洞应该分别安装在哪里,才可以使得空间中两点的平均距离达到最小?这个最小值是多少?

(虫洞必须成对安装,假设两个成对的虫洞分别位于空间中的A点和a点,那么当我们走到A点时,可以穿过虫洞到达a点,反之亦然,使得原本相距遥远的A、a两点的距离变成0)

建议坛友们循序渐进地讨论此问题,先解决N=1的简单情形,然后讨论N=2的情形,把显示K对虫洞安装位置的平面图绘制出来
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-7 10:13:29 | 显示全部楼层
我来解决N=1的简单情形吧

问题1:

如果只安装0对虫洞,且没有周期性边界,那么长度为1的线段上,两个点的平均距离是1/3

如果只安装0对虫洞,那么长度为1的、周期性边界的线段上,两个点的平均距离是1/4

问题2:

如果只安装1对虫洞,且没有周期性边界,那么长度为1的线段上,两个点的平均距离的最小值是(2-sqrt(2))/3,约等于0.195262

这对虫洞应该分别安装在(sqrt(2)-1)/2处和(3-sqrt(2))/2处,这两个位置如下图的A点和a点所示:

1.png

如果只安装1对虫洞,那么长度为1的、周期性边界的线段上,两个点的平均距离的最小值是3/16,等于0.1875

这对虫洞的安装方案不唯一,只要相距最远(距离为1/2)即可,其中1种方案的安装位置如下图的A点和a点所示:

1.png

如果安装2对虫洞,且没有周期性边界,那么长度为1的线段上,两个点的平均距离的最小值是(63-14^1.5)/75,约等于0.141557

第1对虫洞应该分别安装在(9-2*sqrt(14))/10和1/2处,第2对虫洞应该分别安装在1/2和(1+2*sqrt(14))/10处,如下图所示:

1.png

如果安装2对虫洞,那么长度为1的、周期性边界的线段上,两个点的平均距离的最小值是5/36,约等于0.138889

这2对虫洞应该这样安装:

1.png

如果安装K对虫洞,且没有周期性边界,那么需要求解一个三次函数的最值,得到平均距离的最小值和最佳安装位置

最佳安装方案是令K对虫洞的一端全都位于同一个点上,做成一个具有(K+1)个出入口的虫洞,然后令这些出入口等间距地分布在线段上即可

如果有周期性边界,那么这条线段是首尾相接的,相当于一个圆环

最佳安装方案也是令K对虫洞的一端全都位于同一个点上,做成一个具有(K+1)个出入口的虫洞,然后用这些出入口把圆环均分成(K+1)段即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-7-7 13:42:17 | 显示全部楼层
N=1时看上去还是比较好分析的,但是N大了就太复杂了,也不容易理解。
N=1没有虫洞时,我们可以看成一条长度为1的绳子头尾相接得到的一个圆环。
而有一对虫洞时,相当于把圆环上两个点叠在一起打了个结,就变成一个8形的结构。
  两对虫洞,相当于在8形结构上再找两个点打结,当这两个点在一个圈上时,就变成三个接在一起的环;当这两个点在不同的圈上打结,得到结果相当于两个点,中间有四条边相连。
更加一般的,有K对虫洞情况,打结后得到是一个有K个点的连通图,图上每个点的度数都是4.
N=1时,K对虫洞最优解我猜测把这K对一侧全部放在一起,另外一侧均匀分布,整个圆环均匀划分为K+1段的情况。平均距离$\frac{2K+1}{4(K+1)^2}$.

点评

是的,漏了个1  发表于 2024-7-9 06:29
0对虫洞是1/4,1对虫洞是3/16,K对虫洞可能是(2K+1)/(4(K+1)^2)  发表于 2024-7-7 21:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-9 15:40:30 | 显示全部楼层
我对没有周期性边界的情况也是挺感兴趣的

本楼层将会持续更新,陆续给出当N=2时,在没有周期性边界的1*1的正方形里,安装K=0,1,2,...对虫洞的最佳方案

当K=0时,两点的平均距离是(2+sqrt(2)+5*ln(1+sqrt(2)))/15,约等于0.52140543316472,具体推导过程如下贴所示:

https://bbs.emath.ac.cn/thread-19502-1-1.html

当K=1时,两点平均距离的最小值是0.45797...,如下图所示:

1.png

这对虫洞应大致安装在(0.259,0.741)和(0.741,0.259)处,大致的安装位置如下图所示:

1.png

当K=2时,模拟退火算法会收敛到以下2个局部最优解(右边的解是全局最优解):

1.png

当K=3时,我懒得写模拟退火算法了,我猜测最优解是这样的:

1.png

当K=4时,把4个虫洞的一端安装在同一个位置,做成一个具有5个出入口的超级虫洞,

然后对这5个出入口的位置进行模拟退火,就会收敛到以下2个局部最优解(右边的解是全局最优解):

1.png

#####

K=5(5对虫洞)的最佳安装位置实在是太难求了(太烧CPU了),我已经在超算平台里投资了8.75元巨款:

1.png

还是没能成功求得最佳安装位置。

我担心投入更多的资金,依然会打水漂,所以我暂时停止求解了。

目前可以确定的是:

最优解应该是把5对虫洞的一端安装在同一个位置,另一端安装在不同的位置,做成一个具有6个出入口的超级虫洞

而这6个出入口排成其它形状肯定不是最优解,排成“日”形就很接近最优解了

在“日”形的基础上,稍微调整一下,做成如下图所示的4种形状,都是更优的解:

f.png

我目前的算法是很难判断出上面这4种形状,哪个才最优解,因为它们的平均距离的差异实在是太小了

虽然我觉得把运算量(投入的资金)增大至现在的100倍,就有希望判断出来哪个是最优解,但是我觉得现在没有必要进行这项投资

我打算等以后科技发达了(把现有的算法改进了),再用更小的成本把它求解出来

#####

当K=6时,把6个虫洞的一端安装在同一个位置,做成一个具有7个出入口的超级虫洞,

然后对这7个出入口的位置进行模拟退火,就会收敛到以下3个局部最优解(左边的解是全局最优解):

1.png

当K=7时,把7个虫洞的一端安装在同一个位置,做成一个具有8个出入口的超级虫洞,

然后对这8个出入口的位置进行模拟退火,就会收敛到以下这个局部最优解(也是全局最优解):

1.png

当K=8时,把8个虫洞的一端安装在同一个位置,做成一个具有9个出入口的超级虫洞,

然后对这9个出入口的位置进行模拟退火,就会收敛到以下这个局部最优解(也是全局最优解):

1.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-7-9 15:49:41 | 显示全部楼层
本楼层将会持续更新,陆续给出当N=2时,在周期性边界的1*1的正方形里,安装K=0,1,2,...对虫洞的最佳方案

当K=0时,两点的平均距离是(sqrt(2)+ln(1+sqrt(2)))/6,约等于0.3825978582321,参考文献的内容如下图所示:

1.png

当K=1时,两点平均距离的最小值约为0.361397,这对虫洞应该分别安装在(0,0)处和(1/2,1/2)处,

如下图所示(为了体现周期边界,画了3*3个周期):

1.png

K=2的最佳安装位置还在求解中...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-7 19:04 , Processed in 0.031880 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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