基于欧氏距离的矩形Packing问题的确定性启发式求解算法

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.

A Deterministic Heuristic Algorithm Based on Euclidian Distance for Solving the Rectangles Packing Problem

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.