java - 流水线排程递归解决错误

Question

基本上，我是根据提供的公式以递归方式解决装配线调度问题 here

可以从问题陈述中提取以下信息以使其更简单:

两条装配线，1 和 2，每条装配线的工位从 1 到 n。

一辆汽车底盘必须按顺序通过从 1 到 n 的所有工位(在两条装配线中的任何一条)。也就是说，如果它们不在一个移动距离内，它就不能从第 i 站跳到第 j 站。

汽车底盘可以在同一条线上向前移动一站，也可以在另一条线上斜向移动一站。从线路 i 移动到站点 j 会产生额外的成本 ti, j。同线移动不产生费用。

第i 站j 站所用时间为ai,j。

Si,j 表示 i 号线上的第 j 站。

将问题分解成更小的子问题: 如果已知第 (i-1) 个阶乘，我们可以很容易地找到第 i 个阶乘。我们可以在这里应用类似的基础吗？ 如果底盘离开站点Si,j-1的最短时间已知，结合ai,j和ti,j可以快速计算出离开站点Si,j的最短时间。

T1(j)表示汽车底盘离开装配线1站j所用的最短时间。

T2(j) 表示汽车底盘在装配线 2 上离开工位 j 所用的最短时间。

基本情况: 只有当汽车底盘进入汽车工厂时，进入时间ei才会出现。

离开 1 号线第一个车站所需的时间由下式给出: T1(1) = 1 号线进入时间 + 在 S1,1 站停留的时间 T1(1) = e1 + a1,1 类似地，离开 2 号线第一个车站所需的时间由下式给出: T2(1) = e2 + a2,1

递归关系: 如果我们看一下问题陈述，它很快就会归结为以下观察结果: S1,j站的汽车底盘可以来自S1,j-1站或S2,j-1站。

案例 #1:它的前一站是 S1，j-1 离开站点 S1,j 的最短时间由下式给出: T1(j) = 离开站点 S1 所用的最短时间，j-1 + 在站点 S1 所花费的时间，j T1(j) = T1(j-1) + a1, j

案例 #2:它的前一站是 S2，j-1 离开站点 S1, j 的最短时间由下式给出: T1(j) = 离开站点 S2, j-1 的最短时间 + 更换装配线所产生的额外成本 + 在站点 S1, j 花费的时间 T1(j) = T2(j-1) + t2, j + a1, j

最小时间 T1(j) 由案例 #1 和 #2 中获得的两个中的最小值给出。 T1(j) = min((T1(j-1) + a1, j), (T2(j-1) + t2, j + a1, j)) 类似地，到达站点 S2, j 的最短时间由下式给出: T2(j) = min((T2(j-1) + a2, j), (T1(j-1) + t1, j + a2, j))

汽车底盘出厂的最短总时间由下式给出: Tmin = min(离开车站Si,n所用时间+离开汽车厂所用时间) Tmin = min(T1(n) + x1, T2(n) + x2)

动态规划版本很好，但是我的递归版本有一些隐藏的错误，有人能帮我找出错误吗？ 谢谢。

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(carAssemblyDP(a, t, e, x));
        System.out.println(carAssembly(a, t, e, x));
    }

    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 = 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]);
        int 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);
    }

    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]);
    }
}

DP输出的是35，是正确的，但是递归版本输出的是29，显然是错误的。

Answer 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;  
    int T1 = Integer.MAX_VALUE;  
    if(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){       
        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);  
}