共查询到10条相似文献,搜索用时 15 毫秒
1.
王石 《计算机技术与发展》2011,21(3)
针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的. 相似文献
2.
对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的. 相似文献
3.
4.
5.
二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%. 相似文献
6.
在货物装载、木材下料、超大规模集成电路(VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验,提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略,即矩形块选择策略和矩形块放置策略。用本文提出的算法,对21个测试算例进行了实算测试,测试结果表明:算法所得装填结果的优度高,计算时间短。对这21个测试算例。用本文算法计算,得到了其中16个算例的最优解,而计算时间都在2秒以内。进一步的测试表明,本文提出的算法对求解矩形块装填问题十分有效。 相似文献
7.
8.
基于改进粒子群优化算法的矩形Packing问题 总被引:3,自引:1,他引:2
针对具有NP难度的矩形Packing问题,提出一种带变异算子的双种群粒子群算法,该算法将粒子群分为2个不同的子群,使种群在全局和局部都有较好的搜索能力。通过子群重组实现种群间的信息交换。同时在算法中引入变异算子,对产生的局部最优解的邻域进行搜索。实验结果表明,该算法是一种求解矩形Packing问题的高效实用的算法。 相似文献
9.