一个著名题目——等距排布问题

mathe

然后看n=19的构图就很清晰了，都是n=20时的情况去掉一个4度点，边数从54减到50. 而每个图中都可以看到3个半同方向的半正六边形








n=18的图比较复杂，应该有n=19去掉一个四度点和n=17加上一个三度点，另外类似n=17有几个使用了复数点的图需要淘汰。

总体上，现在规律很明显。通过度数比较低的点的图使用笛卡尔积构图（并且在自由度过高时添加额外边）得到一些点数更多的优秀图。然后通过在这些优秀图片上额外添加或删除部分点得到更多优秀图。

mathe

我们发现笛卡尔积模式对于等距排布效率比较高。
如果我们有两个等距排布G1,G2,其中每个点可以用一个向量表示.
其笛卡尔积就是向量集合\(\{g1+g2| g1 \in G1, g2 \in G2\}\).
由于平移和旋转不改变等距排布图的属性，所以上面排布过程中，两个图中原点可以任意选取，并不改变图的性质。
另外，这个笛卡尔积的过程中，由于我们可以只旋转其中一个图，所以得到结果会增加一个自由度。
而从边的数目来看，如果两个图的点、边数目分别为v1,e1,v2,e2, 那么笛卡尔积图的点的数目就是v1*v2,而边的数目为v1*e2+v2*e1. (实际上由于增加了额外自由度，后续还可能可以继续添加边，但是数目不会小于这个值)。为了分析方便，我们先看v1=v2的情况，那么这个图点的数目从\(v1\)增加到\(v1^2\)，边的数目从\(e1\)增加到\(2v1e1\),所以如果我们反复平方，那么点的数目的对数值会从\(\ln(v1)\)变换到\(2^k \ln(v1)\), 边的数目从\(\ln(e1)\)增加到\((2^k-1)\ln(v1)+k\ln(2)+\ln(e1)\), 也就是边的数目为\(e=O(v\ln(v))\), 由此可以看出，初始v的数目接近e的时候效率会比较高。
由此看出，我们应该尽量选择n=2和n=3作为初始构图。
这样我们就可以将问题转为化若干个n=2和n=3的小图，进行多重笛卡尔积，得到一个\(2^u 3^v\)阶图，其中边数为\(2^{u-1}3^v(u+2v)\), 另外包含u+v-1个自由度，于是我们还可以额外添加一些边。
对于图中每个点，我们可以用u+v的向量表示，比如写成\((a_1,a_2,...,a_{u+v})\),
如果我们现在再两个不同点\((a_1,a_2,...,a_{u+v})\)和\((b_1,b_2,...,b_{u+v})\)之间填了一条额外的单位边，如果两个点有某个分量相同
比如\(a_1=b_1\),根据各子图的平移不变性，我们可以发现，这个维度的分量从\(a_1\)改为任意其它值的两个点之间距离也会是1（而且和原先分量必然平行相等），所以我们一次性就可以添加多条边。这种重复的分量越多，一次性获得的额外边会越多。
当然我们不能选额两个自有一个分量不同的点（这代表它们在原先同一个子图中，已经无法额外加边了），所以为了一次性可以添加尽量多的边，我们会选择某些只有两个分量不同的点之间加边。而且为了有效性，这两个分量不同的子图越小越好（对应余下相同的子图尽量大），所以我们会优先选择2个点的子图上分量不同。如果有两个两点子图，那么必然先通过在它们上面添加一条边，合并成要给n=4,e=5的子图。在所有n=2的子图都合并以后（或者只余下一个），开始合并n=3的子图，...，然后到最后所有子图合并为1个，这样通过贪心法就可以得到一个比较不错的结果。唯一的问题是这种额外边不总是能添加成功，比如n=2和n=3进行合并，得到n=6时，无法添加额外边。

数学星空

22个点的前十图形结果（括号里数字为mathe 文件sg ）

N=22-1 (61)

ABAEAVBJBMBVCGCHCICNDFDMDRDSDVEFEKELEVFPFQFVGHGMGRGTHMHSHUINIOIRISJKJLJNJOKLKPKTLQLUMOMVNONTNUOPOQPQPRPTQSQURSRTSUTUTVUV





