求解圆形packing问题的一个快速拟物算法

求解背包问题的一种新的近似算法引言：现实中有很多问题至今还没有多项式式时间可解的算法，如本文的背包问题。

实际应用中可以通过近似算法来获得一个解。

近似算法在理想情况下，可以保证近似解与最优解只有一个常数之差。

背包问题的近似算法现实中有很多问题至今还没有多项式式时间可解的算法，如本文的背包问题。

实际应用中可以通过近似算法来获得一个解。

近似算法在理想情况下，可以保证近似解与最优解只有一个常数之差。

近似算法设计的两个基本要求：算法能在N的多项式时间内完成算法的近似解满足一定的精度4.1 近似算法定义接下来我们来介绍几个定义，来衡量近似算法的性能。

定义1（近似比）设问题Π是最大化问题，I是问题Π的一个实例：A是问题Π的一个近似算法，A(I)是用算法对问题Π的实例I求解得到的近似值OPTA是问题Π的最优算法，OPTA(I)是算法OPTA对问题Π的实例I求解得到的准确值则可以定义近似算法A的近似比率ρ(I):ρ(I)=OPTA(I)A(I)最小化问题的近似比为：ρ(I)=A(I)OPTA(I)算法A的近似比率ρ(I)总是大于等于1，近似比率越小，算法越好。

定义2(相对误差界) 若对于输入规模为n的问题，存在一个函数ϵ(n)，使得：ρ(I)=|OPTA(I)−A(I)OPTA(I)|≤ϵ(n)近似算法的近似比率ρ(I)与相对误差的界ϵ(n)存在如下的关系：ϵ(n)=ρ(I)−1定义3（优化问题近似方案）把近似算法A的近似比满足如下条件：且{Aϵ|ϵ>0且ρ(I,ϵ)≤1+ϵ}称为优化问题的近似方案。

定义4（多项式近似方案，PAS）如果近似方案中的每一个算法Aϵ，以输入实例规模的多项式时间运行，则称该方案为多项式近似方案（Polynomial Approximiation Scheme ,PAS )定义5（完全多项式近似方案，FPAS）如果近似方案中的每一个算法Aϵ的计算时间是1ϵ和n的多项式，则称这个近似方案是完全多项式近似方案（Fully Polynomial Approximiation Scheme ,FPAS )完全多项式近似方案(FPAS)通俗理解，在理想情况下，若ϵ减少某个常数倍，近似方案中算法的计算时间的增长也不会超过某个常数倍。

Packing问题问题描述：如何把任意数量任意尺⼨矩形集⽆重复的放到⼀个⾯积最⼩的封闭矩形中。

