长方体布局问题的一种启发式算法

摘要：

长方体布局问题属于NP完全问题,在串行机上解决这类问题只能依赖启发式算法.本文提出了一种对布局空间进行动态分解和对剩余空间进行合并和再利用的启发式算法.分解过程采用三叉树数据结构表示,深度优先原则搜索,根据一定的定序规则和定位规则快速求得问题的满意解.同时针对影响布局结果的"难布置的布局物体",设计剩余空间的合并规则,达到该类物体的布入,并通过算例说明了本算法的有效性,对长方体布局具有一定的指导意义,也为人机结合的优化布局提供了良好基础.

关键词：布局、启发式算法、空间分解

所属期刊栏目：25

分类号：TP183(自动化基础理论)

资助基金：国家自然科学基金500750002

在线出版日期：2004-01-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：8-13