收稿日期:2002-11-20.
作者简介:王华昌(1968-),男,讲师;武汉,华中科技大学塑性成形模拟及模具技术国家重点实验室(430074).
一种矩形件优化排样综合算法
王华昌 陶献伟 李志刚
(华中科技大学塑性成形模拟及模具技术国家重点实验室)
摘要:提出了应用于矩形件优化排样中的关键算法:条料生成算法与填充算法.把二者融合在一起,提出了一种适用于矩形件优化排样的最小残料算法.该算法依据残料大小决定条料,并对空白矩形进行有效填充,可快速得到排样结果.将其与模拟退火算法相结合,能够跳出局部搜索,最终可获得近似总体最优的排样结果.关 键 词:矩形件优化排样;条料生成算法;填充算法;最小残料算法;模拟退火算法中图分类号:T G316 文献标识码:A 文章编号:1671-4512(2003)06-0009-04
矩形件优化排样是指有多种不同矩形件,每种矩形件需要若干个,尽可能多地排放,使给定的矩形板材利用率最高.矩形件优化排样问题实质是一个组合优化的二维布局问题,具有工件种类多、数量大等特点,是计算复杂性最高的一类NP 完全问题,至今还无法找到解决该问题的有效多项式时间算法.
国内外已经有不少专家学者在这个领域做了很多研究工作,并且取得了一些成果,例如背包算法[1]、组块技术[2]等,都能够得到较好的排样效果.但是,前者是近似优化算法,后者是局部搜索方法,达不到排样的总体最优.而不经任何处理的模拟退火排样算法虽然可达到近似最优解,却不适合/一刀切0的下料工艺,只适合/正交切割0.
为获得总体最优解,作者提出了最小残料算法.该算法是一种接近最优解的局部搜索算法,适用于矩形件毛坯的优化排样.将其与模拟退火算法思想相结合,能随机地接受某些劣化解,跳出局部极小点,因而有较强的全局搜索能力.同时,可满足排样速度快、板材利用率高的要求和/一刀切0高效率下料工艺,从而较好地解决了现行排样算法中存在的上述问题.
1 最小残料算法
1.1 数据结构
设板材的长度为l,宽度为w ,工件种类数为n,则矩形工件基本信息存储如下:
typedef struct tagRect
{
int w ;M 工件宽度 int l ;M 工件长度
int n ;M 工件数目}Rect,*pRect;
矩形工件输出坐标如下:typedef struct tag Point
{
int x 1;M 当前输出工件左下角点横坐标 int y 1;M 当前输出工件左下角点纵坐标 int x 2;M 当前输出工件右上角点横坐标 int y 2;M 当前输出工件右上角点纵坐标}XPoint,*pXPoint;1.2 约束条件和目标函数
排样的基本目标是使得排样所用的板材数尽可能少,以提高材料的利用率;排样的基本约束条件是矩形件之间不能有相互重叠区域,并且矩形件不能有排出板材的部分.排样规则为每一个矩形件可以被横向排放或者纵排.排样方式为从板材的最左下角开始排到板材的右上角结束一块板材的排样.设板材左下角的坐标为(0,0),(x 1i ,y 1i )和(x 2i ,y 2i )为第i 块矩形工件在板材上左下角和右上角坐标,那么他们的关系为
x 2i =x 1i +Rect [i].l ;
y 2i =y 1i +Rect [i].w ,
或者
x 2i =x 1i +Rect [i].w ;y 2i =y 1i +Rect [i].l ,
其中前者为横排时同一矩形件坐标关系,后者为
第31卷第6期 华 中 科 技 大 学 学 报(自然科学版) V ol.31 No.62003年 6月
J.Huazhong U niv.of Sci.&T ech.(Nature Science Editio n)
Jun. 2003
纵排时同一矩形件坐标关系,则排样的过程就是根据一定的寻优规则,确定每个矩形工件在板材上的左下角和右上角坐标.
设任意两个参加排样的矩形工件的左下角和右上角坐标分别是(x1s,y1s),(x2s,y2s)和(x1t, y1t),(x2t,y2t),则满足下面任何一种情况,工件不会相互重叠:a.x2s[x1t;b.x1s\x2t;
c.y1t\x2s;
d.y2t[x1s.
对于任意第i种工件,必须满足下面的约束,否则工件必然越出板材之外:a.x1i\0;
b.y1i\0;
c.x2i[nl;
d.y2i[w;
在满足以上初始约束条件的前提下,使得板材利用率尽可能地高,因此,优化排样的目标函数可表达为
max E n i=1(Rect[i].l Rect[i].w#
Rect[i].n)/([Point[last].x2-w]w),
式中,Point[last].x2为最后一个排样工件右上角横坐标;w为板材之间间隔.
1.3条料生成算法
排样问题是二维布局的问题,化二维布局为一维布局,即沿板材的宽度方向不断产生条料.生成条料的方式很多,作者所提出的基于最小残料的条料生成算法能够使板材利用率在宽度方向达到最高,算法描述如下:
a.把所有的工件按照长度从大到小排序;
b.令i=n,k=1;
c.从第i种工件沿着板材宽度方向试探排样;
d.令h=i,若当前第h种工件排样完毕,则令h=h-1,若Rect[h].n不为0,则紧邻以上工件继续试探排样;若为0,则续排下一种工件.同时,每排一个工件,须判定板材宽度是否排完;
e.若板材宽度仍可排,则转d,继续排样,直到不可排.否则,返回剩余宽度Leftw idth[k].若Leftw idth[k]为0,则中止循环,转g,否则,顺序执行;
f.令i=i-1,k=k+1,转c,继续第k种方案排样,直到i=0,中止循环;
g.确认Leftw idth[k]为最优条料生成途径;
h.输出此次沿宽度方向的排样结果.
为更加清楚地说明条料生成过程,下面给出一个典型例子.表1所示为排样数据,共有4种工件,板材宽度为1000mm,长度不定.
按照以上描述的条料生成算法,表中矩形工件的首次条料生成过程如图1~4所示.
表14种工件的参数
序号n l/mm w/mm
11283040
23680140
37460110
49230160
图1条料生成方案1图2条料生成方案2
L eftw idth[1]=100mm Leftwidth[2]=30mm
图3条料生成方案3图4条料生成方案4
L eftw idth[3]=70mm L eftw idt h[4]=40mm
由图中可知,条料生成方案2的剩余宽度最小.根据算法判断准则,该方案为首次条料最终生成方案.在条料产生的同时,会出现如图中阴影表示的空白矩形,如何对这些空白矩形进行填充,则是算法的关键.
1.4空白矩形的填充算法
每个空白矩形都可看作一块一定尺寸的板材.由于其尺寸相对较小,针对这种情况,作者开发了专门用于空白矩形排样的填充算法.对未排工件分别进行横向排列和纵向排列的试探,判断是否能够对其进行填充.如果能够填充,则选择横向填充或者纵向填充,并进而得到排样的条料.在完成上述填充过程的同时,在原空白矩形上会产生更多的更小的空白矩形,调用填充算法对其进一步填充,直到任何待排工件都不能再填充为止.算法描述如下:
a.设由条料生成算法得到空白矩形长度和宽度分别为l和w;
b.令i=n-1,若i\0,Rect[i].n>0,判断工件长度是否大于板材宽度,如果是,采用连续横排,转e;否则,顺序执行;
c.对于所有待排工件,计算最小工件长度
10华中科技大学学报(自然科学版)第31卷
min -l =min{Rect [i].l};
d .分别计算局部利用率,
LocalRatio1=(Rect [i ].n Rect [i ].l #Rect [i].w )/(l 1w ),
LocalRatio2=(Rect [i ].n Rect [i ].l #Rect [i].w )/(l 2w ),
并取M ax {LocalRatio1,LocalRatio2},由此判定选用连续横排或者连续纵排;
e .对于所产生的空白矩形进行填充,令k =n -1,若k \0,则Rect [k ].n >0;对工件k 进行试探填充,若满足约束条件,则调用相应空白矩形填充算法,对其填充.对于所产生的新的空白矩形,继续调用填充算法,直到不能填充任何工件为止.填充完毕后,令k =k -1,更新工件数目;
f .判断剩余板材长度l 是否大于m in -l ,如果大于,转b ;否则,调用结尾空白矩形填充算法对其填充,更新工件信息.若工件的总数目大于0,产生下一张板材,转c .否则,顺序执行;
g .输出排样结果,包括用于输出图形的坐标文件和每块板材的排样信息.
1.5 最小残料算法
综合条料生成算法与填充算法,导出适合于矩形件排样的最小残料算法,可描述如图5所示
.
图5 最小残料算法流程图
2 模拟退火算法的应用
利用最小残料算法的排样存在一个缺陷,那就是在产生条料时,只能按照对工件的长度排序依次产生,虽然能够保证得到当前最小残料的条料,却不能保证第i 个工件在该位置是最合适的.
为解决上述问题,作者将模拟退火算法思想应用于最小残料算法中,增加解的空间,一定程度接受劣质解,提高全局搜索能力,可得到近似最优
解.
模拟退火算法[3]应用的一般形式是:从选定的初始解开始,利用一个新解产生装置和接受准则,重复执行包括/产生新解)))计算目标函数差)))判断是否接受新解)))接受(或者舍弃)新解0这四个任务的试验,不断对当前解迭代,从而达到使目标函数最优的执行过程.
当满足以下条件时,算法中止[4]:
a .算法获得的当前最优解达到预定值;
b .算法对所有可能点搜索完毕.
综合最小残料算法和模拟退火算法的最优毛坯排样算法可用图6表示.
图6 模拟退火求解算法流程图
3 排样实例
基于上述算法,给出了两个典型算例.
算例1 表2所示为7种工件的参数,该组工件中,每种工件的数量较多,而且工件尺寸与板材尺寸相对差异较大,工件之间尺寸差异不大,属于中等规模排样.板材的尺寸为4000mm @2900mm,获得的排样结果如图7所示.
表2 7种工件的参数
序号n l /mm w /mm 11034506027050010039054070412040010051502001006403601507
45
450
120
图7 排样图(板料利用率为97.75%)
算例2 表3所示为26种工件的参数,该组工件中,每种工件的数量很少,而且工件尺寸与板
11
第6期 王华昌等:一种矩形件优化排样综合算法
表326种工件的参数
序号n l/mm w/mm
14740290
221190290
31117050
411190690
521170220
62730600
73590290
82880290
9186050
1011820290
111180050
1211810690
131890220
144730450
154600290
162540200
1721480290
181146050
191880540
202860220
214600450
221690270
2311480540
241880220
252570220
262600590
材尺寸相对差异较为接近,工件之间尺寸差异不大,属于难度较高的排样问题,适用于非批量生产.板材的尺寸为1850mm@1240mm,获得的排样结果如图8所示
.
图8排样图(板料利用率为90.38%)
参考文献
[1]曹炬,周济,余俊.矩形件排样的背包算法.中
国机械工程,1994,5(2):11~12
[2]崔耀东.矩形毛坯下料排样的一种优化算法.机械工
艺师,1998(6):32~33
[3]康立山,谢云,尤矢勇等.非数值并行算法(第一
册))))模拟退火算法.北京:科学出版社,1994. [4]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算
法求解.四川大学学报(工程科学版),2001,33(5): 35~38
A synthetical algorithm for the optimal layout of rectangular part
Wang H uachang Tao X ianw ei L i Zhigang
Abstract:A minimal area algorithm for the optimal layout for rectang ular parts w as proposed based on strip creation algorithm and rectangle-filling algorithm.This algorithm means the choice of the created strip de-termined by the remained area and filling the rectangle created by the strip efficiently.T o find global opt-i mal layout solution,the simulated annealing algorithm w as integ rated w ith the minimal area.It overcomes the defect of the minimal area algorithm and jum ps out of the poor qualified result point.
Key words:rectangular parts optimal layout;strip creation algorithm;rectangle-filling algorithm;m inim al area algorithm;simulated annealing algorithm
W ang Huachang Lect.;State Key Lab.of Plastic Forming Simulation and Die&Mould Tech., Huazhong Univ.of Sci.&Tech.,Wuhan430074,China.
12华中科技大学学报(自然科学版)第31卷
我伟大的母校 课程设计报告书 实践课题：动态分区分配 姓名：路人甲 学号：20XXXXXX 指导老师：路人乙 学院：计算及科学与技术学院 课程设计实践时间 2013.3.11~2013.3.22
一．课程设计的目的： 二．设计内容： 三．设计要求： 四．程序流程图 Alloc
Best_fit Worst_fit
Free Show
Main 五．源代码 #include
typedef struct DuLNode//结构指针 { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 } DuLNode,*DuLinkList;//指针链表 DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点 Status alloc(int);//内存分配 Status free(int); //内存回收 Status Best_fit(int); //最佳适应算法 Status Worst_fit(int);//最差适应算法 void show();//查看分配 Status Initblock();//开创空间表 Status Initblock()//开创带头结点的内存空间链表 { block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.state=Free; return OK; } //分配主存 Status alloc(int ch) { int request = 0; cout<<"请输入需要分配的主存大小(单位:M)："; cin>>request; if(request<0 ||request==0) { cout<<"分配大小不合适，请重试！"< 矩形件排样程序的实现王晨浩-试题b ————————————————————————————————作者: ————————————————————————————————日期: 矩形件排样程序的实现 王晨浩 摘要 针对样板矩形排样程序的实现问题,本人通过实施FORTRＡN90编程,采用直接明了的数字排列的方式,直观清晰的展现了一个矩形样板中矩形件排样的最优方案。而程序语言本身，结构明朗,层次清晰，适合懂本语言的人斟酌损益和修缮完美；程序运行系统,清晰明朗的输入输出步骤,将程序层序化和普遍化展现淋漓；程序表述方式，人性化的中文语言提示，将程序的可接受度和观赏度大大提高。 本程序采取了通过对板面和具体矩形的数字化展现,通过对整体的数字比较描摹和判定板面的整体矩形排列方式,最终以一个具体的数字排列，实现对矩形排列的宏观显现。关键词:ＦORTＲAN90程序,矩形排列方案，板面矩形设计 一、问题重述 （一) 问题简介 工业上经常需要在一块大板材上下料得到若干个小的矩形件,使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽１5、高无限制的矩形板材上,排列2５块尺寸已知的小矩形,2５块小矩形的尺寸如表1,板材的利用率达10０％,如图１所示。 图1 一种排样方案 表１ 小矩形的尺寸 序号 宽 高 1 1２ 6 2 4 7 ３ ６ 7 ４ 10 ２ ５ 2 ５ ６ 6 4 7 ４ 2 8 ４ 6 9 7 ９ 10 4 5 11 6 4 12 4 6 13 ６ 3 14 4 ５ １5 2 4 16 8 ４ １７ 8 6 1８ 8 3 １９ 6 3 ２0 2 6 ２１ 8 2 22 3 5 2３ ２ ５ 2４ 3 4 ２5 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这２5块小矩形按照某种次序排在一个大的板材上呢?目前这仍是一个世界难题。 通常要求在一个排样图中,任何一个矩形件在不超出板材边界的情况下,按照一个排样方案(给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案(解）},{R P D =,其中),,,(21n p p p P =，),,,(21n r r r R =,p i 为矩形件的序号,r i 为排样方式，r i =１表示将矩形件旋转90°， r i =０表示矩形件不旋转。将第i 个矩形件安排在板材上的过程中,均不能再往下、往左移动，则称其满足B Ｌ条件(ｂo ｔtom-l ｅｆｔ-con ｄｉｔｉｏn ，B Ｌ-c ｏｎdition)。 操 作 系 统 实 验 报 告 课程名称：操作系统 实验题目：首次适应算法 姓名： **** 专业班级： *********** 学号： ************* 指导老师： ***** 一、实验目的 在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。 二、实验要求 1.内存大小初始化 2.可以对内存区进行动态分配，采用首次适应算法来实现 3.可以对已分配的内存块进行回收，并合并相邻的空闲内存块。 三、实验内容 把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配给该作业的内存块，并合并相邻的空闲内存块。 四、实验结果 运行效果： 1.初始化内存区大小，并添加作业，选择1添加作业 2. 当作业大小超过存储块大小时，分配失败。 3.选择3，可查看内存分配情况 4.选择2回收内存 5.添加新作业 6.回收C作业，相邻的空闲内存块合并。 五、实验总结 首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始查找，直到找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区仍留在空闲链中。若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败。这里，我采用数组的方式，模拟内存分配首次适应算法，动态的为作业分配内存块。可以根据作业名称回收已分配的内存块，当空闲内存块相邻时，则合并。 通过此次的实验，让我对内存分配中首次适应算法更加熟悉，在此基础上，我也测试最佳适应算法（best_fit）和最坏适应算法（worst_fit），并对其进行了比较分析，从比较中我发现，针对同一个问题，解决的方法不止一种，而且不同的方法所要消耗的资源和时间也不相同，根据不同的要求，方法的优劣也不同，可以说方法是解决问题的一种模式，随环境不同而体现出优越性。 六、实验附录 程序源代码： #include 矩形件排样程序实现（要求：只能由一个学生独立完成，不得抄袭）工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽40、高15的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。 图1 一种排样方案 表1 小矩形的尺寸 序号宽高 1 1 2 6 2 4 7 3 6 7 4 10 2 5 2 5 6 6 4 7 4 2 8 4 6 9 7 9 10 4 5 11 6 4 12 4 6 13 6 3 14 4 5 15 2 4 16 8 4 17 8 6 18 8 3 19 6 3 20 2 6 21 8 2 22 3 5 23 2 5 24 3 4 25 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形 按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。 通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，p i 为矩形件的序号，r i 为排样方式，r i =1表示将矩形件旋转90°, r i =0表示矩形件不旋转。将第i 个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL 条件（bottom-left-condition ，BL-condition ）。 基于BL 条件，有一种下台阶算法，具体步骤如下： (1) 将零件1p 排放在板材的左下角，若11=r 则将其旋转90°后再排放，求出排放后所占板材的最大高度； (2) 将i p ),,3,2(n i =根据其排样方式置于板材右边最大高度处，向下向左移动i p ，且向下移动优先（即原本已无法再向下移动，故开始向左移动，而在向左移动的过程中若发现又能继续向下移动，则先向下移动），直至i p 无法向下向左移动为止（即接触到其他零件或板材边界），并求出此时的最大高度； (3) 重复上述过程，直至所有零件排放完毕，最后所得最大高度即为所需板材高度。 其排样过程如图2所示，就好象下台阶一样，于是形象地称之为下台阶算法。 图2 下台阶算法的排样过程 剩余矩形排样法是目前所提出的一种有效的排样算法，该方法记录了所有可利用的空间，更能合理地分配给待排样的矩形件，提高了每个排样方案的板材利用率，更接近最优排样方案。例如对于同一个矩形件序列)4,3,2,1(进行排样， 矩形件排样程序的实现 王晨浩 摘要 针对样板矩形排样程序的实现问题，本人通过实施FORTRAN90编程，采用直接明了的数字排列的方式，直观清晰的展现了一个矩形样板中矩形件排样的最优方案。而程序语言本身，结构明朗，层次清晰，适合懂本语言的人斟酌损益和修缮完美；程序运行系统，清晰明朗的输入输出步骤，将程序层序化和普遍化展现淋漓；程序表述方式，人性化的中文语言提示，将程序的可接受度和观赏度大大提高。 本程序采取了通过对板面和具体矩形的数字化展现，通过对整体的数字比较描摹和判定板面的整体矩形排列方式，最终以一个具体的数字排列，实现对矩形排列的宏观显现。关键词：FORTRAN90程序，矩形排列方案，板面矩形设计 一、问题重述 （一）问题简介 工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽15、高无限制的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。 图1 一种排样方案 表1 小矩形的尺寸 序号 宽 高 1 12 6 2 4 7 3 6 7 4 10 2 5 2 5 6 6 4 7 4 2 8 4 6 9 7 9 10 4 5 11 6 4 12 4 6 13 6 3 14 4 5 15 2 4 16 8 4 17 8 6 18 8 3 19 6 3 20 2 6 21 8 2 22 3 5 23 2 5 24 3 4 25 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。 通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，p i 为矩形件的序号，r i 为排样方式，r i =1表示将矩形件旋转90°, r i =0表示矩 形件不旋转。将第i 个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL 条件（bottom-left-condition ，BL-condition ）。 第26卷第1期2005年2月 青岛科技大学学报 Jour nal ofQ i n gdao University o f Science and Techno logy V o.l26No.1 Feb.2005 文章编号:1672-6987(2005)01-0065-05 二维矩形排样问题的启发式算法 邵巍,隋树林,杜军威 (青岛科技大学自动化与电子工程学院,山东青岛266042) 摘要:矩形件优化排样问题具有多个算法,但是这些算法均有一些局限性,如排列不规则,计算量巨大等等。本文给出了单一尺寸的矩形排样问题的几种启发式算法,它克服了现有众多排样算法执行效率低的缺陷,使板料排样的执行效率和优化率均得以显著提高,并用D elphi编程实现,可直接应用于实际问题中。 关键词:排样问题;启发式算法;De l p h i 中图分类号:TP391文献标识码:A So m e K i nd of A lgorith m s for the Opti m al Layout of Rectangul ar Part S HAO W e,i SU I Shu-li n,DU Jun-we i (College ofAu t o m ati on and E l ectron i c E ngi neeri ng,Q i ngdao U nivers it y of Sci en ce and T echnol ogy,Q i ngdao266042,Ch i na) A bstract:There are l o t o f algor ith m s on the opti m al layout o f rectancular par,t butm ost of the a l g orit h m s have som e li m its(such as irregu lar arrange m en,t excessive ca lculating,etc.). K inds o f heuristic algorithm is g iven i n th is paper.It overco m es sone proble m s for m ost o f a l g o-rithm s at a lo w executi n g rate can high ly enhance the executive rate and i n crease the radio of the opti m izati o n.It carried it out w ith De l p h i language,these a l g orith m s can be used w e ll in practice. K ey words:layou;t heuristic algorithm;Delphi 切割(cuttingprob le m)和装填问题(pack i n g-proble m)统称为布局问题,属于复杂的组合最优化范畴,已经证明即使是最简单的布局问题,也是NP完全问题,因此,绝大部分有效的解决布局问题的算法都是启发式的方法[1~6]。由于许多企业应用板材数量巨大,所以提高很少的利用率便可节省很多原材料,大大降低成本。本工作针对现有众多排样算法执行效率低的缺陷,给出了单一尺寸的矩形排样问题的几种启发式算法。 1数学模型的建立及算法 设在L*W(分别记各边为上L,下L,左W,右W)的矩形内放入a*b的小矩形,不妨设a\b,要使得大矩形中放入尽量多的小矩形。 1.1方法1 先设在下L边上排列n个a,m个b,自下到上依次排列各矩形,并记在垂直方向上堆放t个b,k个a,尽量使得W方向排列尽量多的小矩形,直到不能再放置a或b边,如图1(a)所示。 此种排法的约束条件可描述为: L-b 首次适应算法,最佳适应算法,最坏适应算法源代码[宝典] 首次适应算法,最佳适应算法,最坏适应算法源代码#include void show();//查看分配 Status Initblock();//开创空间表 Status Initblock()//开创带头结点的内存空间链表{ block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.state=Free; return OK; } //分配主存 Status alloc(int ch) { int request = 0; cout<<"请输入需要分配的主存大小(单位:KB):"; cin>>request; if(request<0 ||request==0) { cout<<"分配大小不合适，请重试～"< #include 收稿日期:2002-11-20. 作者简介:王华昌(1968-),男,讲师;武汉,华中科技大学塑性成形模拟及模具技术国家重点实验室(430074). 一种矩形件优化排样综合算法 王华昌 陶献伟 李志刚 (华中科技大学塑性成形模拟及模具技术国家重点实验室) 摘要:提出了应用于矩形件优化排样中的关键算法:条料生成算法与填充算法.把二者融合在一起,提出了一种适用于矩形件优化排样的最小残料算法.该算法依据残料大小决定条料,并对空白矩形进行有效填充,可快速得到排样结果.将其与模拟退火算法相结合,能够跳出局部搜索,最终可获得近似总体最优的排样结果.关 键 词:矩形件优化排样;条料生成算法;填充算法;最小残料算法;模拟退火算法中图分类号:T G316 文献标识码:A 文章编号:1671-4512(2003)06-0009-04 矩形件优化排样是指有多种不同矩形件,每种矩形件需要若干个,尽可能多地排放,使给定的矩形板材利用率最高.矩形件优化排样问题实质是一个组合优化的二维布局问题,具有工件种类多、数量大等特点,是计算复杂性最高的一类NP 完全问题,至今还无法找到解决该问题的有效多项式时间算法. 国内外已经有不少专家学者在这个领域做了很多研究工作,并且取得了一些成果,例如背包算法[1]、组块技术[2]等,都能够得到较好的排样效果.但是,前者是近似优化算法,后者是局部搜索方法,达不到排样的总体最优.而不经任何处理的模拟退火排样算法虽然可达到近似最优解,却不适合/一刀切0的下料工艺,只适合/正交切割0. 为获得总体最优解,作者提出了最小残料算法.该算法是一种接近最优解的局部搜索算法,适用于矩形件毛坯的优化排样.将其与模拟退火算法思想相结合,能随机地接受某些劣化解,跳出局部极小点,因而有较强的全局搜索能力.同时,可满足排样速度快、板材利用率高的要求和/一刀切0高效率下料工艺,从而较好地解决了现行排样算法中存在的上述问题. 1 最小残料算法 1.1 数据结构 设板材的长度为l,宽度为w ,工件种类数为n,则矩形工件基本信息存储如下: typedef struct tagRect { int w ;M 工件宽度 int l ;M 工件长度 int n ;M 工件数目}Rect,*pRect; 矩形工件输出坐标如下:typedef struct tag Point { int x 1;M 当前输出工件左下角点横坐标 int y 1;M 当前输出工件左下角点纵坐标 int x 2;M 当前输出工件右上角点横坐标 int y 2;M 当前输出工件右上角点纵坐标}XPoint,*pXPoint;1.2 约束条件和目标函数 排样的基本目标是使得排样所用的板材数尽可能少,以提高材料的利用率;排样的基本约束条件是矩形件之间不能有相互重叠区域,并且矩形件不能有排出板材的部分.排样规则为每一个矩形件可以被横向排放或者纵排.排样方式为从板材的最左下角开始排到板材的右上角结束一块板材的排样.设板材左下角的坐标为(0,0),(x 1i ,y 1i )和(x 2i ,y 2i )为第i 块矩形工件在板材上左下角和右上角坐标,那么他们的关系为 x 2i =x 1i +Rect [i].l ; y 2i =y 1i +Rect [i].w , 或者 x 2i =x 1i +Rect [i].w ;y 2i =y 1i +Rect [i].l , 其中前者为横排时同一矩形件坐标关系,后者为 第31卷第6期 华 中 科 技 大 学 学 报(自然科学版) V ol.31 No.62003年 6月 J.Huazhong U niv.of Sci.&T ech.(Nature Science Editio n) Jun. 2003 ）数据挖掘分类算法之决策树（zz Decision tree决策树（）以实例为基础的归纳学习算法。决策树是 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采 并根据不同的用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路属性值从径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年又ID3算法的基础上，1993年QuinlanQuinlan提出了著名的ID3算法。在提出了若干改提出了C4.5算法。为了适应处理大规模数据集的需要，后来又SPRINT (scalable 进的算法，其中SLIQ(super-vised learning in quest)和是比较有代表性的两个算法。parallelizableinduction of decision trees) (1) ID3算法算法的核心是：在决策树各级结点上选择属性时，用信息增益 ID3）作为属性的选择标准，以使得在每一个非叶结点进行测（information gain 检测所有的属性，其具体方法是：试时，能获得关于被测试记录最大的类别信息。再对由该属性的不同取值建立分支，选择信息增益最大的属性产生决策树结点，直到所有子集仅包含同一各分支的子集递归调用该方法建立决策树结点的分支，类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较 它们的大小，就不难获得具有最大信息增益的属性。个m个不同值，定义mS 设是s个数据样本的集合。假定类标号属性具有中的样本数。对一个给定的样本分类所需si是类Ci不同类Ci(i=1,…,m)。设的期望信息由下式给出：为底，其原2Ci 其中pi=si/s的概率。注意，对数函数以是任意样本属于因是信息用二进制编码。个划分为v可以用属性A将Sv 设属性A具有个不同值{a1,a2,……,av}。aj上具有相同的值A，其中Sj中的样本在属性子集 {S1,S2,……,Sv}（j=1,2,……,v）。设sij是子集Sj中类Ci的样本数。由A 划分成子集的熵或信息期望由下式给出： 熵值越小，子集划分的纯度越高。对于给定的子集Sj，其信息期望为 其中pij=sij/sj 是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是 Gain(A)= I(s1, s2, …,sm)-E(A) ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：决策树可当训练数据集加大时，且对噪声比较敏感，只对比较小的数据集有效，能会随之改变。算法(2) C4.5 ID3 C4.5算法继承了算法的优点，并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值1) 实验四操作系统-动态分区分配算法萨斯的发生的v设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求如下： 1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。 2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。 3）输入：空闲分区个数n，空闲分区大小P1, …,P n，进程个数m，进程需要的分区大小S1, … ,S m，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。 4）输出：最终内存空闲分区的分配情况。 代码实现： #include int FreePartition[MaxNumber];次适应算法 2.循环首次适应算法 3.最佳适应算法 4.最坏适应算法:"< 1 第七章 习题及解答 7-11如图7.45所示，主存中有两个空白区。现有如下程序序列：程序1要求50KB ；程序2要求60KB ；程序3要求70KB 。若用首次适应算法和最佳适应算法来处理这个程序序列，试问：哪一种算法可以分配得下 ? 简要说明分配过程 (假定分区描述器所占用的字节数已包含在程序所要求的主存容量中) 。 图7.45 答：(1) 首次适应法： 程序1要求50KB ，在起始地址为150KB ，大小为120 KB 的空白区进行分割。120KB -50KB=70KB ，分割后剩70KB 的空白区。 程序2要求60KB ，在剩余的70KB 空白区进行分割。70KB -60KB=10KB ，分割后剩 10KB 的空白区。 程序3要求70KB ，在起始地址为300KB ，大小为78KB 的空白区进行分割。78KB -70KB=8KB ，分割后剩8KB 的空白区。 因此首次适应法可满足该程序序列的需求。 (2) 最佳适应法 程序1要求50KB ，在起始地址为300KB ，大小为78 KB 的空白区进行分割。78KB -50KB=28KB ，分割后剩28KB 的空白区。 程序2要求60KB ，在起始地址为150KB ，大小为120KB 的空白区进行分割。120KB -60KB=60KB ，分割后剩60KB 的空白区。 程序3要求70KB ，。此时系统中有大小为 28KB 和60KB 的两个空白区，它们均不能满足程序3 的需求。 因此最佳适应法不能满足该程序序列的需求。 150K B 300K B 主存 7-12已知主存有256KB 容量，其中OS 占用低址20KB ，可以有这样的一个程序序列。 程序1要求 80KB ；程序2要求16KB ；程序3要求 140KB 。 程序1完成；程序3完成。 程序4要求 80KB ；程序5要求120KB 。 试分别用首次适应算法和最佳适应算法分别处理上述程序序列 (在存储分配时，从空白区高址处分割作为已分配区)，并完成以下各步骤。 (1) 画出程序1、2、3进入主存后主存的分配情况。 (2) 画出程序1、3完成后主存分配情况。 (3) 试用上述两种算法中画出程序1、3完成后的空闲区队列结构 (要求画出分区描述器信息，假定分区描述器所需占用的字节数已包含在程序所要求的主存容量中) 。 (4) 哪种算法对该程序序列而言是适合的？简要说明分配过程。 (1) 答：程序1、2和3 进入主存后，主存的分配情况如下图所示。 (2) 答：程序1、3 完成后，主存的分配情况如下图所示： (3) 答：首次适应法下，空闲区队列结构如下图所示。 队列指针 主存 0 256KB -1 160KB 20KB 176KB 主存 0 256KB -1 20KB 160KB 176KB 最佳适应算法源程序代码 #include int flag; //空闲区表登记栏标志，用"0"表示空栏目，用"1"表示未分配}free_table[M]; //空闲区表对象名 //函数声明 void initialize(void); int distribute(int, float); int recycle(int); void show(); //初始化两个表 void initialize(void) { int a; for(a=0; a<=N-1; a++) used_table[a].flag=0; //已分配表的表项全部置为空表项 free_table[0].address=1000; free_table[0].length=1024; free_table[0].flag=1; //空闲区表的表项全部为未分配 } //最优分配算法实现的动态分区 最佳适应算法实验报告 一、实验目的 了解首次适应算法、最佳适应方法、最差适应算法 二、实验方法 修改Minix操作系统的内存分配源码，实现最佳适应算法 三、实验任务 修改Minix操作系统中的内存分配源码，将首次适应算法更改为最佳适应算法。重新编译系统映像文件，观察实验结果。 四、实验要点 内存分配、首次适应算法、最佳适应算法。 五、实验内容 5.1 minix内存分配源码 安装好minix操作系统以后，minix系统的源码位于/usr/src目录中。其中，与内存分配的相关源码则在/usr/src/servers/pm/alloc.c中。minix系统初始的内存分配算法为首次适应算法。 在minix系统中，空闲的内存空间信息采用链表的信息储存起来，而操作系统分配内存空间的过程则是在这个链表中寻找一个合适空间，返回内存空间的地址，再更改链表中的内存空间信息。这就是minix系统分配内存的实质。 5.2分析首次适应算法 首次适应算法，指的从空闲内存块链表的第一个结点开始查找，把最先找到的满足需求的空闲内存块分配出去。这种算法的优点是分配所需的时间较短，但这种算法会形成低地址部分形成很多的空间碎片，高地址区保留大量长度较长的空闲内存块。 内存分配的操作在/usr/src/servers/pm/alloc.c源文件中的alloc_mem函数中完成。在函数的初始位置，定义了两个用于遍历链表的指针变量，两个指针变量的定义如下：registerstruct hole *hp, *prev_ptr; 而hole结构体的定义如下： PRIVATE struct hole { struct hole *h_next; phys_clicksh_base; phys_clicksh_len; } hole[NR_HOLES]; 先分析这个结构体的定义，这个结构体中，有三个变量，h_next是一个指向链表下一个结点的指针变量；h_base则是指向这个链表所表示的空闲内存空间的地址，h_len 则是这个空闲内存空间的长度；phys_clicks的定义可以在/usr/src/include/minix/type.h 中找到，phys_clicks的定义为： typedef unsigned intpyhs_clicks; 学号专业姓名 实验日期教师签字成绩 实验报告 【实验名称】采用可变式分区管理，使用首次获最佳适应算法实现内存分配与回收 【实验目的与原理】 1、理解首次获最佳适应算法的内涵，并熟练掌握该算法。 2、学会可变式分区管理的原理是即在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。 3、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区没有时应将空闲区一分为二。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。 4、当一个作业执行完成时，作业所占用的分区应归还给系统。作业的释放区与空闲区的邻接分以下四种情况考虑： ①释放区下邻（低地址邻接）空闲区； ②释放区上邻（高地址邻接）空闲区 ③释放区上下都与空闲区邻接； ④释放区与空闲区不邻接。 【实验内容】 #include矩形件排样程序的实现王晨浩试题b
首次适应算法 内存分配
B题：矩形件排样程序实现
矩形件排样程序的实现王晨浩-试题b
二维矩形排样问题的启发式算法
首次适应算法,最佳适应算法,最坏适应算法源代码[宝典]
首次适应算法和最佳适应算法-C++语言版
一种矩形件优化排样综合算法
C45算法的源代码全解
操作系统-实验四动态分区分配算法源代码最全
第7章习题及答案
最佳适应算法-源程序代码
实验三 最佳适应算法 实验报告
操作系统 首次最佳适应算法
相关主题
文本预览