摘要
分析了矩形物体布局串行算法的计算复杂性，设计出基于ＳＩＭＤ－ＣＲＥＷ共享存储模型的矩形物体布局的并行算法。
In this paper, the analysis of the computational complexity of the sequential algorithm for the rectangular packing proposed by paper is carried out. A parallel algorithm for the rectangular packing based on SIMD CREW shared memory model is designed. The efficiency of this algorithm has been tested by the comparison with the sequential algorithm through a testing problem, which has shown the advantage of the proposed method——higher computing speed.
出处
《天津大学学报》
EI
CAS
CSCD
1997年第2期199-204,共6页
Journal of Tianjin University(Science and Technology)
基金
国家教委高等学校博士学科点专项科研基金
关键词
矩形物体布局
并行算法
NP完全问题
布局问题
rectangular packing, parallel algorithm, NP complete problem, heuristic method, combinatorial optimization
