装填布局的同构和非同构模式

装填布局问题在工程实践上具有广泛的应用，在理论上属于NPC问题．布局模式是其中的一个重要问题．该文以卫星舱布局方案设计为背景，研究装填布局模式问题，定义了同构和非同构布局模式、待布物的布局等价关系等概念，给出了关系矩阵和模式矩阵以及它们的变换，描述了布局模式控制区和非同构度，提出了同构和非同构布局模式的识别及构造方法．文后讨论了布局模式的若干应用．该工作希望能为缓解装填布局优化问题求解时存在的组合爆炸以及构造高效的求解算法提供启发和借鉴．

Isomorphic and Non-Isomorphic Layout Patterns of Packing Problems

Packing problems are to study how to put objects into a limited area (e.g. a container) reasonably under given constraints and they belong to NPC problems theoretically. Because they have extensive engineering applications practically (such as layout design of spacecraft modules, vehicle, robot and submarine.), packing problems are being concerned more and more in recent years. The layout pattern refers to the relative position relationship between objects in layout scheme and it is one of the important aspects that deserve to be studied in a deep-going way. Taking the layout design of satellite cabins as the background, we study layout patterns of the packing problems. The relevant concepts are defined, such as isomorphic and non-isomorphic layout patterns, layout equivalence relation between objects. Relation matrix, pattern matrix and their transformations are introduced to represent layout patterns. The control zone of layout pattern and non-isomorphic degree are described. We also present methods of recognition and construction for isomorphic and non-isomorphic patterns. At the end of this paper, several applications based on layout patterns are discussed. All of this work expects to benefit relaxing combinatorial explosion that occurs in the process of solving packing and layout optimization problems, as well as constructing new efficient algorithm for them.