Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(7)

本周更新的动态规划问题是装配线问题(Assembly Line Balancing (ASMBAL))。装配线问题没记错的话应该是算导中的动态规划的第一题,具体描述大概是:一件产品从生产到出品要经历一系列过程,其中每个步骤都会有成本开销,而这些过程在流转(也就是说步骤转换)过程也有成本损失,如何平衡选择,可以最小化产品的出品成本。

算导的原题:

      某汽车工厂有2个装配线,每个装配线有n 个装配站(按顺序编号1~n )标记为Si,j,表示第i个装配线的第j个装配站,两个装配线的对应的装配站执行相同的功能,但所用的时间可能不同。经过第i条流水线(i=1,2)的第j 个装配站所花的时间为a[i][j]。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略,而移到另外一个流水线的下一个装配站则需要一定的时间t[i][j]。汽车进入流水线需要花时间,进入装配线1需要时间e[1],进入装配线2需要时间e[2];  汽车出流水线时需要花时间,出装配线1需要时间x[1],出装配线2需要时间x[2] 。汽车的装配需要按顺序经过所有装配站。
  现在已知装配时间a[i][j] 、转移时间t[i][j]、进入装配线的时间e[i]、出装配线的时间x[i],要求输出装配一辆汽车所需要的最短时间,以及经过的装配站。 

      对于这个问题,可以将其与之前所解的有向无环图对比,非常类似,不同的是这个在计算转移成本的时候,不仅需要算路径(也就是转移的成本),还要叠加节点本身的生产成本。以具体为例,装配线有14个装配站,其中0号和13号分别是起点和终点,而剩余12个站平均分配在两条流水线上,具体各计算成本如下图:

image

其中节点权重为v=[0,7,8,9,5,3,6,4,4,8,5,4,7,0],即代表装配时间,而转移时间表示为矩阵形式:

image

因为已经将过程打上了stage的标签,我们定义一个状态为(k,i),表示在第k个阶段的第i条装配线上,那么转移时间就表示为(k,i)->(k+1,j)的一个成本c(k,i,j)。当然由题图可见在同线转移时是没有成本的即c(i,k,k)=0。具体的,定义总成本R(k,i,j)=v(k,i)+c(k,i,j),其中v(k,i)即i装配线的编号为k的节点权重。定义f(k,i)为状态值,即在k阶段时的i装配线到出产时的总成本,那么DPFE为:f(k,i)=min j{R(k,i,j)+f(k+1,j)}。f(N+1,0)=0是初始条件,表示在最后一个节点时的成本,那么往前递推,f(0,0)作为在起点处的成本就是目标函数,于是f(0,0)=(0+2)+(7+2)+(5+1)+(3+1)+(4+0)+(5+1)+(4+3)=38.

解题程序:

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:  
  18: public class ASMBAL {
  19:  
  20:     private static int[][] cost = // (stage,line)
  21:     { 
  22:             { 2, 4 }, // to next line
  23:             { 2, 2 }, { 1, 3 }, { 2, 1 }, { 2, 3 }, { 1, 4 }, // to next line
  24:             { 3, 2 } // from line
  25:     };
  26:     private static int[][] vertexcost = // (stage,line)
  27:     { 
  28:         { 0, 0 }, { 7, 8 }, { 9, 5 }, { 3, 6 }, { 4, 4 }, { 8, 5 }, { 4, 7 } 
  29:     };
  30:     private static int N = vertexcost.length - 1;
  31:  
  32:     private static int arccost(int g, int x, int d) {
  33:         if (g == 0)
  34:             return cost[g][d]; // to next line d
  35:         else if (g == N)
  36:             return cost[g][x]; // from line x
  37:         else if (x == d)
  38:             return 0; // stay same line
  39:         else
  40:             return cost[g][d]; // to next line d
  41:     }
  42:     
  43:     public static double f(int g, int x) {
  44:         if (g > N)
  45:             return 0.0;
  46:         double min = Double.MAX_VALUE;
  47:         for (int d = 0; d <= 1; d++) {
  48:             double c = vertexcost[g][x] + arccost(g, x, d) + f(g + 1, d);
  49:             if (c < min)
  50:                 min = c;
  51:         }
  52:         return min;
  53:     }
  54:     /**
  55:      * @param args
  56:      */
  57:     public static void main(String[] args) {
  58:         System.out.println(f(0,0));
  59:     }
  60:  
  61: }

posted on 2014-04-21 13:25 changedi 阅读(1205) 评论(1)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(7) 2014-04-23 14:40 无添加

还是看不懂啊。。。  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: