资源描述：
《求解带平衡约束圆形Packing问题的快速局部搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第13卷第5期中国图象图形学报Vol.13,No.52008年5月JournalofImageandGraphicsMay,2008求解带平衡约束圆形Packing问题的快速局部搜索算法刘建黄文奇(华中科技大学计算机科学与技术学院,武汉430074)摘要带平衡性约束的圆集在圆容器内的布局优化问题,属于NP困难问题。针对此问题,提出了一种快速的局部搜索算法。该算法首先构造出等价的物理模型,定义系统的能量函数,再利用最速下降法对能量函数进行优化,从而间接得到问题的近似解。在局部搜索算法中引入加速策略,提高了计算效率。最后通过两个算例的数值计算
2、,验证了该方法的可行性和有效性。关键词约束布局问题NP困难格局局部搜索算法加速策略中图法分类号:TP391文献标识码:A文章编号:100628961(2008)0520991207AFastLocalSearchAlgorithmforSolvingCirclesPackingProblemwithConstraintsofEquilibriumLIUJian,HUANGWen2qi(CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology
3、,Wuhan430074)AbstractTheoptimallayoutproblemofcirclegroupinacircularcontainerwithperformanceconstraintsofequilibriumbelongtoNP2hardproblem.Afastlocalserachalgorithm(LS)ispresentedforsolvingthisproblem.Firstly,themethodconstructsanequivalentphysicalmodelanddefinestheenergy
4、functionofthesystem.Thentheenergyfunctionisoptimizedbythesteepestdescentmethodandtheapproximationsolutionisobtainedindirectly.Inordertoimprovethecomputationalefficiency,theacceleratingstrategyisaddedtotheLSalgorithm.Twoexamplesarecomputednumerically,andtheresultsoftheexpe
5、rimentshowthefeasibilityandefficiencyoftheapproach.Keywordsconstrainedlayoutproblem,NP2hard,configuration,localsearchalgorithm,acceleratingstrategy的带平衡约束的2维不等圆布局问题,就是其中1引言之一。布局问题在理论上等价于二次指派问题,属布局问题就是寻找给定待置物的一种合理放置于典型的NP困难问题,很难找到具有多项式复方案,使其所占空间最小。许多工业领域经常会碰[1]杂性的精确求解算法。人们普
6、遍采用启发式到此类问题,比如电路板设计,玻璃、金属的切割,集的方法求得问题的近似解,但主要是针对布置物装箱装箱等等。通常情况下,求解布局问题仅要求为2维矩形或者3维立方体的情形,讨论圆形、布局物体在空间位置上不相互冲突即可,还有一类特别是不等圆布局问题的文献并不多见。文献更复杂的问题,布局时要考虑诸如惯性、平衡性、稳[2]采用离散化的方法处理相同形状、不同大小定性等性能约束,称之为约束布局问题。本文研究物体的布局问题,在理论上证明了该类问题是基金项目:国家自然科学基金项目(10471051);国家重点基础研究发展计划(973)项目(200
7、4CB318000)收稿日期:2006201229;改回日期:2007201229第一作者简介:刘建(1978～),男。华中科技大学计算机学院软件与理论专业博士研究生。从事算法设计与分析的研究。E2mail:packlj@163.com©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net992中国图象图形学报第13卷3NP困难的。文献[3]研究不等圆在矩形内的布径R表示待置圆的集中程度。那么X成为合法格局,
8、基于若干布置规则给出了一种启发式算法。局必须满足的约束条件表达如下:文献[4]研究单位圆在圆形容器内的布局问题。(1)两圆之间的不干涉条件文献[5]、[6]提出用拟物、拟人的方法求解无性(x-
