求解二维矩形Packing问题的完备算法  

Complete Algorithm for 2D Rectangular Packing Problem

作　　者：何琨[1] 姚鹏程[1] 李立文[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2014年第8期55-59,89,共6页Computer Science

基　　金：国家自然科学基金(61173180)资助

摘　　要：对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法。The classical complete algorithm for the NP hard 2D rectangular packing problem is not only related to the number of items but also related to the width and height of the rectangular container. By observing the characteristics of feasible layouts for this packing problem, we corresponded each feasible layout to a pair of acyclic directed graphs. Then based on the prtifer code,we proposed a new complete algorithm whose computational complexity is only based on the number of items.

关 键 词：PACKING问题 完备算法 计算复杂度 Prüfer编码 有向无环图 

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