矩形布局问题吸引子法研究

王金敏， 齐 杨

（天津职业技术师范大学天津市高速切削与精密加工重点实验室，天津 300222）

矩形布局问题吸引子法研究

王金敏， 齐 杨

（天津职业技术师范大学天津市高速切削与精密加工重点实验室，天津 300222）

吸引子法是布局定位函数中的一种，在解决布局问题中取得了较好的效果。论文的研究，获得了吸引子法的一些基本性质：诸如定位函数的三维图像为一个平面、定位函数值相等的点共线、吸引子法使矩形块堆积在一个角上等。此外，通过研究布入点的几何意义，提出了一种手动快速布局方法。最后通过研究吸引子放置位置对布局的影响，还得出了隐性吸引子这一重要的性质。

布局问题；启发式算法；定位函数；吸引子法

矩形布局问题[1]广泛地存在于工业生产实践之中。长期以来，人们为解决该问题提出各种理论和方法[2]，并取得了一定的效果。这些方法中最主要的有两种[3]：优化算法和启发式算法。其中优化算法只能找到局部最优解，且所得解的质量在很大程度上依赖于初始解的选择[4]。于是人们将研究的重心转向了启发式算法[5],并提出了一系列求解算法，其中，构造启发算法是最常见的一种算法。构造启发算法主要由定序规则和定位规则确定[6]。常见的定序规则有按面积递减、按最长边递减和按可行域面积等顺序确定布局块的布局次序。常见的定位规则有占角顺放策略、金角策略、下台阶法和定位函数法等。吸引子法[7]是定位函数法中的一种。……