算法思想：（为了便于描述，把要找的封闭矩形记为a，封闭矩形的集合记为as，把矩形集合记为rs，n为rs中矩形的个数，把可以插⼊矩形的位置记为corners）1.把所有矩形集中的矩形按⾼度从⼤到⼩排序，此时rs[0]⾼度最⼤2.把a初始化为：height = rs[0].height，width = rs[0].width + rs[1].width + ...... + rs[n - 1].width，corners初始化为：坐标顶点3.把rs[0]放⼊a中，并把由于rs[0]的插⼊产⽣的corner放⼊corners集合中，删除已经使⽤的corner，如下图所⽰：4.从rs[1]到rs[n - 1]，每次插⼊时选择可以插⼊的X值最⼩的corner，插⼊成功之后，删除已经使⽤的corner，并且插⼊新产⽣的corner，由于a的初始化条件，可以保证rs中的所有矩形都可以插⼊a中5.所有矩形插⼊完成后，对a进⾏“瘦⾝”，让a正好包含所有的矩形，并记录此时a的宽度为width，a的⾯积为area（此时a是所有符合条件的封闭矩形中的‘最狭长’的，令as[0] = a）6.依次减少a.width，增加a.height，重复3-5，如果a的⾯积有所减少，则把a插⼊到as中，直到a.width = rs中最宽矩形的宽度7.as集合的最后⼀个元素就是可以包含rs中所有矩形的⾯积最⼩的封闭矩形，算法结束算法实现：在算法的实现中需要注意的地⽅：1.计算由于矩形的插⼊产⽣的新的corner（需要考虑很多特殊情况）2.判断矩形是否可以插⼊⼀个corner3.数据结构的设计以下程序是算法最核⼼的⽅法，插⼊矩形，并记录新产⽣的cornerprivate boolean putIn(PngRect png){if(pngs == null){pngs = new ArrayList<PngRect>();pngs.add(png);png.setStartP(new Point(0,0));if(png.getHeight() < mHeight){Rect owner = new Rect(0,png.getStopP().getY(),mWidth,mHeight);Corner corner = new Corner(new Point(0,png.getHeight()),owner);corners.add(corner);}if(png.getWidth() < mWidth){Rect owner = new Rect(png.getStopP().getX(),0,mWidth,mHeight);Corner corner = new Corner(new Point(png.getWidth(),0),owner);corners.add(corner);}return true;}else{Corner corner;int x;int y;Rect owner;for(int i = 0; i < corners.size(); ++i){corner = corners.get(i);x = corner.getPoint().getX();y = corner.getPoint().getY();owner = corner.getRect();Point startP = corner.getPoint();int endX = owner.right;int endY = owner.bottom;/** 可以放进该corner，此处存在覆盖问题，需要判断四条边是否有点在已经被使⽤，如果是，则返回，试下⼀个corner* v0-----v1* | |* | a |* | |* v2-----v3* 同时为了防⽌完全重叠，还需要判断额外⼀个点,例如图中的a点*/if(x + png.getWidth() <= mWidth && y + png.getHeight() <= mHeight){Point v0 = startP;Point v1 = new Point(startP.getX() + png.getWidth(),startP.getY());Point v2 = new Point(startP.getX(),startP.getY() + png.getHeight());Point v3 = new Point(startP.getX() + png.getWidth(),startP.getY() + png.getHeight());Point a = new Point(startP.getX() + png.getWidth()/2,startP.getY() + png.getHeight()/2);if(contains(v0,v1,true) || contains(v1,v3,false) || contains(v2,v3,true) || contains(v0,v2,false) || contains(a)){//有可能正好落在边上continue;}// if(contains(a) ||contains(v0) || contains(v1) || contains(v2) || contains(v3) ){//有可能正好落在边上// continue;// }if(x + png.getWidth() < endX){corners.add(i + 1,new Corner(new Point(x + png.getWidth(),y),new Rect(x + png.getWidth(),y,mWidth,mHeight)));//此处owner可能为空 }if(y + png.getHeight() < endY){corners.add(i + 1, new Corner(new Point(x,y + png.getHeight()),new Rect(x,y + png.getHeight(),mWidth,mHeight)));}corners.remove(i);sortCorners();png.setStartP(corner.getPoint());pngs.add(png);return true;}}}return false;}实体类：Cornerpublic class Corner {//Corner的起始点private Point point;//可以填充图⽚的区域private Rectangle rect;public Corner(Point point,Rectangle rect){this.point = point;this.rect = rect;}public Point getPoint(){return point;}public Rectangle getRect(){return rect;}}PngRectpublic class PngRect {private int mHeight;private int mWidth;private Point mStartP;//最左上⾓的点private Point mStopP;//最右下⾓的点private BufferedImage mBitmap;public PngRect(int width, int height, BufferedImage bitmap){this.mWidth = width;this.mHeight = height;this.mBitmap = bitmap;}public int getWidth(){return this.mWidth;}public int getHeight(){return this.mHeight;}public void setStartP(Point p){mStartP = p;mStopP = new Point(p.x + mWidth, p.y + mHeight);}public Point getStartP(){return mStartP;}public Point getStopP(){return mStopP;}public BufferedImage getBitmap(){return mBitmap;}//判断某个点是否包含在矩形内public boolean contains(Point p){if (mStartP == null){return false;}int x = p.x;int y = p.y;if (x > mStartP.getX() && x < mStopP.getX() && y > mStartP.getY() && y < mStopP.getY()) {return true;}return false;}//把pngs中的图⽚按⾼度从⼤到⼩排序public static void sortPngRects(ArrayList<PngRect> pngs){PngRect maxHeightrect;PngRect tempRect;PngRect currentRect;int k;for (int i = 0; i < pngs.size(); ++i){maxHeightrect = pngs.get(i);currentRect = pngs.get(i);k = i;for (int j = i + 1; j < pngs.size(); ++j){tempRect = pngs.get(j);if (tempRect.getHeight() > maxHeightrect.getHeight()){maxHeightrect = tempRect;k = j;}}if (k != i){pngs.set(i,maxHeightrect);pngs.set(k,currentRect);}}}}。

求解圆形Packing问题的一个启发式算法
康雁;黄文奇
【期刊名称】《计算机研究与发展》
【年(卷),期】2002(039)004
【摘要】求解NP难度问题一直是计算机科学技术中的一个瓶颈任务.自20世纪70年代以来的研究表明,求解NP难度问题不存在既完整严格又不太慢的求解算法.因此,近年来,启发式方法成为研究热点.圆形Packing问题是NP难的,具有很高的理论和实践价值.它的求解目标是寻求多个圆在一个大圆内的一个优良布局,使得这些圆互不重叠地放置.基于拟物法以及适者生存的启发式思想,为圆形Packing问题的快速求解提出了一个高效的启发式算法.算法的高效性通过计算实例得到了验证.【总页数】5页(P410-414)
【作者】康雁;黄文奇
【作者单位】中国科学院软件研究所,北京,100080;华中科学技术大学计算机科学与技术学院,武汉,430074
【正文语种】中文
【中图分类】TP301
【相关文献】
1.求解圆形packing问题的一个快速拟物算法 [J], 康雁;黄文奇
2.求解不等圆Packing问题的一个启发式算法 [J], 陈矛;黄文奇
3.基于禁忌搜索的启发式算法求解圆形packing问题 [J], 康雁;黄文奇
4.基于禁忌搜索的启发式算法求解球体Packing问题 [J], 刘景发;周国城;潘锦基
5.求解2D条带矩形Packing问题的迭代启发式算法 [J], 彭碧涛;周永务
因版权原因，仅展示原文概要，查看原文内容请购买。

第13卷　第5期2008年5月中国图象图形学报Journal of I m age and GraphicsVol .13,No .5M ay,2008 基金项目:国家自然科学基金项目(10471051);国家重点基础研究发展计划(973)项目(2004CB318000)收稿日期:2006201229;改回日期:2007201229第一作者简介:刘　建(1978～　),男。

华中科技大学计算机学院软件与理论专业博士研究生。

从事算法设计与分析的研究。

E 2mail:packlj@求解带平衡约束圆形Pack ing 问题的快速局部搜索算法刘　建黄文奇(华中科技大学计算机科学与技术学院,武汉　430074)摘　要　带平衡性约束的圆集在圆容器内的布局优化问题,属于NP 困难问题。

针对此问题,提出了一种快速的局部搜索算法。

该算法首先构造出等价的物理模型,定义系统的能量函数,再利用最速下降法对能量函数进行优化,从而间接得到问题的近似解。

在局部搜索算法中引入加速策略,提高了计算效率。

最后通过两个算例的数值计算,验证了该方法的可行性和有效性。

关键词　约束布局问题　NP 困难　格局　局部搜索算法　加速策略中图法分类号:TP391 文献标识码:A 文章编号:100628961(2008)0520991207A Fa st L oca l Search A lgor ith m for Solv i n g C i rcles Pack i n g Proble m w ith Con stra i n ts of Equ ili br i u mL I U J ian,HUANG W en 2qi(College of Co m puter Science and Technology,Huazhong U niversity of Science and Technology,W uhan 430074)Abstract The op ti m al layout p r oble m of circle gr oup in a circular container with perfor mance constraints of equilibriu m bel ong t o NP 2hard p r oble m.A fast l ocal serach algorith m (LS )is p resented f or s olving this p r oble m.Firstly,the method constructs an equivalent physicalmodel and defines the energy functi on of the syste m.Then the energy functi on is op ti m ized by the steepest descent method and the app r oxi m ati on s oluti on is obtained indirectly .I n order t o i m p r ove the computati onal efficiency,the accelerating strategy is added t o the LS algorith m.T wo exa mp les are computed nu merically,and the results of the experi m ent show the feasibility and efficiency of the app r oach .Keywords constrained layout p r oble m,NP 2hard,configurati on,l ocal search algorith m,accelerating strategy1　引　言布局问题就是寻找给定待置物的一种合理放置方案,使其所占空间最小。