A4正方形

mathe

n=1显然正方形最优边长为1，n=2正方形最优边长为$\frac{\sqrt{2}}2$
n=3和n=4我们现在只能构造边长\(\frac12\), n=5和n=6我只能得出边长\(\frac{\sqrt{2}}3\)
n=7总算可以有所不同了，如图排放

边长\(\frac{\sqrt{2}}4\)是有空隙的，边长至少可以达到\(\frac{3+4\sqrt{2}}{23} \approx 0.37638496736923392153072847377559966584\)

wayne

要是能 确定 最优解的判定标准 也是一个重大突破。

王守恩

wayne 发表于 2020-10-22 09:55
要是能 确定 最优解的判定标准 也是一个重大突破。

\(\D\sqrt{2}\)的连分数：\(\D\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29}\frac{99}{70},\)
n=2×3，按2×3布置正方形，边长a=√2/3, 面积利用率=2/3·√2=0.94280904158206336586779248280647
n=5×7，按5×7布置正方形，边长a=1/5, 面积利用率=7/5/√2=0.98994949366116653416118210694679
n=12×17, 按12×17布置正方形，边长a=√2/17，面积利用率=12/17·√2=0.99826839696924356386001557003038
这些面积利用率很高的布置，显然是最优方案了。

mathe

\(u\times v\)构型的边长为\(\min\{\frac1u,\frac{\sqrt{2}}v\}\).
而如果中心多一个45度方向放置的正方形，那么假设边长为a,中间水平空b,垂直空c,
那么应该有\(\begin{cases}u a+b=1\\va+c=\sqrt{2}, b+c=\sqrt{2}a\end{cases}\)
得出$(u+v+\sqrt{2})a=1+\sqrt{2}$,即$a=\frac{1+\sqrt{2}}{u+v+\sqrt{2}}$.
这两种构型很多时候结果不错

mathe

我们可以尝试计算机随机撒点加逐步迭代的方法来找到较优的解。
i)由于所有正方形边长相等，在给定边长后，只需要中心的位置和一条对角线的方向就可以确定正方形了。
由此，随机撒点只需要随机产生各中心的坐标和一条对角线的方向即可。
ii) 开始我们可以让所有正方形充分小，使得各正方形不会相交，然后可以逐步让它们膨大直到再膨大会相交为止，最终的边界条件是某个正方形的某个顶点正好落在另外一个正方形的某边上或者落在A4矩形的边界上。
iii)在某些正方形无法继续膨胀的前提下，某些正方形可以通过平移的方法摆脱无法膨胀的局面，这一步也比较好判断，通常只要不超过两个顶点受到约束，就可以通过平移摆脱无法膨胀的局面，唯一需要关心的是如何平移可以使得迭代次数尽量减少，也就是平移后尽量各个顶点离其它部分正方形或矩形边界的距离能够较均匀（或者最差三个顶点），在步骤iii)中反复迭代若干此后返回步骤ii),如果所有正方形都无法通过平移的方法摆脱无法膨胀的局面，进入步骤四
iv)这个步骤中我们需要通过旋转加平移的方案使得正方形尽量摆脱无法膨胀的局面，这时，大部分小正方形都应该有三个或四个顶点落在其它约束线段上。
    对于每个这样的小正方形，我们假设它的中心坐标为(a,b), 其中一个顶点坐标为(a+s,b+t),于是余下各顶点坐标分别为(a+s,b-t), (a-s,b+t), (a-s, b-t).
   我们知道其中至少有三个顶点落在线性约束条件中，于是我们还会有三到四个线性约束条件。
   如果是四个约束条件，那么正好是四个变量四条约束方程，我们需要判断对应方程的行列式是否为0，如果非零，那么说明解唯一，已经处于无法改善的地位。
      但是如果行列式为0，说明可以去除一个约束方程，于是和三个约束条件的情况相等。
   于是在三个线性约束条件的情况下，我们的目标是找到一个解使得正方形对角线长度$s^2+t^2$尽量大，通过使用前面的三个约束条件，可以消除变量使得这里变化为单变量的二次函数，于是其极值必然在抛物线顶点或参数边界。由此，我们可以找到一个更新位置的新正方形，它会尽量和周边约束条件保持足够距离。
   （实际计算过程可能会更加复杂一些，可能需要考虑旋转后不巧会遇上其它新增加的约束条件，于是要添加新约束重新考虑）
   在至少每个正方形都经过此步骤处理后，可以继续回到步骤ii)进行迭代，知道达到一个不错的结果。

aimisiyou

mathe 发表于 2020-10-23 07:23
我们可以尝试计算机随机撒点加逐步迭代的方法来找到较优的解。
i)由于所有正方形边长相等，在给定边长后， ...

10个小正方形是什么情形？

mathe

aimisiyou 发表于 2020-10-23 11:07
10个小正方形是什么情形？

9个解决了吗？9个我只能找到边长$1/3$的方案，如果这样9～12的最优方案都是$1/3$

lsr314

8个正方形的可选方案有很多，边长最大是多少？

王守恩

wayne 发表于 2020-10-22 09:55
要是能 确定 最优解的判定标准 也是一个重大突破。

+ 表示歪放的正方形，- 表示正放的正方形
第n行的第一个数=\(\lbrack\sqrt{\frac{n}{\sqrt{2}}}\ \rbrack\)
1=1×1
2=1×2
3=1×2+1=2×2-1
4=2×2
5=2×3-1
6=2×3
7=2×3+1
8=2×4
9=3×3
10=3×4-2
11=3×4-1
12=3×4
13=3×4+1
14=3×5-1
15=3×5
16=3×5+1
17=3×5+2
18=4×5-2
19=4×5-1
20=4×5
21=4×6-3
22=4×6-2
23=4×6-1
24=4×6
25=4×6+1

dlpg070

mathe 发表于 2020-10-23 11:11
9个解决了吗？9个我只能找到边长$1/3$的方案，如果这样9～12的最优方案都是$1/3$

9～12的最优方案都是1/3
下面 n=10的排列 :
a=1/3
A4正方形_10_20201022.png

n=10正方形

显然 n=9,10,11,12 ,a=1/3成立