CAJ | 학술논문

加权圆集布局问题是基于性能驱动的一类布局问题,由于其NP-hard属性,难以在多项式时间内求解,提出一种快速启发式搜索算法.权矩阵的行向量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|.| 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 se-lected 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 prob-lem in the paper can be obtained. The experimental results show that the performances of the proposed algorithm is superior to the existed algorithms.