參考文獻

實驗問題描述

一個汽車公司在有2條裝配線的工廠內(nèi)生產(chǎn)汽車，每條裝配線有n個裝配站，不同裝配線上對應(yīng)的裝配站執(zhí)行的功能相同，但是每個站執(zhí)行的時間是不同的。在裝配汽車時，為了提高速度，可以在這兩天裝配線上的裝配站中做出選擇，即可以將部分完成的汽車在任何裝配站上從一條裝配線移到另一條裝配線上。裝配過程如下圖所示：

裝配線問題

我們對這張圖來分析一下

裝配過程的時間包括：進入裝配線時間e、每裝配線上各個裝配站執(zhí)行時間a、從一條裝配線移到另外一條裝配線的時間t、離開最后一個裝配站時間x。舉個例子來說明，現(xiàn)在有2條裝配線，每條裝配線上有6個裝配站，各個時間如下圖所示：

實驗解題步驟

(1)描述通過工廠的最快結(jié)構(gòu)

• 如果我們需要找到經(jīng)過S(i, j)的最短路徑其實我們需要先知道S(1, j-1)和S(2, j-1)的最優(yōu)解(一個問題的最優(yōu)解包含了最優(yōu)子結(jié)構(gòu)的一個最優(yōu)解)
  • 通過裝配線S1,j-1的最快線路，然后直接通過裝配站Si,j
  • 通過裝配站S2,j-1的最快線路，從裝配線2移動到裝配線1，然后通過裝配線S1,j。

(2)一個遞歸的解

• 最終目標是確定工件通過工廠的所有路徑的最快時間，所以我們假設(shè)這個變量是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īng)過當(dāng)前節(jié)點的時間
  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]) //包括經(jīng)過當(dāng)前節(jié)點的時間

(3)計算最快時間

用C語言來實現(xiàn)這個算法

//核心代碼在這個地方
//由于編程語言是從0開始計數(shù)的
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)
 
}