紧凑排版

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

onlooker

您好，我最近也想弄一个类似的排版插件，但是没有什么思路，想听一点你的思路

qjchen

packing问题都是很难，这里有一篇文章是关于此题目算法的

https://arxiv.org/ftp/arxiv/papers/1402/1402.0557.pdf

作者觉得在当时，这篇文章是
Overall, our algorithms represent the current state-of-the-art for this problem, outperforming other algorithms by orders of magnitude, depending on the benchmark.

mahuan1279

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

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

可惜看不懂英文……

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中.这应该是它的局限.

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

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