A4正方形

dlpg070

dlpg070 发表于 2021-1-2 20:27
优秀解排行表文件存于附件,可能有误请指正
sqrt2.out:
998         {Va: n=27, w=35, a1=17,b1=1, a2=10,  ...

sqrt2_1_20210101.zip (17.67 KB, 下载次数: 4)

2021-1-3 09:14 上传

点击文件名下载附件

EN=15不够大,改为EN=20 ,排行表更新到附件sqrt2_1_20210101.txt
初步比较与sqrt2.out一致
最新统计结果:
EN=15    20
T0: 523    523 平放
V: 139  136 斜放
Va:177  180 斜放为主混排
Tk: 36   36 平放为主混排
Cm: 75    75 平放为主混排
Cm2:19   19 平放为主混排
Cu2: 6    6 平放为主混排

明显待修改:
1 n=3 (T2V,T2H 限制条件)
2 n=17 (n*n+1类型)
3 n= 27(n*n+2类型)

dlpg070

uk702 发表于 2021-1-3 07:41
n = 100、101 可能有改进空间。
应该也不可能了，9*11 意味着水平要排 9 个，因此不可能超过 1/9 = 0.111 ...

当初n=7第一次出现立排时引起轰动, n=26等+2类型也被寄予厚望,后来被斜排打败了,
现在T2V,T2H已经彻底退出优秀解行列
例如n=100,n=101 T2V和T2H 跌出前20名

n=100:前20名排行榜
1 100        Tk: 8*12+ 4         0.11273883840(0.89873594929)
2 100        {V: n= 9,u=10,w=12,s= 1,t=0.27000217891}         0.11184848626(0.88459651437)
3 100        {V: n= 9,u=10,w=12,s= 2,t=0.27000217891}         0.11184848626(0.88459651437)
4 100        {V: n= 9,u=10,w=12,s= 3,t=0.27000217891}         0.11184848626(0.88459651437)
5 100        {V: n= 9,u=10,w=12,s= 4,t=0.27000217891}         0.11184848626(0.88459651437)
6 100        {V: n= 9,u=10,w=12,s= 5,t=0.27000217891}         0.11184848626(0.88459651437)
7 100        T0: 9*12-8         0.11111111111(0.87297133480)
8 100        {H: n=13,u=20,w= 7,s=10,t=0.27000000000}         0.11052210468(0.86374052316)
9 100         {Vs: n=11, w= 1, s= 4, a1= 9, b1= 9, t=0.69854064992}         0.11029374309(0.86017487655)
10 100         {Va: n=10, w=10, a1= 5,b1= 1, a2= 1, b2= 2, t=0.54442406446}         0.11022705644(0.85913501997)
11 100        {H: n=13,u= 4,w=11,s= 1,t=0.24000000000}         0.10992638760(0.85445444825)
12 100        {H: n=13,u= 4,w=11,s= 2,t=0.24000000000}         0.10992638760(0.85445444825)
13 100        {H: n=13,u=17,w= 8,s= 4,t=0.24000000000}         0.10992638760(0.85445444825)
14 100        {H: n=13,u=17,w= 8,s= 5,t=0.24000000000}         0.10992638760(0.85445444825)
15 100        {H: n=13,u=17,w= 8,s= 6,t=0.24000000000}         0.10992638760(0.85445444825)
16 100        {H: n=13,u=17,w= 8,s= 7,t=0.24000000000}         0.10992638760(0.85445444825)
17 100        {H: n=13,u=17,w= 8,s= 8,t=0.24000000000}         0.10992638760(0.85445444825)
18 100        {H: n=13,u=26,w= 6,s=13,t=0.24000000000}         0.10992638760(0.85445444825)
19 100        {V: n=12,u= 7,w=12,s= 1,t=0.79738800185}         0.10990858166(0.85417766064)
20 100        {V: n=12,u= 7,w=12,s= 2,t=0.79738800185}         0.10990858166(0.85417766064)
n=101:前20名排行榜
1 101        {V: n= 9,u=14,w=11,s= 5,t=0.26688759682}         0.11179307207(0.89255740492)
2 101        {V: n= 9,u=14,w=11,s= 6,t=0.26688759682}         0.11179307207(0.89255740492)
3 101        {V: n= 9,u=14,w=11,s= 7,t=0.26688759682}         0.11179307207(0.89255740492)
4 101        {V: n= 9,u=15,w=11,s= 6,t=0.24068019938}         0.11137162345(0.88584038706)
5 101        {V: n= 9,u=15,w=11,s= 7,t=0.24068019938}         0.11137162345(0.88584038706)
6 101        T0: 9*12-7         0.11111111111(0.88170104815)
7 101         {Va: n= 9, w= 9, a1= 1,b1= 2, a2= 1, b2= 2, t=0.03367607843}         0.11075954992(0.87613038132)
8 101         {Va: n= 9, w= 9, a1= 1,b1= 3, a2= 1, b2= 1, t=0.03367607843}         0.11075954992(0.87613038132)
9 101         {Va: n= 9, w=10, a1= 1,b1= 2, a2= 1, b2= 1, t=0.03374968768}         0.11075892136(0.87612043727)
10 101         {Va: n= 9, w=11, a1= 1,b1= 1, a2= 1, b2= 1, t=0.03382396026}         0.11075828775(0.87611041339)
11 101        {V: n= 9,u= 2,w=13,s= 1,t=0.03396938193}         0.11075704896(0.87609081568)
12 101        {V: n=12,u= 5,w=13,s= 1,t=0.79737021943}         0.10990688733(0.86269283827)
13 101        {V: n=12,u= 5,w=13,s= 2,t=0.79737021943}         0.10990688733(0.86269283827)
14 101        {H: n=13,u=22,w= 7,s= 9,t=0.23000000000}         0.10975112529(0.86024932311)
15 101         {Va: n=10, w=12, a1= 3,b1= 1, a2= 1, b2= 1, t=0.53171957471}         0.10957245592(0.85745071681)
16 101         {Vs: n=11, w= 1, s= 4, a1= 8, b1=10, t=0.68875303273}         0.10955295541(0.85714554441)
17 101        {H: n=13,u= 8,w=10,s= 4,t=0.21000000000}         0.10943501410(0.85530098541)
18 101        {H: n=13,u=13,w= 9,s= 4,t=0.21000000000}         0.10943501410(0.85530098541)
19 101        {H: n=13,u=18,w= 8,s= 8,t=0.21000000000}         0.10943501410(0.85530098541)
20 101        {H: n=13,u=23,w= 7,s=10,t=0.21000000000}         0.10943501410(0.85530098541)

dlpg070

dlpg070 发表于 2021-1-3 11:21
当初n=7第一次出现立排时引起轰动, n=26等+2类型也被寄予厚望,后来被斜排打败了,
现在T2V,T2H已经彻底退 ...

n=100 最优解 Tk:
A4_100_3_20201215.png

n=100Tk

n=101 最优解 V: 从图看,似乎有Va更优秀解
A4斜排_101s5_20201231.png

n=101V

mathe

有没有人对15#中随机算法感兴趣？
10 对于每个小正方形，中心的坐标和一个顶点到中心的向量确定了这个小正方形。而由于所有小正方形大小相同，所以除了一个公共的边长参数以外，每个小正方形只用中心和一个单位方向向量就可以确定。
于是设第i个正方形中心坐标为$(x_i,y_i)$,其一个顶点到中心的方向倾斜角为$t_i$，而所有小正方形顶点到中心距离为$r$
于是第i个小正方形顶点坐标分别为$(x_i+r\cos(t_i),y_i+r\sin(t_i)),(x_i-r\sin(t_i),y_i+r\cos(t_i)),(x_i-r\cos(t_i),y_i-r\sin(t_i)),(x_i+r\sin(t_i),y_i-r\cos(t_i))$。
1. 于是在给定所有的$(x_i,y_i), t_i$, 根据各个顶点坐标必须在A4纸内部，我们得到16n条关于r的一次不等式。
另外我们知道第i个小正方形的所有顶点都必须在第j个小正方形的外部，或者说
$(x_i-x_j, y_i-y_j)$在向量$(\frac{\cos(t_j)-\sin(t_j)}2, \frac{\sin(t_j)+\cos(t_j)}2)$和$(-\frac{\sin(t_j)+\cos(t_j)}2,\frac{\cos(t_j)-\sin(t_j)}2)$两者上的投影长度必须有一个大于$\frac{\sqrt{2}r}2$,而这两个投影的长度都可以直接计算出来，由此对于每对不同的$(i,j)$都可以得出关于$r$的一个一次不等式,总共$n(n-1)$条关于r的不等式。
由此计算所有这些不等式，就可以得出满足条件的r的最大值。

2. 然后在依次假定n-1个小正方形已经确定的情况下，我们需要少量移动或旋转第n个小正方形，使得可以让它尽量的变大（提供更大的潜在扩展机会）。于是设这时假设膨胀以后第n个小正方形顶点到中心距离最大可以从r变大到$r_n$,那么记$c_n = r_n\cos(t_n), d_n = r_n\sin(t_n)$, 我们有变参$x_n,y_n,c_n,d_n$,同样要求它的四个顶点都在初始矩形内部，并且其它n-1个正方形（顶点坐标已知，大小采用参数r）的四个顶点都在这个正方形外部，以及它的四个顶点都在其它正方形的外部。但是这种判断会存在一定非线性，不好处理，需要根据初始状态那些顶点和那些边已经接触了，仅仅保留接触点处的不等式，使得$c_n^2+d_n^2$尽量大来找到最佳变换，这是一个相对比较简单的二次规划问题。

3.对每个不同的小正方形重复步骤2，并且迭代1～2步骤，可以不断的扩大r直到无法扩展。
不同的初始状态最后应该会收敛到不同的局部最优解。

uk702

mathe 发表于 2021-1-3 19:12
有没有人对15#中随机算法感兴趣？
10 对于每个小正方形，中心的坐标和一个顶点到中心的向量确定了这个小正 ...

我用 julia 写了一个最简单的，测试了 n = 9，只保证 9 个小正方形都在长方形内（若倾斜时超出长方形边界，就强制改成正放），还没有检查各个小正方形之间是否有交叠，就感觉效率太低了。

也不排除这个算法太糙的原因。

1. #随机生成9个点及倾角
   
2. using Random
   
3. 
   
4. n = 9
   
5. s = 1/3
   
6. h = sqrt(2)
   
7. ratio = 0.99
   
8. 
   
9. while true
   
10.         # a = (rand(n), sqrt(2)*rand(n), pi/2*rand(n))
    
11.         # for i=1:9 println((a[1][i], a[2][i], a[3][i])) end
    
12. 
    
13.         # 每个点离上下左右的距离必须大于等于 s/2
    
14.         ok = true
    
15.         c = zeros(n, 3)
    
16.         for i=1:n
    
17.                 for tr=1:10
    
18.                         b = rand(3)
    
19.                         c[i, 1] = s/2 + b[1]*(1-s)
    
20.                         c[i, 2] = s/2 + b[2]*(h-s)
    
21.                         c[i, 3] = pi / 2 * b[3]
    
22. 
    
23.                         ok = true
    
24.                         for j=1:i-1
    
25.                                 d = (c[j, 1] - c[i, 1])^2 + (c[j, 2] - c[i, 2])^2
    
26.                                 if d < (s^2) * ratio
    
27.                                         ok = false
    
28.                                         break
    
29.                                 end
    
30.                         end
    
31.                        
    
32.                         if ok
    
33.                                 p1 = [c[i, 1]-s/2*cos(c[i, 3])-s/2*sin(c[i, 3]), c[i, 2]-s/2*sin(c[i, 3])+s/2*cos(c[i, 3])];
    
34.                                 p2 = [c[i, 1]-s/2*cos(c[i, 3])+s/2*sin(c[i, 3]), c[i, 2]-s/2*sin(c[i, 3])-s/2*cos(c[i, 3])];
    
35.                                 p3 = [c[i, 1]+s/2*cos(c[i, 3])-s/2*sin(c[i, 3]), c[i, 2]+s/2*sin(c[i, 3])+s/2*cos(c[i, 3])];
    
36.                                 p4 = [c[i, 1]+s/2*cos(c[i, 3])+s/2*sin(c[i, 3]), c[i, 2]+s/2*sin(c[i, 3])-s/2*cos(c[i, 3])];
    
37.                                
    
38.                                 ok = false
    
39.                                 if p1[1] >= 0 && p1[1] <= 1 && p1[2] >= 0 && p1[2] <= h
    
40.                                         if p2[1] >= 0 && p2[1] <= 1 && p2[2] >= 0 && p2[2] <= h
    
41.                                                 if p3[1] >= 0 && p3[1] <= 1 && p3[2] >= 0 && p3[2] <= h
    
42.                                                         if p4[1] >= 0 && p4[1] <= 1 && p4[2] >= 0 && p4[2] <= h
    
43.                                                                 ok = true
    
44.                                                         end
    
45.                                                 end               
    
46.                                         end                       
    
47.                                 end
    
48.                                
    
49.                                 if !ok c[i, 3] = 0.0; ok = true end
    
50.                                 break
    
51.                         end
    
52.                 end
    
53. 
    
54.                 # 10 次为尝试失败
    
55.                 if !ok
    
56.                         break
    
57.                 end
    
58.         end
    
59.        
    
60.         if ok
    
61.                 # 生成 n 个小正方形
    
62.                 # r=zeros(n, 8)
    
63.                 # for i=1:n r[i, i], r[i, 2], r[i, 3], r[i, 4] = c[i, 1], c[i, 2], c[i, 3], c[i, 3] end
    
64.                 # 顶点1:
    
65.                 for i=1:n
    
66.                         p1 = [c[i, 1]-s/2*cos(c[i, 3])-s/2*sin(c[i, 3]), c[i, 2]-s/2*sin(c[i, 3])+s/2*cos(c[i, 3])];
    
67.                         p2 = [c[i, 1]-s/2*cos(c[i, 3])+s/2*sin(c[i, 3]), c[i, 2]-s/2*sin(c[i, 3])-s/2*cos(c[i, 3])];
    
68.                         p3 = [c[i, 1]+s/2*cos(c[i, 3])-s/2*sin(c[i, 3]), c[i, 2]+s/2*sin(c[i, 3])+s/2*cos(c[i, 3])];
    
69.                         p4 = [c[i, 1]+s/2*cos(c[i, 3])+s/2*sin(c[i, 3]), c[i, 2]+s/2*sin(c[i, 3])-s/2*cos(c[i, 3])];
    
70.                         println("r = Polygon[{{$(p1[1]), $(p1[2])}, {$(p2[1]), $(p2[2])}, {$(p3[1]), $(p3[2])}, {$(p4[1]), $(p4[2])}}]; sqs = Append[sqs, r];")
    
71.                 end
    
72.        
    
73.                 for i=1:n, j=1:i-1
    
74.                         d = (c[j, 1] - c[i, 1])^2 + (c[j, 2] - c[i, 2])^2
    
75.                         if d < (s^2) * ratio
    
76.                                 println((i, j, d, c[i, 1], c[i, 2], c[j, 1], c[j, 2]))
    
77.                                 exit(0)
    
78.                         end
    
79.                 end
    
80. 
    
81.                 println(reshape(c', 27))
    
82.                 exit(0)
    
83.         end       
    
84. end
    
85. 
    

复制代码

mathe

两个正方形不相交的充分必要条件是其中一个正方形的四个顶点都在另一个正方形某条边所在直线的外侧。

如图，正方形FGHI和ABCD不相交。所以FGHI的中心J必然也在ABCD外部，不妨设它在边CD的外侧。
如果FGHI每个点都在CD外侧，已经符合条件。不然必然有某个顶点G在CD内侧，有对称性，不妨设同时在BC外侧。
如果如上图，F在BC内侧，那么正方形ABCD四个顶点都在FG的外侧。不然FGHI四点都在BC外侧。
于是设正方形ABCD的中心为E，从计算角度来判断两个正方形是否相交，可以判断:
i)计算EF,EG,EH,EI在边AB所在直线上投影长度的最小值L1
ii)计算EF,EG,EH,EI在边BC所在直线上投影长度的最小值L2
iii)计算AJ,BJ,CJ,DJ在边FG所在直线上投影长度的最小值L3
iv)计算AJ,BJ,CJ,DJ在边GH所在直线上投影长度的最小值L4
那么两个正方形不相交的充分必要条件是L1,L2之一不小于AB的一半或
L3,L4之一不小于FG的一半。
比如上图中是仅L4不小于FG的一半，所以两者不相交。

