Abstract: The weighted circle layout problem is a class of layout optimization problem with behaviour constraints. Due to its NP-hard attribute, it is very difficult to solve in polynomial time. This paper puts forward a heuristic searching algorithm. The heuristic idea of the proposed algorithm is that ||.||1 of the row vector of the weighted matrix is used as heuristic information of first round of the roulette selection, the elements of the current row（the row number is equal to the the subscript of the circle selected this time） of weighted matrix are taken as heuristic information for next roulette selection; the location rule with the lower computational complexity is given by using the theory of graphics. Through the heuristic searching, the optimal solution of problem in the paper can be obtained. The experimental results show that the performances of the proposed algorithm is superior to the existed algorithms.

Key words: layout problem of weighted circles, heuristic, behaviour constraints, location rule

摘要： 加权圆集布局问题是基于性能驱动的一类布局问题，由于其NP-hard属性，难以在多项式时间内求解，提出一种快速启发式搜索算法。权矩阵的行向量1范数作为首次赌轮选择圆的启发信息，依次以权矩阵的当前行（其行号等于当前选择圆的序号）元素作为下次赌轮选择的启发信息，利用图形学理论给出低计算复杂度的定位规则，进而基于该定序定位规则提出一种启发式搜索算法，以求得该问题的最优解。数值实验表明，该算法的性能优于已有算法。

关键词: 加权圆集布局问题, 启发式, 性能驱动, 定位规则