郑荣杰， 张鹏程， 崔海良， 李国顺， 罗海兵， 刘昕彤

（河北工程技术高等专科学校，河北 沧州 061001）

矩形布局[1]是在矩形的边与布局空间边界平行的情况下，将其不相嵌地放入布局空间中，同时达到空间排布的最优化。这一问题属于布局问题的一个子问题。它在机械设计与制造、交通运输、大规模集成电路设计等领域有着广泛的应用，是当前CAD/CAM研究的热点问题之一[2]。

布局问题作为具有NP-hard的最优组合问题，在有限的时间内一般无法获得全局最优解[3]。对其求解只能依赖于各种启发算法，其中构造式启发方法应用最广[4]。使用构造式方法求解矩形布局，其过程分为定序和定位两步:定序规则确定矩形布入的次序，定位规则确定矩形布入位置。矩形可行域是指待布矩形在布局空间中所有可行位置的集合。近来，研究发现结合矩形可行域制定定序规则和定位规则，可以使矩形布局过程更灵活，算法的自适应性更强[4]。

随着矩形布入，布局空间的边界发生变化，边界的形状变得复杂。确定此类空间中矩形可行域成为一个难题。考虑到蒙特卡罗方法研究非确定性问题的优势[5]，我们将其引入到于矩形可行域研究，最终得到了有意义的结果。

1 蒙特卡罗方法

蒙特卡罗方法[6]，是一种根据统计抽样理论近似求解数学物理问题的计算机模拟方法，已广泛应用于金融工程学，宏观经济学，生物医学，计算物理学等领域。对于确定性问题，其基本思想是：建立一个与所求解有关的概率模型，基于这个模型进行随机抽样；……