v25 v10 图1G(V,E) 为简单起见先考虑e=0的情况构造如图的一个有向赋权网络图G(V,E.为 了表示切割过程的有向性,在网络图上加上坐标轴x,y,,图G(,E)含义为 (1)空间网络图中每个结点 Vi(xi, yi表示被切割石材所处的一个状态顶点 坐标x、yt份别代表石材在左右、前后、上下方向上已被切割的刀数例如 V24(2,1,2)表示石材在左右方向上已被切割两刀,前后方向上已被切一刀,上下 方向上已被切两刀,即面M、M、M、M5、M6均已被切割顶点v1(0,0,0)表 示石材的最初待加工状态,顶点V27(2,2,2)表示石材加工完成后的状态 次切割变为状态v,即当且仅当x计y1=xj+yj计z时,Ⅴi( XI,yI, ZI)到vj 有弧(vvj),相应弧上的权W(i,Vj即为这一切割过程的费用 wvi,vj)(xj-xj)×(bi×ci)+(yjyi)×(ai×ci)+(zzi)×( aix bi)×r 其中,ai、bi、cif分别代表在状态V时,长方体的左右面、上下面、前后面 之间的距离 例如,状态V5(1,1,0),a5=a0-u1,b5=b0-u3,c5=00状态v6(2,1,0) W(5,V6)=(b0-u3)×c0 63根据准则知第一刀有三种选择,即第一刀应切M1、M3、M5中的某个 面,在图中分别对应的弧为(V1,V2),(1,v4),(1,v10,.图G中从Ⅵ1到V27的 任意一条有向道路代表一种切割方式从v1到V27共有90条有向道路,对应着所 考虑的90种切割方式V1到27的最短路即为最少加工费用,该有向道路即对应 所求的最优切割方式图1 G(V,E) 为简单起见,先考虑e=0 的情况.构造如图的一个有向赋权网络图G(V,E).为 了表示切割过程的有向性，在网络图上加上坐标轴 x，y，z，图G(V,E)的含义为： (1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点 坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数.例如： V24(2,1,2) 表示石材在左右方向上已被切割两刀，前后方向上已被切一刀，上下 方向上已被切两刀，即面M1、M2、M3、M5、M6均已被切割.顶点V1(0,0,0) 表 示石材的最初待加工状态，顶点V27(2,2,2)表示石材加工完成后的状态. (2)G的弧（Vi,Vj）表示石材被切割的一个过程，若长方体能从状态Vi经一 次切割变为状态Vj，即当且仅当xi+yi+zi+1=xj+yj+zj时，Vi(xi,yi,zi)到Vj(xj,yj,zj) 有弧(Vi,Vj)，相应弧上的权W(Vi,Vj)即为这一切割过程的费用. W(Vi,Vj)=(xj-xi)  (bi  ci)+(yj-yi)  (ai  ci)+(zj-zi)  (ai  bi)  r 其中，ai、bi、ci分别代表在状态Vi时，长方体的左右面、上下面、前后面 之间的距离. 例如，状态V5（1，1，0），a5 = a0-u1,b5 = b0-u3,c5 = c0;状态V6（2，1，0） W(V5，V6) ＝（b0-u3)  c0 (3)根据准则知第一刀有三种选择， 即第一刀应切M1、M3、M5中的某个 面，在图中分别对应的弧为( V1,V2)，(V1,V4)，(V1,V10). 图G中从V1到V27的 任意一条有向道路代表一种切割方式.从V1到V27共有90条有向道路，对应着所 考虑的90种切割方式.V1到V27的最短路即为最少加工费用，该有向道路即对应 所求的最优切割方式