最优切割问题

4c4af04fbf3e0a802967f339bf469771.pdf 最优切割问题 99131059 魏 炜一：问题的提出某些工业部门（如贵重石才的加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两个部分。从一个长方体中加工出一个已知尺寸位置预定的长方体（这个长方体的对应表面是平行的），通常要经过6次截断切割。设水平切割单位面积的费用是垂直切割单位面积的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。试为这些部门设计一种安排个面加工次序的方法。待加工的长方体和成品的长，宽，高分别为10，14.5,19和3,2,4两者左侧面，正面，底面之间的距离分别为6 ,7,9（单位均为厘米）垂直切割的费用为每平方厘米1元。r和e数据如下(a)r=1,e=0 (b)r=1.5 e=2二：问题的分析刚拿到这个题目时，还是很茫然的，不知应该用什么样的方法进行解答，当学到图与网络分析的时候，突然觉得这道题是不是可以用最短路的来求解呢？抱着试试看的心里，我将问题成功的转换成了求一个图的最短路的问题，而我们要求最短路就是要先求出每一条边所表示的权重。三：问题的解决设待加工体的长、宽、高分别为a0、b0、c0。六个切割面分别位于左、右、前后、上下相应为S1、S2、S3、S4、S5、S6。这六个面与成品的相应外测面的距离分别为d1、d2、d3、d4、d5、d6。不失一般性设d1=d2、d3=d4、d5=d6。故可以只考虑S1在S2前、S3在S4前、S5在S6前被切割的方式。I：e=0 r=1 的情形。先考虑如何建立图形。将切割问题转化为求图的最短路径问题。赋权网络图G*的建立。由于共计切6刀，因此我们想到要建立一个三维网络图： 图形的解释。图中各个点表示每个切割状态。例如 表示最初状态，表示已经切割完毕。表示左前被切一刀，前后各被切一刀，上下没有被切。 求权*的过程。G的边（表示石材被切割的一个过程。若两个定点之间有弧，当且仅当的时候，则我们把相应的弧上的权看成是切割过程的费用。当我们得到这个计算方法时，看到图形有27个点，需要计算很多权。因为我们要用图中Dijkstra算法*。这个看似很繁琐，但当我们做了每两点之间的权后，发现是有规律可循的，其规律如下：总有两个参量是不变的，因此我们总能得到关于一个参量的结果。如果没有变化，且满足，因此剩余变量差总为1，后面为不变量两者相应的长、宽、高中的两者相乘即可，所以得到底是怎么样得一个状态呢？其实也是有规律可以遵循的，例如：，首先第一和第三变量不变，因此权为而相应数均为2，因此均已完成切割，所以。同理可以计算出权，这些均为算法的进行奠定了基础。我们知道待加工长方体长、宽、高分别为10、14.5、19,成品为3、2、4。因此两者各侧面的距离如下：（即6175.569算法已经成型，因此在这里我们在PASCAL平台上进行编程实现便可以得到我们想要的最优切割的排列路径为：其权为374，程序见附录。II：e=2 r=1.5的情形。从上面的分析可以看出，若还用上一个网络赋权图，显然达不到要求，因为有些边上的权是要增加的，而某些边的权即可不变。显然我们应该寻找一个新的图来进行求解。由于问题的要求，不管中间是否穿插平行切割，只要先后两次垂直切割不平行时，就要加入转刀费，即额外费用e。而这两个垂直平面切割方式只能有三种可能情况： 先切一对平行面，再切另外一对，费用增加e； 先切一个面，再切一对平行面，再切另外一个面，费用增加2e； 每切一次的面总是两两互相垂直，费用增加3e。这样的话我们可以得到一下结论：切割情况必经点(1,0,z) (2,0,z) (2,1,z)(0,1,z) (0,2,z) (1,2,z)(0,1,z) (1,1,z) (2,1,z)(1,0,z) (1,1,z) (1,2,z)(1,0,z) (1,1,z) (2,1,z)(0,1,z) （1,1,z） (1,2,z)若我们去掉(2,1,z)z=0,1,2和(1,2,z)z=0,1,2点集和与之关联的边得到新的赋权网络图如下： 赋权网络图2 赋权网络图3现在我们的问题非常明了细化，就是要从找到一条最短路径。从两者之间取小，就可以得到最优化切割方案：（源程序见附录）1： 其权为443.5。2：其权为468.5。从而我们得到问题的解答。关键词解释：I：若图G的每一条边e都对应一个实数，则称为改边的权，并称图为赋权图。II：设是赋权图G中从U到V的路径，则称=为路径P的权。III：在赋权图G中，从顶点U到顶点V具有最小权的路称为从U到V的最短路。附录：一：全体的切割情况解决方案源代码。program cut (input,output); const r=1; max=9999; 定义一个默认的最大数type mat=array1.27,1.27 of real; disttype=array1.27 of real; zuo_biao=record x,y,z:integer; end; vset=array1.27 of zuo_biao; pathtype=set of 1.27;把路径定义为一个集合var a0,b0,c0,u1,u2,u3,u4,u5,u6,ai,bi,ci,m,wm:real; da_cost:mat;相连矩阵 dist:disttype;从开始顶点到其余各点的最短路径 i,j,k,l,p,n:integer; path:array1.27 of pathtype;记录所切割的路径 s:set of 1.27; v:vset;定义的各个顶点 begin writeln(please input data which have been knowed:a0,b0,c0,u1,u2.u6); read(a0,b0,c0,u1,u2,u3,u4,u5,u6);输入一些已知量 i:=1 ;自动生成整张图的各个顶点的三维坐标，共有27个顶点 for l:=0 to 2 do for p:=0 to 2 do for n:=0 to 2 do with vi do begin vi.x:=n; vi.y:=p; vi.z:=l; i:=i+1 end; for i:=1 to 27 do以下为求解相连顶点的权值 begin for j:=1 to 27 do begin if (vi.x+vi.y+vi.z+1=vj.x+vj.y+vj.z)and(vi.x=vj.x)and(vi.y=vj.y)and(vi.z=vj.z)and(iu2 then ai:=a0-u1 else ai:=a0-u2; if vi.x=2 then ai:=a0-u1-u2; if vi.y=0 then bi:=b0; if vi.y=1 then if u3u4 then bi:=b0-u3 else bi:=b0-u4; if vi.y=2 then bi:=b0-u3-u4; if vi.z=0 then ci:=c0; if vi.z=1 then if u5u6 then ci:=c0-u5 else ci:=c0-u6; if vi.z=2 then ci:=c0-u5-u6; m:=(vj.x-vi.x)*(bi*ci)+(vj.y-vi.y)*(ai*ci)+(vj.z-vi.z)*(ai*bi)*r; da_costi,j:=m end else da_costi,j:=max如果没有直接路径的话则把其设置为默认的最大值 endend;以下我们所采用的是Diskstra的算法来求解图中的最短路径 for i:=1 to 27 do begin disti:=da_cost1,i; if distimax then pathi:=1+i else pathi:= end; s:=1;先找出开始顶点 for k:=1 to 26 do begin wm:=max; j:=1 ; for i:=1 to 27 do if not(i in s)and (distiwm) then begin j:=i; wm:=disti end; s:=s+j; for i:=1 to 27 do如果有通过其他顶点而改变权值的话则加以修改 if not(i in s )and(distj+da_costj,idisti) then begin disti:=distj+da_costj,i; pathi:=pathj+i把此顶点加入路径集合 end end; writeln(the shortest distance between 1 to 27 is); writeln(dist27);输出权值 writeln(the shortest path between 1 to 27 is); for i:=1 to 27 do if i in path27输出路径 then begin write(i);write(-) end end.调试测试的结果为：please input data which have been knowed:a0,b0,c0,u1,u2.u610 14.5 19 6 1 7 5.5 6 9the shortest distance between 1 to 27 is 3.7400000000E+02the shortest path between 1 to 27 is1-10-13-14-23-26-27二：去掉部分点集及与其相关连的边后的解决方案源代码。1：去掉（2，1 ,z）z=0,1,2:program halfcut1 (input,output);const r=1.5;此处r变为1.5 max=9999; e=2;type mat=array1.27,1.27 of real; disttype=array1.27 of real; zuo_biao=record x,y,z:integer; end; vset=array1.27 of zuo_biao; pathtype=set of 1.27;var a0,b0,c0,u1,u2,u3,u4,u5,u6,ai,bi,ci,m,wm:real; da_cost:mat; dist:disttype; i,j,k,x,y,l,p,n:integer; path:array1.27 of pathtype; s:set of 1.27; v:vset; begin writeln(please input data which have been knowed:a0,b0,c0,u1,u2.u6); read(a0,b0,c0,u1,u2,u3,u4,u5,u6); i:=1 ; for l:=0 to 2 do for p:=0 to 2 do for n:=0 to 2 do with vi do begin vi.x:=n; vi.y:=p; vi.z:=l; i:=i+1 end; for i:=1 to 27 do begin for j:=1 to 27 do begin if (vi.x+vi.y+vi.z+1=vj.x+vj.y+vj.z)and(vi.x=vj.x)and(vi.y=vj.y)and(vi.z=vj.z)and(iu2 then ai:=a0-u1 else ai:=a0-u2; if vi.x=2 then ai:=a0-u1-u2; if vi.y=0 then bi:=b0; if vi.y=1 then if u3u4 then bi:=b0-u3 else bi:=b0-u4; if vi.y=2 then bi:=b0-u3-u4; if vi.z=0 then ci:=c0; if vi.z=1 then if u5u6 then ci:=c0-u5 else ci:=c0-u6; if vi.z=2 then ci:=c0-u5-u6; m:=(vj.x-vi.x)*(bi*ci)+(vj.y-vi.y)*(ai*ci)+(vj.z-vi.z)*(ai*bi)*r; da_costi,j:=m end else da_costi,j:=max end end; 以下是重新加权的边 da_cost4,5:=da_cost4,5+e; da_cost5,8:=da_cost5,8+e; da_cost8,9:=da_cost8,9+e; da_cost13,14:=da_cost13,14+e; da_cost14,17:=da_cost14,17+e; da_cost17,18:=da_cost17,18+e; da_cost22,23:=da_cost22,23+e; da_cost23,26:=da_cost23,26+e; da_cost26,27:=da_cost26,27+e; 以下代码主要是解决去掉相关点及其与之关联的边后其相连矩阵需采取的动作 for i:=1 to 27 do if (i=6)or(i=15)or(i=24)根据顶点坐标对应的点来处理 then begin for j:=1 to 27 do da_costi,j:=max把其值设置为最大值的话就相当于无边关联 end; for y:=1 to 27 do if (y=6)or(y=15)or(y=24) then begin for x:=1 to 27 do da_costx,y:=max end; for i:=1 to 27 do begin disti:=da_cost1,i; if distimax then pathi:=1+i else pathi:= end; s:=1; for k:=1 to 26 do begin wm:=max; j:=1 ; for i:=1 to 27 do if not(i in s)and (distiwm) then begin j:=i; wm:=disti end; s:=s+j; for i:=1 to 27 do if not(i in s )and(distj+da_costj,idisti) then begin disti:=distj+da_costj,i; pathi:=pathj+i end end; writeln(the shortest distance between 1 to 27 is); writeln(dist27); writeln(the shortest path between 1 to 27 is); for i:=1 to 27 do if i in path27 then begin write(i);write(-) end end.调试测试的结果为：please input data which have been knowed:a0,b0,c0,u1,u2.u610 14.5 19 6 1 7 5.5 6 9the shortest distance between 1 to 27 is 4.4350000000E+02the shortest path between 1 to 27 is1-4-13-14-17-26-272：同理我们可以得到去掉（1，2，z）z=0,1,2的源代码：program halfcut2 (input,output);const r=1.5; max=9999; e=2;type mat=array1.27,1.27 of real; disttype=array1.27 of real; zuo_biao=record x,y,z:integer; end; vset=array1.27 of zuo_biao; pathtype=set of 1.27;var a0,b0,c0,u1,u2,u3,u4,u5,u6,ai,bi,ci,m,wm:real; da_cost:mat; dist:disttype; i,j,k,x,y,l,p,n:integer; path:array1.27 of pathtype; s:set of 1.27; v:vset; begin writeln(please input data which have been knowed:a0,b0,c0,u1,u2.u6); read(a0,b0,c0,u1,u2,u3,u4,u5,u6); i:=1 ; for l:=0 to 2 do for p:=0 to 2 do for n:=0 to 2 do with vi do begin vi.x:=n; vi.y:=p; vi.z:=l; i:=i+1 end; for i:=1 to 27 do begin for j:=1 to 27 do begin if (vi.x+vi.y+vi.z+1=vj.x+vj.y+vj.z)and(vi.x=vj.x)and(vi.y=vj.y)and(vi.z=vj.z)and(iu2 then ai:=a0-u1 else ai:=a0-u2; if vi.x=2 then ai:=a0-u1-u2; if vi.y=0 then bi:=b0; if vi.y=1 then if u3u4 then bi:=b0-u3 else bi:=b0-u4; if vi.y=2 then bi:=b0-u3-u4; if vi.z=0 then ci:=c0; if vi.z=1 then if u5u6 then ci:=c0-u5 else ci:=c0-u6; if vi.z=2 then ci:=c0-u5-u6; m:=(vj.x-vi.x)*(bi*ci)+(vj.y-vi.y)*(ai*ci)+(vj.z-vi.z)*(ai*bi)*r; da_costi,j:=m end else da_costi,j:=max end end;da_cost2,5:=da_cost2,5+e; da_cost5,6:=da_cost5,6+e; da_cost6,9:=da_cost6,9+e; da_cost11,14:=da_cost11,14+e; da_cost14,15:=da_cost14,15+e; da_cost15,18:=da_cost15,18+e; da_cost20,23:=da_cost20,23+e; da_cost23,24:=da_cost23,24+e; da_cost24,27:=da_cost24,27+e;for i:=1 to 27 do if (i=8)or(i=17)or(i=26)根据去掉顶点的坐标来确定的点 then begi