摘要
使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.
Sòlving 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 u- sually 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 algo- rithm 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 demon- strate that the algorithm is quite effective in solving the problem.
出处
《计算机学报》
EI
CSCD
北大核心
2006年第5期734-739,共6页
Chinese Journal of Computers
基金
国家自然科学基金(10471051)
国家"九七三"重点基础研究发展规划项目基金(2004CB318000)资助.
关键词
PACKING问题
拟人法
占角动作
穴度
价值度
欧氏距离
Packing problem
quasi-human
corner-occupying placement
hole degree
value
Euclidian distance
