【作者】 陈端兵；

【导师】 黄文奇；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2007， 博士

【摘要】 NP难度问题是一大类问题,NP完全问题则是其中最简单最基本的一类问题。NP完全问题在科学哲学和现实生活中的重要价值在于它同时具有看来相反的两个性质:通俗性和难解性。导致NP完全问题难解的主要根源在于解空间随问题规模的扩大呈指数增长,甚至是一个连续欧氏空间的无穷集合。矩形packing问题属于NP难度问题。此问题来源于物件布局、切裁下料以及超大规模集成电路设计等实际问题,常见的提法有:矩形背包问题,矩形装填问题和矩形块布局问题。我们将人类在近万年来所从事的一些特殊活动中采取的方法和形成的实践经验加以形式化,把它说精确、说完整,并予以进一步的发展,在此基础上设计出求解矩形packing问题的纯粹拟人算法。在“占角动作”和“穴度”两个重要概念的基础上得到了挑选占角动作的具体策略,并提出了求解矩形背包问题的三个具体的纯粹拟人算法:最大穴度算法A₀,前瞻穴度算法A₁和强化穴度算法A₂。算法A₀采用纯粹贪心的办法放置矩形块,即每次挑选穴度最大的占角动作并将动作关联的矩形块按相应的位置和方向放在容器中。算法A₁在放每一块矩形块时,都运用回溯的策略,以确定一个“全局最好”的动作。算法A₂仅在放第一块时运用回溯的策略,以后就采用最大穴度算法放置剩下的矩形块。用Hopper和Turton提出的21个测试实例对三个算法的性能进行了实算测试,并与当今国际文献已报道的最先进的两个算法——初步拟人算法Heuristic1和混合启发式算法（HH）进行了对比。算法A₁求出了其中15个实例的最优解,算法A₂求出了其中7个实例的最优解,这一结果优于算法Heuristic1和HH所得结果。以“角点数”和“贴边数”两个概念为基础,对算法A₀,A₁和A₂进行改进而得到了三个相应的改进算法A’₀,A’₁和A’₂。对Hopper和Turton提出的21个测试实例,算法A’₁求出了其中19个实例的最优解,算法A’₂求出了其中8个实例的最优解,这一结果比A₁和A₂所得结果要好。结合二分的思想,将算法A’₁加以改造而得到了矩形装填问题的拟人求解算法A₃。用三组测试算例对算法性能进行了实算测试。对Hopper和Turton提出的21个测试实例,算法A₃所得容器高度与最优高度的偏差的平均值为0.04%;对Hopper提出的35个装填实例,偏差的平均值为1.8%;对Berkey和Martello等人提出的10组共500个装填实例,偏差的平均值为2.28%。这些结果比目前国际上已报道的最先进的启发式算法所得结果要好。以算法A₀和A₁为基础,结合“聚类”的思想,提出了矩形块布局问题的拟人求解算法A₄。对MCNC和GSRC两组共21个实例,算法求出了其中20个实例的最优解,这一结果好于CompaSS算法（Compacting Soft and Slicing Packings）、基于角模块序列的模拟退火算法（CBL）及遗传算法所得结果。在算法A0和A1的基础上,提出了求解价值优化的矩形packing问题的纯粹拟人算法A₅。算法中使用了两个主要的拟人策略——矩形块选择策略和占角动作选择策略。用国际上公认的21个小规模实例和630个大规模实例对算法性能进行了测试,并和基于人口进化理论的启发式算法（PH）进行了对比,算法A₅所得结果比PH算法所得结果好得多。大量的实算测试和对比分析表明:我们提出的诸算法是求解矩形packing问题的有效算法。人们今后还可沿着“占角”和“穴度”的哲学思想,对直角多边形和长方体packing问题展开研究。更多还原

【Abstract】 Among all NP-hard problems, NP-complete problems are the simplest and the mostfundamental ones. NP-complete problems are of critical value in philosophy of scienceand real life because of their two opposite characteristics: popularity and difficulty. Themain reason of the difficulty is that the solution space is an exponential function of theproblem size, even an infinite set in Euclidian space.The rectangle packing problem has proven to be NP-hard. It is from some practicalproblems such as layout, cutting, very large scale integration （VLSI） designing etc and isgenerally described as rectangle knapsack problem, rectangle strip packing problem andrectangle placement problem, respectively.We formalize the method and experience from some special works of human beingin ten-thousand-year, state it exactly and completely, and then upgrade it to a higher level.Based on this idea, pure quasi-human algorithms are proposed to solve the rectangle pack-ing problem.Based on the corner-occupying action （COA） and caving degree, we give the COAselecting criterion and propose three pure quasi-human algorithms, i.e., maximum cavingdegree algorithm A0, look ahead caving degree algorithm A1 and strengthening caving de-gree algorithm A2, to solve the rectangle knapsack problem. In algorithm A0, pure greedystrategy is considered to pack a rectangle, that is, pick the COA with maximum caving de-gree and pack the corresponding rectangle into the container in the corresponding positionand orientation at each packing step. In algorithm A₁, backtracking strategy is consid-ered in order to determine a global best COA for packing a rectangle. In algorithm A2,backtracking strategy is used to pack the first rectangle, and then maximum caving degreealgorithm is used to pack the others. The performance of three algorithms is evaluated by21 instances provided by Hopper and Turton and compared with that of two most advancedalgorithms——simple quasi-human algorithm Heuristic1 and hybrid heuristic algorithm （HH）. Optimal solutions of 15 instances are achieved by A₁ and 7 by A₂. The quality ofthe results is better than that of results obtained by Heuristic1 and HH.Based on vertex degree and edge degree, we improve three algorithms A₀, A₁ and A₂and obtain algorithms A’₀, A’₁ and A’₂, respectively. For 21 instances provided by Hopperand Turton, optimal solutions of 19 instances are achieved by A’₁ and 8 by A’₂. The qualityof the results is superior to that of results obtained by A₁ and A₂.In order to solve the rectangle strip packing problem , we modify the algorithm A’₁ onthe basis of dichotomy strategy and obtain a quasi-human algorithm A₃. The performanceof the algorithm is evaluated through three group benchmarks. For 21 instances providedby Hopper and Turton, 35 strip packing instances by Hopper and 10 group benchmarks（500 instances） by Berkey and Martello et al, the average deviation between the best con-tainer height and the optimum is 0.04%, 1.8% and 2.28%, respectively. The quality ofthese results is better than that of the results obtained by the most advanced heuristic al-gorithms which are reported up to now.Based on A0 and A1 combining clustering strategy, a quasi-human algorithm A₄ ispresented to solve the rectangle placement problem. For MCNC and GSRC benchmarks（21 instances）, optimal solutions of 20 instances are achieved by A₄. Experimental resultsdemonstrate that A4 is more efficient than CompaSS algorithm （Compacting Soft andSlicing Packings）, simulated annealing algorithm based on corner block list （CBL） andgenetic algorithm.On the basis of A₀ and A₁, a pure quasi-human algorithm A₅ is proposed to solve therectangle packing problem with value optimization. Two primary quasi-human strategies,i.e., rectangle selecting strategy and COA selecting criterion, are considered in the algo-rithm. The performance of the algorithm is evaluated by 21 small and 630 large publicinstances and compared with that of population heuristic algorithm （PH）. The quality ofthe results achieved by A₅ is superior to that of the results by PH.Experimental results and comparisons demonstrate that the presented algorithms inthis dissertation are efficient for solving the rectangle packing problem. In the future,rectilinear block packing and cuboid packing problems could be studied further on the basis of corner-occupying action and caving degree.更多还原