uk702

mathe 发表于 2021-1-4 07:58
两个正方形不相交的充分必要条件是其中一个正方形的四个顶点都在另一个正方形某条边所在直线的外侧。

#195 的代码采取的是逐个增加的办法，可以考虑先选取一个较少的边长a，并保证前 n-1 个正方形互相不交叠，然后再尝试第 n 个正方形，这次只要保证第 n 个正方形与前 n-1 个正方形不交叠，这样就得到一个合适的解，如果这个解比之前尝试的所有 n 都要好，这就是一个更优的解。即使第 n 个正方形没找到合适的解（a 越接近最优解，找不到的概率就越高，远超过 99.9999...%），那我们至少得到 n-1 的解。

如果这个解的边长 a 并不最优，可尝试进行调整，比如说找到距离最近的两个点，然后各自退让一点点，再检测这些正方形是否交叠，这一步估计不难，也会得到稍微优化一点点的解。但这一步只能稍微调整一点点，很快就瓶颈了，局部调整再也没戏。

但如何进行多个正方形的调整，包括整体移位、旋转，感觉这个不好做。但如果不做这一步，全靠随机碰死老鼠，得到最优化解几无可能。事实上最优解都是满足整体布局要求的。

mathe

对于某个给定的候选解，必然有部分上面的不等式转化为等式。
比如顶点$(x_i+r\cos(t_i), y_i+r\sin(t_i))$到中心$(x_j,y_j)$的向量在边方向$(\frac{\cos(t_j)+\sin(t_j)}2, \frac{\cos(t_j)-\sin(t_j)}2)$的投影绝对值正好是$r$,比如
$F(x_i,x_j,y_i,y_j,t_i,t_j,r)=(x_i-x_j+r\cos(t_i))\frac{\cos(t_j)+\sin(t_j)}2+(y_i-y_j+r\sin(t_i))\frac{\cos(t_j)-\sin(t_j)}2=-\frac{sqrt{2}r}2$
于是我们需要选择稍微微调参数使得上面不等式左边继续变小。
也就是近似要求
$\frac{\partial F}{\partial x_i}\Delta x_i+\frac{\partial F}{\partial x_j}\Delta x_j+\frac{\partial F}{\partial y_i}\Delta y_i+\frac{\partial F}{\partial y_j}\Delta y_j +\frac{\partial F}{\partial t_i}\Delta t_i+\frac{\partial F}{\partial t_j}\Delta t_j + \frac{\partial F}{\partial r}\Delta r \le 0$
而一系列的等式约束，对应一系列的微调要求，可以对应一个线性不等式组。
我们需要判断对于给定的这个不等式组，是否存在解即可

