一种求解矩形块布局问题的拟物拟人算法

摘要：

在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法.本文以人类上万年以来形成的经验为基础,利用"占角"和"聚类"两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局算法.用本文提出的算法,对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试,测试结果表明:计算所得布局结果的优度高,计算时间短.对MCNC和GSRC测试算例,除apte实例外,其它所有实例均得到了最优解,而计算时间都在10秒以内.与CBL算法、遗传算法和号称当今最好的CompaSS算法相比,本文算法所得结果的优度更高,计算时间更短.进一步的测试表明,本文提出的拟物拟人布局算法为当今的一种高效算法.

关键词：Packing、VLSI布图规划、拟物拟人算法、占角动作、聚类

所属期刊栏目：32

分类号：TP3(计算技术、计算机技术)

资助基金：中国科学院资助项目10471051

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

页数：共5页

页码：182-186