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

KeyTo9_Fans

本贴考虑的空间是一个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对虫洞安装位置的平面图绘制出来

KeyTo9_Fans

我来解决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对虫洞，那么长度为1的、周期性边界的线段上，两个点的平均距离的最小值是3/16，等于0.1875

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



如果安装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处，如下图所示：



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

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



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

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

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

最佳安装方案也是令K对虫洞的一端全都位于同一个点上，做成一个具有(K+1)个出入口的虫洞，然后用这些出入口把圆环均分成(K+1)段即可

mathe

N=1时看上去还是比较好分析的，但是N大了就太复杂了，也不容易理解。
N=1没有虫洞时，我们可以看成一条长度为1的绳子头尾相接得到的一个圆环。
而有一对虫洞时，相当于把圆环上两个点叠在一起打了个结，就变成一个8形的结构。
  两对虫洞，相当于在8形结构上再找两个点打结，当这两个点在一个圈上时，就变成三个接在一起的环；当这两个点在不同的圈上打结，得到结果相当于两个点，中间有四条边相连。
更加一般的，有K对虫洞情况，打结后得到是一个有K个点的连通图，图上每个点的度数都是4.
N=1时，K对虫洞最优解我猜测把这K对一侧全部放在一起，另外一侧均匀分布，整个圆环均匀划分为K+1段的情况。平均距离$\frac{2K+1}{4(K+1)^2}$.

KeyTo9_Fans

我对没有周期性边界的情况也是挺感兴趣的

本楼层将会持续更新，陆续给出当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...，如下图所示：



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



当K=2时，模拟退火算法会收敛到以下2个局部最优解（右边的解是全局最优解）：



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



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

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



#####

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



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

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

目前可以确定的是：

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

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

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



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

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

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

#####

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

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



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

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



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

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

KeyTo9_Fans

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

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



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

如下图所示（为了体现周期边界，画了3*3个周期）：



K=2的最佳安装位置还在求解中...