算法课 实验6

参考文献

---

实验问题描述

一个汽车公司在有2条装配线的工厂内生产汽车，每条装配线有n个装配站，不同装配线上对应的装配站执行的功能相同，但是每个站执行的时间是不同的。在装配汽车时，为了提高速度，可以在这两天装配线上的装配站中做出选择，即可以将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。装配过程如下图所示：

装配线问题

我们对这张图来分析一下

装配过程的时间包括：进入装配线时间e、每装配线上各个装配站执行时间a、从一条装配线移到另外一条装配线的时间t、离开最后一个装配站时间x。举个例子来说明，现在有2条装配线，每条装配线上有6个装配站，各个时间如下图所示：

实验解题步骤

(1)描述通过工厂的最快结构

• 如果我们需要找到经过S(i, j)的最短路径其实我们需要先知道S(1, j-1)和S(2, j-1)的最优解(一个问题的最优解包含了最优子结构的一个最优解)
  • 通过装配线S1,j-1的最快线路，然后直接通过装配站Si,j
  • 通过装配站S2,j-1的最快线路，从装配线2移动到装配线1，然后通过装配线S1,j。

(2)一个递归的解

• 最终目标是确定工件通过工厂的所有路径的最快时间，所以我们假设这个变量是f*，令fi[j]表示的是工件从起点到达S(i,j)的最快的时间。及f* = min(f1[n]+x1,f2[n]+x2)
  j = 1时：f1[1] = e1+a1[1],f2[1] = e2+a2[1] //包括经过当前节点的时间
  j > 1是：f1[j] = min(f1[j-1]+a1[j]，f2[j-1]+t2[j-1]+a1[j])，f2[j] = min(f2[j-1]+a2[j]，f1[j-1]+t1[j-1]+a2[j]) //包括经过当前节点的时间

(3)计算最快时间

用C语言来实现这个算法

//核心代码在这个地方
//由于编程语言是从0开始计数的
void fastest_way (int aNode[][N], int tNode[][N-1], fastWay[][N-1], int eNode[][], ){
  int i, j;
  fastWay[0][0] = e[0] + a[0][0];
  f[1][0] = e[1] + a[0][1];
  l[0][0] = 1;
  l[1][0] = 2;
  if (fastWay[0][j-1] < fastWay[1][j-1] + tNode[1][j-1]) {
    fastWay[0][j] = fastWay[0][j-1] + aNode[0][j];
    l[0][j] = 1;
  }
  else {
    fastWay[0][j] = fastWay[1][j-1] + tNode[1][j-1]+ aNode[0][j];
    l[0][j] = 2
  }
  //上面一段可以写成 fastWay[0][j] = Math.min(fastWay[0][j-1], fastWay[1][j-1] + tNode[1][j-1]) + aNode[0][j]
  if(fastWay[1][j-1] < fastWay[0][j-1] + tNode[0][j-1])
     {
         fastWay[1][j] = fastWay[1][j-1] + aNode[1][j];
         l[1][j] = 2;
     }
    else
     {
         fastWay[1][j] = fastWay[0][j-1] + tNode[0][j-1] + aNode[1][j];
         l[1][j] = 1;
     }
    //这一段也可以写成 fastWay[1][j] = Math.min(fastWay[0][j-1] + tNode[0][j-1], fastWay[1][j-1]) + aNode[1][j]，同时通过?:三元符号可以对l指针对象进行赋值
//最终条件，临界条件
if(fastWay[0][n-1] + xNode[0] < fastWay[1][n-1] + xNode[1])
     {
         last_f = fastWay[0][n-1] + xNode[0];
         last_l = 1;
     }
     else
     {
         last_f = fastWay[1][n-1] + xNode[1];
         last_l = 2;
     }
//这样写更加好 Go\Python last_f, last_l = (fastWay[0][n-1] + xNode[0] < fastWay[1][n-1] + xNode[1]) ? (fastWay[0][n - 1] + xNode[0], 1):(fastWay[1][n-1]+xNode[1], 2)
 
}