N:=22-2 (143)

ABAEAVBJBMBVCGCHCICNDFDMDRDSDVEFEKELEVFPFQFVGHGMGRGTHMHSHUINIOIRISJKJLJNJOKLKPKTLQLUMOMVNONTNUOPOQPQPRPTQSQURSRTSUTUTVUV





N:=22-3 (27)

ABAGASAVBHBRBVCICJCQCSDKDLDQDREFEHENEPEVFGFMFOFVGIGJGVHKHLHVIJIMITJOJUKLKNKULPLTMOMPMSMTNONPNRNUOSOUPRPTQRQSQTQURSTUTVUV





N:=22-4 (163)

ABAGASAVBHBRBVCICJCQCSDKDLDQDREFEHENEPEVFGFMFOFVGIGJGVHKHLHVIJIMITJOJUKLKNKULPLTMOMPMSMTNONPNRNUOSOUPRPTQRQSQTQURSTUTVUV





N:=22-5 (60)

ABAHANATBHBMBSCDCGCOCQDGDPDREIEOEPEUFJFMFNFVGLGUGVHKHUHVIKIQIRIUJLJSJTJVKMKNKULOLPLVMNMQMSNRNTOPOQOSPRPTQRQSQVRTRVSTSUTU





N:=22-6 (420)

ABAHANATBHBMBSCDCGCOCQDGDPDREIEOEPEUFJFMFNFVGLGUGVHKHUHVIKIQIRIUJLJSJTJVKMKNKULOLPLVMNMQMSNRNTOPOQOSPRPTQRQSQVRTRVSTSUTU





N:=22-7 (43)

ABAIAVBNBRBVCJCKCQCRDEDFDGDPELEPESEVFGFHFTFVGHGLGUHNHQHSIKIPIRISJMJNJOJQKMKRKTLNLOLULVMOMSMTMVNQNVOROSOUPSPTPUQTQURUTUTV





N:=22-8 (213)

ABAJAKBLBMBTCFCHCKCSDIDMDQDSEGEIEMERFNFQFSFTGLGOGPGRHJHKHNHUIMIOIVJKJLJQJRKTKVLNLRLTMPMUNPNTNUOPOQOTOVPQPUQSRURVSUSVTVUV





N:=22-9 (57)

ABAKASBNBPBUCICKCMCPDIDODPDQEFEGEHEOFGFJFRFVGJGTGUHOHQHRHUIPISITJMJNJQKLKMKNKSLPLQLRLSLVMNMTMVNRNUOQOTOVPVQSRURVSTSUTUTV





N:=22-10 (434)

ABAKATAVBHBKBRCHCQCRCUDGDJDPDTEIENEQESFGFIFNFPGLGPGVHRHSHVINIUIVJLJMJOJTKOKPKSLMLNLSLVMNMPMQMUNROQOROSOTPUQSQURTSVTUTVUV

数学星空

n=22 的46个结果见附件：

1~16.zip (958.55 KB, 下载次数: 0)

5 天前 上传

点击文件名下载附件

17~30.zip (988.87 KB, 下载次数: 0)

5 天前 上传

点击文件名下载附件

31~46.zip (1014.43 KB, 下载次数: 0)

5 天前 上传

点击文件名下载附件

wayne

感觉n=21的时候,有个图不属于 笛卡尔积的模式,而是 三个正六边形 两两交织.

mathe

这个就是最简单的笛卡尔积形式。
N=7有7个向量{A0,A1,A2,A3,A4,A5,A6}, N=3有3个向量{B0,B1,B2}
笛卡尔积就是21个向量\(\{A_i+B_j| 0\le i \le 6, 0\le j \le 2\}\)
比如我们这里可以使用复平面选择A0=0, A1 = \(\omega\) 为六次单位根， A2,...,A6分别是A1的2到6次方。
同样选择B0=0, B1为任意一个单位向量， B2=B1*A1, 于是B0,B1,B2是一个正三角形。

wayne

我是肉眼观察所有的最优解. 总结 在欧氏几何空间下 n的最优图解 是不是由 k的最优图 跟 n-k的最优图  的点集合的 二元笛卡尔直积构成. 在我这个思路下, 刚才那个图 就是唯一的一个异类.
如果我的观察成立,那么靠这种算法迭代下去的时间复杂度应该比较低.

