1. 从“乱放”到“排样”一个看似简单却充满挑战的工程问题如果你曾经尝试过把一堆大小不一的箱子塞进一个有限空间的货柜里或者玩过俄罗斯方块那么你已经直观地接触过“二维矩形排样”问题的核心。在工业制造、物流仓储、服装裁剪、芯片布局乃至我们日常的搬家打包中如何将一系列矩形物品无重叠、高效率地放置在一个更大的矩形区域内是一个无处不在的优化难题。这不仅仅是简单的“摆放”其背后是数学、计算机科学和运筹学的深度结合目标是在满足各种约束如方向固定、切割工艺、材料利用率的前提下最大化空间利用率或最小化原材料浪费。我最初接触这个问题是在一个板材切割的数学建模项目中。客户提供了一批订单每张订单包含几十种不同尺寸的矩形零件我们需要将它们排布在标准尺寸的大板材上目标是使用尽可能少的板材。手动尝试了几次后我立刻意识到这绝非人力所能及——可能的排列组合数量是天文数字。于是转向算法和代码求解成了唯一出路。而MATLAB凭借其强大的矩阵运算能力、丰富的可视化工具以及相对友好的语法成为了实现这类离散优化算法的理想试验场。今天我就来详细拆解一下如何从零开始用MATLAB实现一个基础的二维矩形排样算法。我们将聚焦于一个经典场景所有矩形方向固定不能旋转需要放入一个宽度固定、高度可变的板材中目标是寻找一个排样方案使得最终所需的板材高度最小。这个过程本质上就是在求解一个二维的装箱问题2D Bin Packing Problem。2. 算法核心如何教会计算机“聪明地”摆放矩形在动手写代码之前我们必须先确定让计算机遵循的“摆放规则”也就是算法策略。二维矩形排样属于NP-Hard问题意味着没有能在多项式时间内找到绝对最优解的通用算法对于大规模问题。因此实践中我们采用各种启发式算法来寻找“足够好”的可行解。其中最低水平线算法Bottom-Left Fill, BLF及其变种因其简单、高效且效果不错成为了入门和实践的首选。2.1 最低水平线算法BLF原理拆解你可以把待排样的矩形板材想象成一个不断增高的容器。算法的核心思想是总是将下一个待放置的矩形放在当前已放置矩形所形成的“轮廓线”中尽可能低且靠左的位置。具体来说算法维护一个叫做“轮廓线”的数据结构。这条线由一系列水平线段组成代表了当前板材内部空间的“可放置顶部边界”。初始时轮廓线就是板材的底边一条从x0到x板材宽度的水平线段高度为0。放置一个矩形的过程如下扫描轮廓线从左到右遍历当前的轮廓线寻找一个空隙。这个空隙必须满足其宽度大于等于待放置矩形的宽度并且其高度由轮廓线在该段的y坐标决定是当前所有可行空隙中最低的。放置矩形将矩形的左下角对齐找到的这个最低空隙的最左端。这样矩形就“坐”在了这段轮廓线上。更新轮廓线矩形放置后它会挡住其下方的轮廓线并形成新的、更高的轮廓线段。我们需要删除被矩形覆盖的旧轮廓线段并在矩形的顶部增加新的水平线段。这个过程就像用一块积木填补了坑洼并创造了新的“地面”。这个算法的“贪心”之处在于它只着眼于当前这一步将矩形放在当前看来最“踏实”最低的位置而不考虑对后续矩形放置的全局影响。尽管如此它通常能产生较为紧凑的排样。2.2 关键细节与变种策略单纯的BLF有时会产生细长的空隙导致空间浪费。因此我们通常需要引入一些优化策略矩形排序策略先放哪个矩形后放哪个矩形对结果影响巨大。常见的排序规则包括面积降序先放置面积大的矩形。大矩形先定下格局小矩形用来填充缝隙这符合直觉。宽度降序/高度降序优先放置更长边较大的矩形。综合排序例如按max(宽度高度)降序排列。 在代码中我们可以在排样开始前对矩形列表按照选定规则进行一次排序。这是提升排样质量最简单有效的手段之一。空隙合并与轮廓线管理高效的轮廓线数据结构是算法性能的关键。我们需要能够快速查询最低可行位置并高效地更新轮廓线。通常可以用一个列表或优先队列来存储轮廓线的各个线段记录其左端点x、右端点x和高度y。在更新时需要仔细处理线段的分割、合并与删除操作这是算法实现中最容易出bug的部分。放置策略微调除了“最低且最左”还有“最佳匹配”等变种即不仅考虑高度最低还考虑放置后剩余空间的形状是否“更好”但这会显著增加计算复杂度。在我们的MATLAB实现中我们将采用“按高度降序排序 基础最低水平线算法”作为核心。选择高度降序是因为在我们的目标最小化板材高度下优先固定高度大的矩形有助于快速“撑起”布局的框架限制布局的高度增长。3. MATLAB实现步骤详解从数据结构到可视化理论清晰后我们开始用MATLAB将其转化为代码。整个过程可以分为几个清晰的模块。3.1 数据准备与初始化首先我们需要定义问题的输入和核心数据结构。% 1. 定义板材和矩形数据 plate_width 100; % 板材固定宽度 rect_list [30, 20; 25, 25; 15, 40; 40, 10; 20, 30; 10, 10]; % N x 2 矩阵每行 [宽度 高度] num_rects size(rect_list, 1); % 2. 按高度降序对矩形进行排序排序策略 [~, sort_idx] sort(rect_list(:, 2), descend); % 按第二列高度降序排序 sorted_rects rect_list(sort_idx, :); % 3. 初始化轮廓线 % 轮廓线表示为一组水平线段每条线段格式[y, x_left, x_right] % 初始轮廓线就是板材底部高度为0从x0到xplate_width skyline [0, 0, plate_width]; % 4. 初始化记录每个矩形放置位置的结果矩阵 % 格式 [rect_index, x_left, y_bottom, width, height] placed_rects zeros(num_rects, 5); placed_count 0;这里skyline变量是我们的核心。它是一个矩阵每一行代表轮廓线中的一段。[0, 0, plate_width]表示在高度y0处有一条从x0延伸到xplate_width的线段即空白板材的底部。3.2 核心排样循环寻找最低可放置位置接下来我们遍历排序后的矩形列表为每个矩形寻找家。for i 1:num_rects current_width sorted_rects(i, 1); current_height sorted_rects(i, 2); best_y Inf; % 初始化最佳放置点的高度为无穷大 best_x 0; % 对应的x坐标 best_seg_idx 0; % 找到的最佳轮廓线段索引 % 遍历所有轮廓线段寻找最低的可放置位置 for s 1:size(skyline, 1) seg_y skyline(s, 1); seg_xl skyline(s, 2); seg_xr skyline(s, 3); seg_len seg_xr - seg_xl; % 如果当前线段宽度足够放置当前矩形 if seg_len current_width % 这是一个候选位置矩形左下角放在 (seg_xl, seg_y) candidate_y seg_y; candidate_x seg_xl; % 检查从 candidate_x 到 candidate_xcurrent_width 的区间内 % 所有涉及的轮廓线段的高度是否都 candidate_y即矩形底部能否平整放置 % 这是一个关键检查防止矩形“悬空” valid true; check_x_start candidate_x; check_x_end candidate_x current_width; for cs 1:size(skyline, 1) cs_xl skyline(cs, 2); cs_xr skyline(cs, 3); % 如果两线段在x方向上有重叠 if ~(check_x_end cs_xl || check_x_start cs_xr) % 在有重叠的区间轮廓线高度必须 candidate_y if skyline(cs, 1) candidate_y valid false; break; end end end % 如果检查通过且这个位置比之前找到的位置更低y更小 if valid candidate_y best_y best_y candidate_y; best_x candidate_x; best_seg_idx s; end end end % 如果找到了可放置位置 if best_seg_idx 0 % 记录放置信息 placed_count placed_count 1; original_idx sort_idx(i); % 映射回原始矩形索引 placed_rects(placed_count, :) [original_idx, best_x, best_y, current_width, current_height]; % 3.3 更新轮廓线关键且复杂的步骤 % 这是算法的心脏需要小心处理线段的分割 % ... (更新逻辑见下一小节) else % 如果没有找到位置理论上在宽度固定的板材中如果排序合理且矩形总宽不超过板材宽应总能找到 warning(矩形 %d (宽%.1f, 高%.1f) 无法放置, i, current_width, current_height); end end placed_rects placed_rects(1:placed_count, :); % 裁剪结果矩阵在寻找位置时valid检查至关重要。因为轮廓线是分段的我们找到的候选线段可能只是矩形放置区间的一部分。我们必须确保矩形底部所覆盖的整个X区间[best_x, best_xcurrent_width]内所有轮廓线段的高度都不高于best_y。否则矩形就会有一部分悬在空中这是非法的放置。3.3 轮廓线更新算法的“外科手术”找到放置位置后我们需要更新skyline。这是整个算法中最需要细心编码的部分。% --- 更新轮廓线 skyline --- % 1. 找到被当前矩形覆盖的轮廓线段 rect_left best_x; rect_right best_x current_width; rect_top best_y current_height; new_skyline []; % 用于构建新的轮廓线列表 for s 1:size(skyline, 1) seg_y skyline(s, 1); seg_xl skyline(s, 2); seg_xr skyline(s, 3); % 情况A该线段完全在当前矩形覆盖的X区间之外原样保留 if seg_xr rect_left || seg_xl rect_right new_skyline [new_skyline; [seg_y, seg_xl, seg_xr]]; % 情况B该线段完全在当前矩形覆盖的X区间之内将被矩形完全遮挡因此删除 % 注意这里只删除完全被覆盖的线段。部分覆盖的线段需要分割。 elseif seg_xl rect_left seg_xr rect_right % 完全覆盖删除不加入new_skyline continue; % 情况C该线段被当前矩形从左部分覆盖 elseif seg_xl rect_left seg_xr rect_left seg_xr rect_right % 保留左侧未被覆盖的部分 new_skyline [new_skyline; [seg_y, seg_xl, rect_left]]; % 情况D该线段被当前矩形从右部分覆盖 elseif seg_xl rect_left seg_xl rect_right seg_xr rect_right % 保留右侧未被覆盖的部分 new_skyline [new_skyline; [seg_y, rect_right, seg_xr]]; % 情况E该线段跨度大于矩形覆盖区间矩形在中间 elseif seg_xl rect_left seg_xr rect_right % 分割成左右两段 new_skyline [new_skyline; [seg_y, seg_xl, rect_left]]; new_skyline [new_skyline; [seg_y, rect_right, seg_xr]]; end end % 2. 添加矩形顶部产生的新轮廓线段 % 只有当矩形顶部高于其放置点的轮廓线时才需要添加。 % 我们添加从 rect_left 到 rect_right 在高度 rect_top 处的一条新线段。 % 但需要检查是否与现有线段合并同高度的相邻线段应合并。 new_seg_added false; for ns 1:size(new_skyline, 1) % 如果已经有一条线段在完全相同的高度并且x区间相邻或重叠则合并 if abs(new_skyline(ns, 1) - rect_top) 1e-10 % 浮点数容差比较 if (new_skyline(ns, 2) rect_right new_skyline(ns, 3) rect_left) % 区间有重叠或相邻合并 new_skyline(ns, 2) min(new_skyline(ns, 2), rect_left); new_skyline(ns, 3) max(new_skyline(ns, 3), rect_right); new_seg_added true; break; end end end if ~new_seg_added % 如果没有合并则添加新线段 new_skyline [new_skyline; [rect_top, rect_left, rect_right]]; end % 3. 最后需要对新的轮廓线按x_left进行排序以便下次遍历 [~, sort_order] sort(new_skyline(:, 2)); skyline new_skyline(sort_order, :);这段代码模拟了“手术”过程移除被覆盖的线段保留未被覆盖的部分并在顶部添加新的线段。合并相邻同高线段的步骤是为了保持轮廓线数据的简洁避免产生大量碎片化的小线段影响后续查询效率。3.4 结果计算与可视化排样结束后我们需要计算关键指标并可视化结果。% 计算板材使用高度轮廓线的最高点 used_height max(skyline(:, 1)); % 计算材料利用率所有矩形面积和 / (板材宽度*使用高度) total_rect_area sum(rect_list(:,1) .* rect_list(:,2)); utilization total_rect_area / (plate_width * used_height); fprintf(排样完成\n); fprintf(板材尺寸宽 %.1f 使用高度 %.2f\n, plate_width, used_height); fprintf(材料利用率%.2f%%\n, utilization * 100); % 可视化排样结果 figure(Position, [100, 100, 800, 500]); hold on; grid on; box on; axis equal; % 绘制板材边界 rectangle(Position, [0, 0, plate_width, used_height], EdgeColor, k, LineWidth, 2, LineStyle, --); % 绘制每个矩形 colors lines(num_rects); % 生成不同颜色 for i 1:placed_count idx placed_rects(i, 1); x placed_rects(i, 2); y placed_rects(i, 3); w placed_rects(i, 4); h placed_rects(i, 5); % 绘制矩形填充 rectangle(Position, [x, y, w, h], FaceColor, colors(idx, :), EdgeColor, k, LineWidth, 1.5); % 添加文本标签显示矩形编号和尺寸 text(x w/2, y h/2, sprintf(%d\n(%d×%d), idx, w, h), ... HorizontalAlignment, center, VerticalAlignment, middle, ... FontSize, 8, FontWeight, bold, Color, white); end % 绘制最终轮廓线可选用红线表示 for s 1:size(skyline, 1) plot([skyline(s, 2), skyline(s, 3)], [skyline(s, 1), skyline(s, 1)], r-, LineWidth, 1.5); end xlabel(宽度); ylabel(高度); title(sprintf(二维矩形排样结果 (利用率: %.1f%%), utilization*100)); xlim([-5, plate_width5]); ylim([-5, used_height5]); hold off;可视化是MATLAB的强项。通过rectangle和text函数我们可以清晰地看到每个矩形的位置、尺寸和编号。绘制红色的轮廓线有助于直观理解算法的工作过程。4. 性能优化与高级策略探讨基础版本虽然能工作但在处理矩形数量多、尺寸差异大的情况时可能效率不高或排样结果不理想。这里分享几个优化方向和进阶思路。4.1 数据结构优化用“优先队列”加速查找在基础循环中我们每次都要遍历整个轮廓线列表来寻找最低位置这是一个O(N)的操作N为当前轮廓线段数。当轮廓线变得复杂时这会成为性能瓶颈。一个经典的优化是使用优先队列最小堆。我们不再存储所有线段而是存储一系列“潜在放置点”。每个点代表轮廓线上某一段的左端点。优先队列按照点的y坐标高度排序。每次需要放置新矩形时我们从队列中取出y最小的点作为候选位置然后进行可行性检查宽度是否足够、是否会产生悬空。如果检查失败则将此点从队列中移除并尝试将其右侧相邻的点如果存在加入队列。如果成功放置则更新队列加入新产生的潜在放置点通常是新矩形顶部的两个角点。这种策略将查找最低点的平均复杂度降低到O(log N)。在MATLAB中我们可以用containers.Map模拟或自己实现一个简单的堆结构但对于入门和中等规模问题基础版本通常已足够。4.2 引入旋转与多规格板材实际生产中许多矩形零件是可以90度旋转的例如木板、金属板。支持旋转非常简单在尝试放置一个矩形时分别尝试其原始方向和旋转90度后的方向交换宽高选择那个能放在更低位置或更优位置的方向。这会使内层循环的计算量大约翻倍。更复杂的情况是多规格板材或无限长带材。对于多规格板材问题升级为二维的“二维装箱问题”需要同时决定用哪块板以及如何在板上排样。常见的启发式方法是先对所有板材和矩形排序然后采用“先适合First Fit”或“最佳适合Best Fit”策略将矩形依次放入当前最适合如剩余空间最小的板材中。对于无限长带材如卷材裁剪目标则是在宽度固定的前提下最小化使用的总长度其算法与单板材高度最小化问题本质相同。4.3 全局搜索与元启发式算法最低水平线算法是一种构造性启发式算法它给出一个可行解但未必是最优解。为了追求更优解我们需要引入全局搜索能力。遗传算法GA将矩形序列的排列顺序编码为染色体。初始种群由多种排序规则随机、按面积、按周长等生成的序列构成。适应度函数就是调用上述BLF算法计算该序列下的板材使用高度高度越小适应度越高。通过选择、交叉、变异操作迭代进化种群最终找到一个较好的排序方案。GA的强大之处在于它能跳出局部最优探索更广的解空间。模拟退火SA从一个初始序列如按高度降序开始通过随机交换两个矩形的位置产生一个新序列新解。如果新序列产生的排样高度更低则接受它如果更高则以一个随时间衰减的概率接受它这有助于跳出局部最优。SA参数初始温度、冷却速率的设置需要一些经验。禁忌搜索TS在搜索过程中记录近期移动如交换了哪两个矩形并禁止在短期内反向移动从而迫使搜索走向新的区域。在这些元启发式算法框架下我们的BLF算法就充当了一个“解码器”或“评估器”的角色给定一个矩形顺序它负责快速生成一个排样方案并计算其质量高度。这种“启发式构造 元启发式优化”的框架是解决复杂排样问题的标准范式。5. 实战踩坑调试、验证与效率陷阱纸上得来终觉浅绝知此事要躬行。在实现和调试排样算法的过程中我踩过不少坑这里分享几个关键点。注意浮点数精度问题。在比较轮廓线高度、判断线段重合或相邻时直接使用比较浮点数是非常危险的。由于计算误差理论上应该相等的两个数可能略有差异。务必使用容差比较例如abs(a - b) 1e-10。我在更新轮廓线合并线段时就曾因为精度问题导致本该合并的线段没有合并产生了错误的细小缝隙进而影响后续矩形的放置。调试与可视化是关键。当算法出现矩形重叠或放置位置明显不合理时最有效的调试方法是在核心循环中插入可视化代码。例如在放置每个矩形后立即绘制当前所有已放置矩形和轮廓线然后使用pause(0.5)让程序暂停一下动态观察排样过程。这能帮你迅速定位是哪个矩形放置出了问题以及问题发生时轮廓线的状态是怎样的。MATLAB的交互式调试和实时绘图能力在这里是无价之宝。验证排样方案的合法性。算法跑完后不能只看利用率和可视化结果“看起来”不错必须进行严格的合法性验证。编写一个验证函数检查所有矩形是否都在板材边界内 (x0, xwplate_width, y0)。任意两个矩形是否重叠。对于矩形i和j检查是否满足x_i w_i x_j或x_j w_j x_i或y_i h_i y_j或y_j h_j y_i只要一个条件成立即不重叠。如果所有条件都不成立则说明重叠。矩形是否“坐实”。即每个矩形的底边是否完全贴合在其下方轮廓线上允许容差。这可以通过检查矩形底部y坐标是否等于其覆盖X区间内轮廓线的最大高度来验证。警惕算法的时间复杂度。基础BLF算法的时间复杂度大致是O(N²)因为每个矩形都需要扫描当前轮廓线最坏情况下轮廓线段数随矩形数线性增长。对于几百个矩形这通常可以接受。但当矩形数量上千时运行时间会显著增加。此时就必须考虑4.1中提到的数据结构优化如优先队列将查找复杂度降为O(N log N)。在MATLAB中向量化操作比循环快得多但在这种强逻辑依赖、数据不断变化的问题中完全的向量化比较困难。一个折中方案是在更新轮廓线时尽量使用矩阵操作一次性处理多个线段减少在循环内动态增长数组new_skyline [new_skyline; ...]的次数因为这会频繁触发内存重分配影响性能。可以预先分配一个足够大的数组用索引进行填充。最后算法的结果具有随机性如果你引入了随机排序或元启发式算法或者对输入顺序极其敏感对于确定性算法如按高度排序的BLF。因此对于重要的生产问题不要只运行一次算法就采纳结果。应该尝试多种不同的初始排序规则或者运行多次元启发式算法从生成的多个可行解中挑选最好的一个。这通常能以可接受的时间成本换取利用率上几个百分点的提升这在批量生产中意味着巨大的成本节约。从理解问题、选择算法、实现代码、调试验证到思考优化完成一个二维矩形排样项目就像完成一次微型的系统工程。它锻炼的不仅仅是编程能力更是将现实问题抽象为数学模型并设计有效策略去求解的综合能力。希望这份详细的拆解能为你打开这扇门让你在遇到下一个“摆放”难题时能够从容地让代码为你寻找最优解。