A Deterministic Heuristic Algorithm Based on Euclidian Distance for Solving the Rectangles Packing Problem
A Deterministic Heuristic Algorithm Based on Euclidian Distance for Solving the Rectangles Packing Problem
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Huang Wen
中科院分区：
文献类型：
--
作者：
Huang Wen
解决NP难问题是当今计算机科学技术的瓶颈任务。近年来的研究表明，对于NP难问题，可能不存在一种既完备又严格且速度不太慢的算法。因此，其求解方法通常是启发式的。矩形Packing问题是NP难的。给定一组宽度和高度固定的矩形和一个较大的矩形，矩形Packing问题是通过将这些矩形包装在一个较大的矩形内而不完全重叠来找到一个好的布局。本文在拟人策略的基础上，提出了基于欧氏距离的最大空洞度优先的角占据布局策略。提出了一种有效的启发式算法，应用该算法可快速求解矩形件排样问题。在MCNC和GSRC基准电路上的实验结果表明，该算法在解决该问题上是相当有效的。
Solving NP hard problem is the bottleneck task for computer science and technology nowadays. In recent years, investigations show that for NP hard problems, there may not exist an algorithm that is both complete and rigorous and not too slow. So its solution methods are usually heuristic. The rectangles Packing problem is NP hard. Given a set of rectangles with fixed width and height and a larger rectangle, the rectangles Packing problem is to find a good layout by Packing these rectangles without overlapping entirely inside a larger rectangle. In this paper, based on the quasi-human strategy, the authors propose the so-called corner-occupying and largest hole degree first placement policy based on Euclidian distance. An effective heuristic algorithm is presented, and the solution to the rectangles Packing problem can be obtained quickly by applying this algorithm. Experimental results on MCNC and GSRC benchmark circuits demonstrate that the algorithm is quite effective in solving the problem.