均分田地，田埂最短问题

查看数: 199378 | 评论数: 188 | 收藏 0

关灯 | 提示：支持键盘翻页<-左右->

帖子模式

gxqcn

发布时间: 2010-11-11 08:54

正文摘要:

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

mathe 发表于 2019-10-21 10:21:49

45~52的结果

mathe 发表于 2019-9-4 15:57:06

44个区域

mathe 发表于 2019-8-17 07:38:02

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

mathe 发表于 2019-8-11 19:12:50

圆形高精度(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)

评分

参与人数 1	威望 +6	金币 +6	贡献 +6	经验 +6	鲜花 +6	收起理由
王守恩	+ 6	+ 6	+ 6	+ 6	+ 6	赞一个!

查看全部评分

mathe 发表于 2019-8-3 20:30:14

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

mathe 发表于 2019-8-3 19:37:37

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

看图中圆形结果，24一下的最优结果都具有一定的对称性。但是超过25以后，开始出现很多不对称的结果，很有可能这时找到的已经不是最优结果了发表于 2019-8-5 08:50

评分

参与人数 1	贡献 +12	经验 +12	鲜花 +12	收起理由
数学星空	+ 12	+ 12	+ 12	太强大啦～

查看全部评分

mathe 发表于 2019-8-3 19:18:37

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

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

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

mathe 发表于 2019-8-3 18:49:12

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

wayne 发表于 2019-8-3 08:34:29

蛤蛤蛤我就先睹为快了.
这个网站太猛了,给出了图,还有解析解,作图的代码. 提出了构图遵循的几个原则
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