動態規劃經典：流水線調度問題詳解與 Java 實現

問題背景

流水線調度問題 是動態規劃的教科書級案例。場景為：汽車工廠有兩條裝配線，每條線上有 n 個工位。車身必須按順序經過所有工位，可在同一線前進，也可斜向轉移到另一條線（需付出轉移時間 t[i][j]）。每條線有進廠時間 e[i] 和出廠時間 x[i]。目標是求構建一輛車身的最短總時間。

問題建模與狀態定義

定義兩個核心狀態：

• T1(j)：車身離開第 1 裝配線第 j 工位的最早時間。
• T2(j)：車身離開第 2 裝配線第 j 工位的最早時間。

遞推關係推導

車身到達工位 S1,j 只有兩條路徑：

1. 來自同線上一工位： T1(j-1) + a[1][j]
2. 來自另一條線上一工位（含轉移時間）： T2(j-1) + t[2][j] + a[1][j]

取較小者即為 T1(j)。同理可得 T2(j)。

T1(j) = min( T1(j-1) + a[1][j],  T2(j-1) + t[2][j] + a[1][j] )
T2(j) = min( T2(j-1) + a[2][j],  T1(j-1) + t[1][j] + a[2][j] )

邊界條件與最終答案

• 初始工位：T1(1) = e[1] + a[1][1]，T2(1) = e[2] + a[2][1]
• 最終最短時間：min( T1(n) + x[1], T2(n) + x[2] )

為何用動態規劃？

問題存在重疊子問題與最優子結構。計算 T1(j) 需要 T1(j-1) 和 T2(j-1)，這些值會被重複使用。自底向上填表可將指數級遞歸優化為 O(n) 時間、O(n) 空間（甚至可優化至 O(1) 空間）。

Java 完整實現（含遞歸對比）

代碼包含三種版本：遞歸（含修正版）、動態規劃（DP）、路徑打印練習。

package DP;

public class AssemblyLineScheduling {
    public static void main(String[] args) {
        int[][] a = {{4, 5, 3, 2}, {2, 10, 1, 4}};
        int[][] t = {{0, 7, 4, 5}, {0, 9, 2, 8}};
        int[] e = {10, 12};
        int[] x = {18, 7};

        System.out.println("DP Result: " + carAssemblyDP(a, t, e, x)); // 35
        System.out.println("Recursive Result: " + carAssembly(a, t, e, x));
    }

    // 1. 遞歸版（修正後：增加 line 參數限制）
    public static int carAssembly(int[][] a, int[][] t, int[] e, int[] x) {
        int n = a[0].length - 1;
        return Math.min(
            carAssemblyRec(a, t, e, x, n, 0) + x[0],
            carAssemblyRec(a, t, e, x, n, 1) + x[1]
        );
    }

    public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line) {
        if (n == 0) return e[line] + a[line][0];

        int T0 = Integer.MAX_VALUE, T1 = Integer.MAX_VALUE;
        if (line == 0) { // 僅計算 line 0 的轉移
            T0 = Math.min(
                carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],
                carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]
            );
        } else if (line == 1) { // 僅計算 line 1 的轉移
            T1 = Math.min(
                carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],
                carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]
            );
        }
        return Math.min(T0, T1);
    }

    // 2. 動態規劃版（底向上，O(n) 時間 O(n) 空間）
    public static int carAssemblyDP(int[][] a, int[][] t, int[] e, int[] x) {
        int n = a[0].length;
        int[] T1 = new int[n];
        int[] T2 = new int[n];

        T1[0] = e[0] + a[0][0];
        T2[0] = e[1] + a[1][0];

        for (int i = 1; i < n; i++) {
            T1[i] = Math.min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
            T2[i] = Math.min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
        }
        return Math.min(T1[n-1] + x[0], T2[n-1] + x[1]);
    }
}

遞歸版的關鍵坑點

初寫遞歸時易犯錯：在 carAssemblyRec 中同時計算 T0 和 T1 並取 min，這會導致錯誤地混合兩條線的狀態。正確做法是根據傳入的 line 參數，只計算該線路的兩種來源，另一條線設置為 MAX_VALUE 不參與比較。這是理解「狀態定義精確性」的絕佳教訓。