一种同构、非同构布局模式构造算法研究简报.pdfVIP

一种同构、非同构布局模式构造算法研究简报* 1),2) 2) 2) 3) 滕弘飞 黎自强 史彦军 王奕首 1) (大连理工大学 机械工程学院 大连 116024) 2) (大连理工大学 计算机科学与工程系 大连 116024) 3) (大连理工大学精密与特种加工教育部重点实验室 大连 116024) 摘 要 装填布局(Packing)问题的求解困难在于存在给定规模问题的组合爆炸，如何缓解组合爆炸以提高计算效率 是人们关注的问题.大量计算实践表明，当采用具有确定性有哪些信誉好的足球投注网站规则的算法(如数学规划法)时，初始点(布局模式) 对布局优化的求解质量和计算效率有重要影响.为了探讨其本质和构造有效的初始布局，本文给出了一种基于完全 关联图的准确构造同构、非同构布局模式的算法，最后给出了其计算复杂度及适应范围，与李广强等(2003)的布局 模式构造方法相比较表明，本算法能构造准确布局模式，计算复杂度低，适用范围较广. 关键词 布局模式；同构；非同构；完全关联图 中图法分类号 TP391.75; O224; TH122 A brief report on constructing isomorphic, non-isomorphic layout pattern TENG Hong-fei1,2 LI Zi-qiang2 SHI Yan-jun2 WANG Yi-shou3 (1 School of Mechanical Engineering, 2 Department of Computer Science and Engineering , Dalian University of Technology) (3 Key Laboratory for Dalian University of Technology Precision Non-traditional Machining of Ministry of Education, P. R. China) Abstract: Difficulty in solving packing problem lies in combinatorial explosion of the given scale. How to relax combinatorial explosion has been much concerned in academic and engineering fields. Numerical experiments show that layout pattern (the initial pattern of layout) considerably affects optimization performance, when layout problems are solved using deterministic -search algorithms (e.g. Mathematical Programming). To construct an effective initial layout pattern and to explore the inherent relation between combinatorial explosion and layout pattern, this paper propos es an approach to exactly construct an isomorphic or non-isomorphic layout pattern based on a complete incide