hujunhua

mathe 发表于 2021-1-4 07:58
两个正方形不相交的充分必要条件是其中一个正方形的四个顶点都在另一个正方形某条边所在直线的外侧。

如 ...

两个大小相同的正方形`A_1A_2A_3A_4`和`B_1B_2B_3B_4`是否有重叠，就看四条边是否相交。
逐个计算边-边交点，如果碰到有一个相交，两个正方形就有重叠，
直到16个交点都不在边上（即在至少其中一边的延长线上），则两正方形就不相重叠。

如果两个正方形都用它的四个顶点来表示，那么判断两个正方形的边是否相交的算法如下。
正方形A的边`A_iA_j`上的点为`α(A_j-Ai)+A_i`,(`0≤α≤1`,即`α(1-α)≥0`)
正方形B的边`B_kB_l`上的点为`β(B_l-B_k)+B_k`,(`0≤β≤1`,即`β(1-β)≥0`)
它们的交点可以用方程`α(A_j-Ai)+A_i=β(B_l-B_k)+B_k`，即\[
(A_i-A_j,B_l-B_k)\begin{pmatrix}α\\β\end{pmatrix}=A_i-B_k
\]的解`(α,β)`来表示，当且仅当`α(1-α)≥0∧β(1-β)≥0`时两边相交，否则不相交。

uk702

hujunhua 发表于 2021-1-4 10:22
两个大小相同的正方形`A_1A_2A_3A_4`和`B_1B_2B_3B_4`是否有重叠，就看四条边是否相交。
逐个计算边- ...

我原先的想法跟胡老师的方法一样，但在 n=9 时试了试，只走了第一步就感觉无法走下去了，个人觉得关键是要搞定如何整体调整，mathe 老师的方法或许是条道。

另外一种思路是，先用 T0 的方法把 u*v 个小正方形摆好，再用平移(包括斜向平移) + 裁减若干正放的小正方 + 到处开窗来尝试，这种思路可能可以打破局部性，难点依旧是如何处理斜放的正方形， mathe 老师想来这方面很拿手。