|
|
一、二维矩形排样问题介绍
二维矩形排样问题可以简单理解为：给定一个矩形的材料，需要从上面切割出多个尺寸不同的小矩形，应该如何切割才可以使得材料的利用率最高。
二、方法介绍
小编觉得求解该问题的有以下关键步骤：
1、如何生成小矩形的可放置位置
小编通过实时更新已放小矩形最顶端的红线来生成新的位置，即下图的p1,p2,p3,p4。小编通过链表的方式来存储这些红线，即存储p的x,y坐标和线的长度。
当将一个矩形的左下角放到p4中时，若R4的宽等于l4的长度，或者很接近于l4的长度时（可以用当前所存在小矩形的最小边来判断，若l4的长度减去R4的宽小于最小边，则无需生成线l5），我直接将l4上移到R4顶端;否则，将l4的长等于R4的宽，并生成新的线l5。（注意，这里的小矩形的宽指的是平行于x轴的边的长度）
当选择的位置无法放入任何一个矩形时，我直接将该位置的线直接移动到与相邻两线中较矮的一条线同高的位置，若相邻的线只有一根时，直接移动到高线的高度即可。（注意：移动之后，要将两线合并，生成一根更长的线，即生成一个更宽的位置。）
至于说第一个矩形怎么选择，小编是选择序列的第一个小矩形，这样随着序列的改变，解也会改变。而第一根红线地生成也简单，就是大矩形的最下边。
2、如何从可放置位置中选择一个可放置位置来执行当前的小矩形排布
由于小编的偷懒，便选择了最简单的方式，就是选择y最小的那个位置。
3、如何选择最适合2中所选择的可放置位置的小矩形
这里小编也是选择了最简单的方式，即评分的方式，将每个小矩形放到这个位置中，然后给它打一下分。小编的打分方式为：
(int)((小矩形的宽/位置的长度)*100)/10
对于相同最高分的矩形，小编选择序列中的第一个最高分的矩形。之所以选用上面的打分方式，实际是为了让后面的启发式算法起到更大的作用，否则面对同样的位置，肯定会优先选择宽最接近位置的长度的那个小矩形，这样解的变异能力就变差了。应用小编的方法，即不管是0.96还是0.91，最终的得分都是9分，这样随着序列的变化，解也会相应地变化。当然，这个打分方法只是最简单的一种方式，还有多种方法可以选择。比如一个矩形和空间的匹配度越越高，得分就越高，这样不只是考虑宽，还要考虑高，使用这种打分方法得到的解层与层之间会比较平整。其他的方法小编就不讲了，大家自由去想象。（注意：小矩形是可以旋转的，打分的时候最好旋转一下来打一下分，这样解更好一点）
4、如何更新解
更新解的方法也很简单，只要更新小矩形的序列即可，谈到更新序列这种东西，启发式算法再适合不过，小编使用的是禁忌搜索，当然其他启发式也是完全可以滴，大家可以多用几种方法，然后自己对比一下哈。
[img]https://img-blog.csdnimg.cn/3df3a137d88f430fac24cce9fd44c5de.gif#pic_center[/img] |
|
发表于 2024-6-22 09:46:18
