求解加权圆集布局问题的快速启发式搜索算法  

Fast heuristic searching algorithm for weighted circles layout problem

作　　者：周爱民[1,2] 黎自强[1] 谢艳芳[1] 

机构地区：[1]湘潭大学,信息工程学院,湖南湘潭411105 [2]湖南中医药高等专科学校教务处,湖南株洲412012

出　　处：《计算机工程与应用》2013年第8期72-75,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61272294);湖南省自然科学基金(No.11J059);湖南省教育厅重点项目(No.11A120);湖南省重点学科建设基金项目(湘教发[2012]1号)

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

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

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]