一种同构、非同构布局模式构造算法

An Approach to Constructing Isomorphic or Non-Isomorphic Layout Pattern

给出了一种基于完全关联图的准确构造同构、非同构布局模式的算法,并给出了其计算复杂度及适应范围.与李广强等(2003)的布局模式构造方法相比较表明,本算法能构造准确布局模式,适用范围较广,计算复杂度低,前者为O(n3),本文为O(n),O(n2)或O(n3).

Difficulty in solving Packing problem lies in combinatorial explosion ot the given scale. How to relax combinatorial explosion has been much concerned in academic and engineering fields. Numerical experiments show that initial layout points （layout pattern） considerably affect solution quality and computational efficiency, when layout problems are solved using deterministic search algorithms （e. g. Mathematical Programming）. To explore the inherent relation between combinatorial explosion and layout pattern, and construct an effective initial layout pattern, this paper proposes an approach to exactly construct an isomorphic or non-isomorphic layout pattern based on a complete incidence graph. Furthermore, the comparison with the layout pattern algorithm proposed by Li G. Q. et al （2003） shows that, the proposed approach can construct exact layout pattern, along with broader applied range and lower computation complexity （the former is O（n^3）, the latter is O（n）, O（n^2） or O（n^3））.