本帖最后由 mahuan1279 于 2020-10-12 10:59 编辑
有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
您好，我最近也想弄一个类似的排版插件，但是没有什么思路，想听一点你的思路{:1_1:}
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.
qjchen 发表于 2023-2-22 21:17
packing问题都是很难，这里有一篇文章是关于此题目算法的
https://arxiv.org/ftp/arxiv/papers/1402/140 ...
可惜看不懂英文……
本帖最后由 landsat99 于 2023-2-23 17:07 编辑
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中.这应该是它的局限.
与目前主流的最低扫描算法+遗传、蚁群的迭代优化相比较，此方法是个全新的思路。特别对有某种规律的原料尺寸，可能相当适用。
感谢楼上大咖的资料推荐！