2. 计算机
  3. 阅读以下说明和图，填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和

阅读以下说明和图，填补流程图中的空缺。 【说明】 某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。 (1)e0和e1表示底盘分别进入装配线0和

admin2008-04-04  75
问题 阅读以下说明和图，填补流程图中的空缺。
【说明】
   某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。
        
   (1)e0和e1表示底盘分别进入装配线0和装配线1所需要的时间。
   (2)每条装配线有n个工位，第一条装配线的工位为S0,0，S0,1，…，S0,n-0，第二条装配线的工位为S1,0，S1,1，…，S1,n-1。其中S0,k和S1,k(0≤k≤n-1)完成相同的任务，但所需时间可能不同。
   (3)aij表示在工位Sij处的装配时间，其中i表示装配线(i=0或i=1)，j表示工位号(0≤j≤n-1)。
   (4)tij表示从Sij处装配完成后转移到另一条装配线下一个工位的时间。
   (5)X0和X1表示装配结束后，汽车分别从装配线0和装配线1下线所需要的时间。
   (6)在同一条装配线上，底盘从一个工位转移到其下一个工位的时间可以忽略不计。
   图10-7所示的流程图描述了求最短装配时间的算法，该算法的输入为；
   n：        表示装配线上的工位数；
   e：     表示e1和e2，i取值为0或1：
   a[j]：  表示ai,j，i的取值为0或1，j的取值范围为0～n-1；
   t[j]：  表示ti,j，i的取值为0或1，j的取值范围为0～n-1；
   x：     表示X0和X1，i取值为0或1。
   算法的输出为：
   fi：最短的装配时间；
   li：获得最短装配时间的下线装配线号(0或者1)。
   算法中使用的f[j]表示从开始点到Si,j处的最短装配时间。
   
选项
答案(1)f[0][0]=e[0]+a[0][0] f[1][0]=e[1]+a[1][0] (2)f[0][j-1]+a[0][j] (3)f[j][j-1)+a[1][j]＜f[0][j-1)+t[0][j-1]+a[1][j]， 或f[1][j-1)+a[1][j]＜=f[0][j-1]+t[0][j-1)+a[1][j]， 或其等价形式 (4)fi=f[0][n-1]+x[0] li=0 (5)fi=f[1][n-1]+x[1] 1i=1
解析 本题考查动态规划算法设计方法。
   当问题具有两个特性，即最优子结构和重叠子问题时，可以考虑用动态规划求解问题。用动态规划求解问题具有四个步骤。
   (1)刻画问题的最优子结构，描述问题的最优解包含子问题的最优解。对于本题来说，最短装配时间等于经过装配线。的第n个工位的最短装配时间加上x[0]，或者等于经过装配线1的第n个工位的最短装配时间加上x[1]，取哪条装配线取决于哪个值更小。而经过某个装配线0/1的第i个工位的最短装配时间又等于经过装配线0/1的第1-1个工位的最短装配时间，或者等于经过装配线I/0的第i-1个工位的最短装配时间加上从这个工位到装配线0/1的迁移时间，取决于哪个值更小。
   (2)建立最优子结构的递归关系，这是非常关键的一步。对于本题来说，递归关系为
   
   (3)根据递归关系求最优解的值。对于本题来说，最优解记录在fi中，fi= min(f(0，n-1)+x0,f(1，n-1)+x1)：
   (4)构造最优解。对于本题来说，只是求出最优解是从哪条装配线装配出来，并没有记录最优解。
转载请注明原文地址:https://kaotiyun.com/show/ufDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)