论文部分内容阅读
三维布局问题属于组合最优化问题和NP完全问题,在一定时间内求其精确全局最优解是相当困难的。有效的优化技术,对布局实体的表示和处理,是解决三维布局问题的两个关键。本文论述了在现有研究成果的基础上,采用适合于解决一般性三维布局问题的模拟退火算法,在AutoCAD图形系统上开发用于解决任意形状三维物体布局问题的自动布局系统。 首先对布局问题的种类、求解算法,以及三维布局问题的研究现状进行了综述和分析,指出模拟退火算法与启发式算法相结合,是改进布局算法的一个有效的途径。 设计了三维自动布局系统的体系结构。系统的体系结构包括六部分:AutoCAD平台上的用户界面、布局系统管理模块、布局物体输入创建模块、自动布局模块、布局系统输出模块、AutoCAD图形数据库。 对SA算法和启发式算法在布局问题中的应用进行了研究,为提高收敛速度同时保证一定精确度,对SA算法进行了改进,在算法的搜索策略和变动策略中应用了启发式方法,缩小布局状态空间的搜索。并通过布局实例对算法的退火策略、变动策略进行了比较分析。 对采用ObjectARX实现三维自动布局系统的关键技术进行详细论述。首先对三维布局问题的一般性特征和开发工具ObjectARX进行分析,将一般特征用面向对象技术表述出来,建立三维布局基类,具体的三维布局问题则从该基类派生。论述了利用AutoCAD图形系统进行布局实体造型、图形数据管理,布局实体的干涉检验算法的设计,布局优化算法与布局实体的操作处理的实现,布局占用空间的计算,以及系统输入模块、输出模块的设计等。 最后,总结了本文的工作并展望了进一步的研究方向。