紧凑排版

mahuan1279

有n个矩形，如何无重叠组合使得它们的外接矩形面积最小？

landsat99

qjchen 发表于 2023-2-22 21:17
packing问题都是很难，这里有一篇文章是关于此题目算法的

https://arxiv.org/ftp/arxiv/papers/1402/140 ...

排样问题 确实很难有通用方案。受不同条件约束，差异较大。

大致看了下..  Alto研究中心这篇paper基本解决了两种特定构型(它称为Benchmarks)的排样.
并分析了算法的内存、CPU消耗.
两种构型是对加州大学(Korf，2003 年）的N*N构型是很大扩展 (作者Huang称是此构型目前最优秀的算法）
构型分别为：
1. 定向等周长矩形 (Oriented Equal-Perimeter)的排样
   Benchmarks： 1 × N、2 ×(N-1)、...、(N-1)× 2 和 N × 1
2. 无定向 双周长矩形(Unoriented Double-Perimeter Rectangles)的排样
   Benchmarks： 1 ×(2N-1)、2 ×(2N-2)、...、(N-1)× (N+1) 和 N × N


个人理解，此算法本质是增加了约束条件的一种枚举法。算法比较巧妙，确实可能得到理论的最优解.
此Benchmark的丝路，较难扩展到其它Benchmarks，特别是无规律的Rectangle中.这应该是它的局限.

与目前主流的最低扫描算法+遗传、蚁群的迭代优化相比较，此方法是个全新的思路。特别对有某种规律的原料尺寸，可能相当适用。

感谢楼上大咖的资料推荐！

mahuan1279

有23个矩形零件，尺寸分别如下
length     wide
400       230
400       160
340       130
246       100
350       100
170       110
220       120
420       280
330       220
290       170
230       200
210       170
260       150
180       160
200       180
245       160
210       200
220       140
250       170
300       300
350       320
320       280
165       150

mahuan1279

mikewolf2k 发表于 2020-5-18 10:59
那就是母版有尺寸限制。
即便母版有尺寸限制，还是不明白这个想法有什么实际意义。买来的母版尺寸宽度是 ...

就是根据最高利用率时的外框矩形来定制母板尺寸啊，比如母板长宽限定都不超过10，而8*7母板会浪费16%，6*9母板会浪费14%，遵照母板面积相对小且利用率相对高的原则来挑选母板尺寸并对应下料方式。

mikewolf2k

如何证明面积最小？

mahuan1279

mikewolf2k 发表于 2020-5-18 08:55
如何证明面积最小？

越接近（n个矩形总面积）越好。不一定要找到最小（可能很费时），在合理时间内找到较好的近优解也可以。

mikewolf2k

前面不是有贴图，有软件了么。

mahuan1279

软件是下料软件，即在规定的母板上裁出。此题这个没有母板尺寸限定，只要满足组合在一起耗费的外框矩形总面积越小越好。

mahuan1279

mikewolf2k 发表于 2020-5-18 10:06
前面不是有贴图，有软件了么。

我是用下料软件逐步试算出来的（即限定一个底宽且高无限的母板），然后比较底宽为多少时最优，得到那个软件图。逐步试算好费时，比如底宽从100试算到200，逐步加1.

mikewolf2k

  没有尺寸限制，有什么实际意义？比如全是宽100的长不等的方形，面积最小的肯定是这些方形串起来，一点都不会浪费，这样得出的一个宽100，长无限的母板，有什么用？

mahuan1279

mikewolf2k 发表于 2020-5-18 10:45
没有尺寸限制，有什么实际意义？比如全是宽100的长不等的方形，面积最小的肯定是这些方形串起来，一点都 ...

长宽有一个大范围限定。不可能一个方向无限长。

mikewolf2k

  那就是母版有尺寸限制。
即便母版有尺寸限制，还是不明白这个想法有什么实际意义。买来的母版尺寸宽度是固定的，假设都是三米宽，如果宽度3000X5000，浪费20%，如果宽度2900*6000，浪费1%，那怎么下料？把3000宽的先割掉100成2900，这样一共用6000长？

写不完的日记

很喜欢你发的东西