wayne

我发现这个图的外轮廓 是一个 等边的九边形,但无法做到正九边形.
\[\left(
\begin{array}{c}
\{\text{A},\{0,0\}\} \\
\left\{\text{B},\left\{\sin \left(\frac{1}{6} (\pi -6 \theta )\right),\cos \left(\frac{1}{6} (\pi -6 \theta )\right)\right\}\right\} \\
\left\{\text{C},\left\{\sin \left(\theta +\frac{\pi }{6}\right),-\cos \left(\theta +\frac{\pi }{6}\right)\right\}\right\} \\
\{\text{D},\{1,0\}\} \\
\left\{\text{E},\left\{\frac{1}{2},\frac{\sqrt{3}}{2}\right\}\right\} \\
\{\text{F},\{2 \cos (\theta ),2 \sin (\theta )\}\} \\
\left\{\text{G},\left\{\frac{1}{2} \left(\sqrt{3} \sin (\theta )+3 \cos (\theta )\right),\frac{1}{2} \left(3 \sin (\theta )-\sqrt{3} \cos (\theta )\right)\right\}\right\} \\
\left\{\text{H},\left\{\sqrt{3} \cos \left(\theta +\frac{\pi }{6}\right),\sqrt{3} \sin \left(\theta +\frac{\pi }{6}\right)\right\}\right\} \\
\left\{\text{I},\left\{2 \cos (\theta )+\frac{1}{2},\frac{1}{2} \left(4 \sin (\theta )+\sqrt{3}\right)\right\}\right\} \\
\{\text{J},\{2 \cos (\theta )+1,2 \sin (\theta )\}\} \\
\left\{\text{K},\left\{\frac{1}{2} \left(\sqrt{3} \sin (\theta )+3 \cos (\theta )+1\right),2 \sqrt{3} \sin \left(\frac{\theta }{2}\right) \cos \left(\frac{1}{6} (\pi -3 \theta )\right)\right\}\right\} \\
\left\{\text{L},\left\{\frac{1}{2} \left(\sqrt{3} \sin (\theta )+3 \cos (\theta )+2\right),\frac{1}{2} \left(3 \sin (\theta )-\sqrt{3} \cos (\theta )\right)\right\}\right\} \\
\left\{\text{M},\left\{\sqrt{3} \cos \left(\theta +\frac{\pi }{6}\right)+1,\sqrt{3} \sin \left(\theta +\frac{\pi }{6}\right)\right\}\right\} \\
\left\{\text{N},\left\{\sqrt{3} \cos \left(\theta +\frac{\pi }{6}\right)+\frac{1}{2},\frac{1}{2} \sqrt{3} \left(2 \sin \left(\theta +\frac{\pi }{6}\right)+1\right)\right\}\right\} \\
\left\{\text{O},\left\{\sin \left(\theta +\frac{\pi }{6}\right)+\frac{1}{2},2 \sin \left(\frac{\theta }{2}\right) \sin \left(\frac{1}{6} (3 \theta +\pi )\right)\right\}\right\} \\
\left\{\text{P},\left\{\sin \left(\frac{1}{6} (\pi -6 \theta )\right)+1,\cos \left(\frac{1}{6} (\pi -6 \theta )\right)\right\}\right\} \\
\left\{\text{Q},\left\{\sin \left(\theta +\frac{\pi }{6}\right)+1,-\cos \left(\theta +\frac{\pi }{6}\right)\right\}\right\} \\
\left\{\text{R},\left\{\sin \left(\frac{1}{6} (\pi -6 \theta )\right)+\frac{1}{2},2 \cos \left(\frac{1}{6} (\pi -3 \theta )\right) \cos \left(\frac{\theta }{2}\right)\right\}\right\} \\
\{\text{S},\{\cos (\theta ),\sin (\theta )\}\} \\
\left\{\text{T},\left\{\cos (\theta )+\frac{1}{2},\sin (\theta )+\frac{\sqrt{3}}{2}\right\}\right\} \\
\{\text{U},\{\cos (\theta )+1,\sin (\theta )\}\} \\
\end{array}
\right)\]