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

An Approach to Constructing Isomorphic or Non-Isomorphic Layout Pattern

作　　者：滕弘飞[1] 黎自强[2] 史彦军[1] 王奕首[1] 

机构地区：[1]大连理工大学机械工程学院,大连116024 [2]大连理工大学计算机科学与工程系,大连116024

出　　处：《计算机学报》2006年第6期985-991,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(60073036;50275019;50335040;50575031);高等学校博士点专项科研基金(20010141005)资助

摘　　要：给出了一种基于完全关联图的准确构造同构、非同构布局模式的算法,并给出了其计算复杂度及适应范围.与李广强等(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））.

关 键 词：布局模式 同构 非同构 完全关联图 

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