最小费用切割策略.pdf

第28卷第1期数学的实践与认识Vol.28 No.11998年1月MATHEMATICS IN PRACTICE AND THEORYJan,1998最小费用切割策略崔龙龚玉萍汪霖指导教师：王开华(南京通信工程学院，南京210016)编者按本文在目标函数表达式、优化准则、启发式算法等方面都有清晰的叙述和讨论，衡要本文对于寻求费用最小的切割方式这一有限状态的离散问题，建立了优化棋型，通过对该模型的讨论与求解，解决了问题一至五。首先，对于问题一，运用给出的平行相邻等效定理，求得了箭考虑的不同切割方式的总数为4？6。其次，本文建立了寻求费用最小切制方式的优化模型，在该模的求解中：(1)用穷举法得到了所有费用最小的切割方式，(2)给出并证明了平行切割厚者优先定理。缩小了鞭索范瑟，()引入并改进了人工智能领扩的算法，求得全都费用最小的切割时式，对三种不同的启发函数进行了讨论、比较.然，对=心的青祝下华出了等效厚度厚者优先切割准测，同时文中还讨论该准则在0时的适用性，此外对原题问题三所提出的准测从两个方面进行了评价，并给出了问题五所要求的费用最小的所有切割方式，最后，通过变换，将结论的应用范围推广到一般平行六面体的切制问题。一、建模准备基本假设(但1)每切割一刀后，将待加工的部分留在工作台上，各个面的位置关系保持不变，而将被切割下的部分取走，不予考虑(H2)加工费用为切割费用和调整刀具的费用之和，其它的费用（如刀具磨损费等），本文不作讨论(任3)刀具在水平切割与垂直切割之间进行转换时，刀具的调整不需要额外费用；但当先后两次垂直切割的平面不平行时，不管它们之间是否穿插水平切割，调鉴刀具均需要额外费用。以下讨论的调鉴刀具特指垂直方向间的调整。题意澄清(1)“与水平工作台接触的长方体底面是事先指定的，其含义是$先固定长方体在水平工作台上的放置方式，相应地确定了水平切割面和垂直切割面.(2)建立如图一的直角坐标系来明确待切.割长方体和成品长方体各个面的空间位置关系.图中0(0,0,0，L(a1,b1,c1)为待加工长方体的体对角线的两顶点坐标，图】待切割长方体和成品长方体位置图O(as,b,ca),L(a2,b2,c)为成品长方体的体对角线的两顶点坐标.为了表述方便，我们将待加工的长方体和成品长方体各个面进行编号，其对应关系如下：1(1)，2(2)，3(3),4(4),5(5),6(6)分别表示待加工的长方体和成品长方体的右侧面、背面、上底面、左侧面、正面、下底面.符号说明1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/74数学的实践与认识28卷类似地我们定义在图五的代价树中的加工费用估计函数：f（Siw）=g(S,）+h(Sw)其中f(5:)为根结点S。经过结点S5到达叶结点5。，的最小费用路径的费用估计值，g()是从根结点50经过结点5时的实际费用，(S)是从结点5到达叶结点S6,的最小费用路径的估计费用，它同样体现了搜家的启发信息，也称启发式函数.记(5)为从结点S,5到达叶结点5。，k的最小费用.当(S,)满足许可性条件时，A*算法一定能搜索到从结点S。到达叶结点56，.的最小费用2.启发式函数h(5则)的选择下面我们具体构造出三种(S5)的表达式：(1):(5,5)三0，这种特殊的情况完全缺乏有关的启发信息，算法退化为宽度优先搜素法(2),(S:)=2-1;式中2表示第：次切割将在待加工长方体上形成的截断面的面积，1表示成品长方体与该截断面重叠部分的面积，(3)(5)=o2-1+；式中o4为第：次切割前成品长方体尚来被切割到的各个面共7一i个)面积之和。此时有n(5)Sh(Sid)h(S,)h*(S)针对原问题我们应用A算法：引，入0PEN表及CL0sE表端程计算，其具体的步骤附录略).当搜索结束后CLOSE老结京数目就是算法执行过程中旗过的帝点数目，是算法效率的体现，我们尚三神不同的启发式函数：h()代入A算法，并将，(S,),h2(S),(S,)时的A算法分别记Ai,A:4；,计算终止后CLOSE表中结点数列于表一：表1三种搜索算法结東时CL0SE表结点数目表h(S,)ACL0SE表的结点数h:(S:5）A119h2(S13)A19ha(Si5）A;15由表可见上述三种启发式函数h(S,)越来越趋近于(5，也即含有的启发信息依次增加，从而使得搜索结束后CLOSE表结点数目依次减少，搜索的效率越来越高，此结果与算法的性质十分吻合由此我们建议采用启发式函数(55)=o+1,这样可使得搜索的效率大大提高。(三)改进理A算法1.改进方案A”算法的效率虽然很高，但它还存在以下两点明显的不足之处：(1)搜索的空间还可以进一步的压缩，(2)A算法只能得到一个最优解，不能得到全部的最优解。我们对A算法进行改进如下：首先，将平行切割厚度优先原则应用于A算法；其次，在判断算法结束时，并不是找到OPEN表中第一个最优解（对应的最优值为“(5，就结束搜索，而是继续对那些(S)值与(S)相同的结点，再进行扩展、判断，直到达到最低层，这样就搜索到了全部的最优路径.改进后的A”算法称为改进型A算法2.改进型A算法的检验固定点(a1,b1,c),变动点(a2,b2,c2),(aa,ba,c)中的-个，且仅沿三维坐标轴的一个变动，分别用改进型A1,4防，A:算法计算，从而可以评价和检验算法的效率、稳定性，并讨论当成品长方体的边长变化（即成品长方体越来越接近于待加工的长方体时）对A,4;,A;的效率的影响。初始条件分别取：(1)r=1,e=0,(a1,b1,c1=(10,14.5,19),(as,b3,cs）=(2,7,9)(2)r=1,e=0,(a1,b1c1)=(10,14.5,19),(a2,b2,c)=(7,10,15)具体表格、数据及分析结论略。1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/