均分田地，田埂最短问题

gxqcn

有一块田地需要分给 $n$ 户，要求各户分得面积相等，
田地内部不同户分得的区域将建田埂以分隔（原待分地已有田埂圈定）。
现为实现耕地面积最大化，要求新建田埂总长度最小。请问如何规划？

注：
1、分后新修的田埂对所分面积均等性的影响忽略不计；
2、允许“孤立”田埂的出现，如内部可出现一个“圆田埂”；
3、允许各户分得的田地不连通，即块数可以不止一块。


大家可先来做具体化一点的：
如果是一个单位正方形田地，$n$ 分别等于 2、3、4、5、6、7、8、9、…… 时，该如何操作？新建田埂总长度为多少？


补记：
近期 KeyTo9_Fans 发出了系列最优化问题，比如：火车站的最佳位置、最优美的轨道，
受此影响，也提一个类似问题。
不过我没有 KeyTo9_Fans 那么会生动的描述，
而且问题也要简单得多（甚至不知是否已有人系统研究过）。


当前最优结果
单位圆

n	l	where	who
1	0	-	-
2	2	-	-
3	3	42#	KeyTo9_Fans
4	3.945702967	84#	mathe
5	4.833846644	87#	mathe
6	5.40679693	99#	mathe
7	6	95# 数据参考数学星空 31#	mjs1wh
8	6.647231018	104#	数学星空
		更多结果在176# 高精度结果在186#

正方形

n	l	where	who
1	0	-	-
2	1	-	-
3	1.623278144	13#	KeyTo9_Fans
4	1.975592885	13#	KeyTo9_Fans
5	2.502112930	11#	KeyTo9_Fans
6	2.939946252	114#	mathe
7	3.280726464	116#	mathe
		更多结果在177#

mathe

45~52的结果

mathe

44个区域

mathe

https://oeis.org/A307234
https://oeis.org/A307235
https://oeis.org/A307237
https://oeis.org/A307238
审批了将近五个月

mathe

圆形高精度(50位左右精度)结果:
  3:3
  4:3.94570296726718571384289955211179918887483540107474
  5:4.83384664352739678365771592855759637171533663888553
  6:5.40679692995192887512371620121291651425779887928260
  7:6
  8:6.64723101838026296233844737117921994339523666826884
  9:7.31494334143163622505321129278156560728393436742067
10:7.83705523333972942409003687995175306618088264742072
11:8.33879556032765074482357510437823919631005150791791
12:8.79971992014017690624852935788642518321310930864561
13:9.30306020602751419096827438455278908834415557610568
14:9.74761816428629100908678379829552349051458515109547
15:10.2109247126719321038177523750401521967132677261542
16:10.6002734544885987638741830061081758413742118687960
17:11.0127073444935589178833185607868742400845125059958
18:11.3810573669510245176813557546930807560310942014943
19:11.7268270551468228561661052616043727133110767411489
20:12.1636216798159273193165043412456407781626019889750
21:12.5275158346433593207967816926895353230777818924455
22:12.8982073589909613910094997128832638325464395082337
23:13.2626902433739724934801903945398696525353145329769
24:13.5899427733112380789081642421445386490436077809892
25:13.9344786134661845405039615773941622584465256916494
26:14.2527219956349376669253732438613330396954941339519
27:14.5508630543833282352363828099702501921022260948008
28:14.9050198661742857482436096966259636296125204407745
29:15.2097250229021614186808448690549756246002411984410
30:15.5023171403988526790113198595387272386730251249037
31:15.8295092386907821981649330668063947310730463805898
32:16.1216476819194932861652211864230205567342090983217
33:16.4029560015988280000023634592798483773989151476307
34:16.6873471363621888294345811799032656519722563389863
35:16.9528898952932945688880172700722678012262814419386
36:17.2072231122087160387383238826066663556531642925922
37:17.4609227894969986988120719317066949544443839197065
38:17.7742267467950455711519765606028183970560708248025
39:18.0536598673940756377290095823973019838987283796349
40:18.3202888205424160539674645539489689768434838337940
41:18.5938646562158577835524288084597187124762706151280
42:18.8489703098223545147309884016725110683781594277071
43:19.0920949918223182048671666134662299991492610140510

坐标数据在附件
allbest.tgz (202.69 KB, 下载次数: 7)

2019-8-12 11:37 上传

点击文件名下载附件

mathe

正方形划分为13份比较有意思，是正方形图形中第一个即不是轴对称也不是中心对称的图形

mathe

http://users.aber.ac.uk/sxc/MINPICS/best_candidates_1.pdf
已经计算到均分42份了
其中圆形，附件中边长C需要变换为$C\sqrt(\pi/n)-2\pi$可转化为176#的结果
其中正方形，附件中边长C需要变换为$C/sqrt(n)-4$可以转化为177#的结果。

mathe

随着区域数目变多，可以得出的局部最优点会越来越多，但是可以发现其中各局部最优点出现频率分布还是非常有规律的

比如上图代表将单位圆均分为10个区域时随机产生的14.4万个局部最优点时各局部最优点的频率分布，可以看出它们的频率很好的近似按指数递减
而其中找出的全局最优的结果具有较高的频率。
随机选择其它的
线面是对单位正方形均分7各区域随机产生23.3万个局部最优点时各局部最优点的频率分布。

趋势也类似，其中全局最优的结果同样具有较高的频率。
我们不妨假设全局最优的结果为各局部最优点的概率分布同上面频率分布类似（从实际结果看会更加偏向高频值）
由此可以估算出176#，177#中单位圆和正方形情况的划分方案已经是最优的概率都在99.99%以上。

mathe

还有链接:
http://users.aber.ac.uk/sxc/two_d_clusters.html

wayne

蛤蛤蛤我就先睹为快了.
这个网站太猛了,给出了图,还有解析解,作图的代码. 提出了构图遵循的几个原则
1) 直线或者圆弧
2)新的顶点只有三条边
3) 顶点是费马点,角度120度
4)边界的角度是90度
5)拉普拉斯原则: 顶点处的有向曲率之和为0

Principles for constructing equal area dissections with minimal cut length
� � straight lines or circle arcs
� � vertices with only 3 edges
� � equal angle vertices, 120�
� � joining border with right angle
� � Laplace rule: sum of signed curvatures at vertex is zero