基于蒙特卡罗方法的矩形布局问题研究  

Research on rectangle packing problem based on Monte Carlo method

作　　者：郑荣杰[1] 张鹏程[1] 崔海良[1] 李国顺[1] 罗海兵[1] 刘昕彤[1] 

机构地区：[1]河北工程技术高等专科学校,河北沧州061001

出　　处：《图学学报》2012年第4期33-36,共4页Journal of Graphics

基　　金：河北省教育厅自然科学指导资助项目(Z2011265;Z2010230)

摘　　要：根据蒙特卡罗方法产生的随机步长,控制矩形在布局空间中移动。矩形移动时,自动满足边界约束条件,简化了矩形可行域边界的计算过程。结合定位函数,得到的可行域可用于完成矩形的布局。测试结果表明,使用该方法求解矩形布局问题,布局空间90%以上被矩形占据。The rectangle moves freely according to the random step generated by Monte Carlo method in the region to be packed in.When the rectangle moves,it is confined in the region to be packed in automatically,which makes the calculation of feasible region become simple.After the feasible region is obtained,the rectangle is packed in successfully by the placement function.Experiments show that above ninety percent of the region to be packed in is filled with rectangles.

关 键 词：布局 矩形的可行域 蒙特卡罗方法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]