一、问题描述
加工顺序2.png
二、解决思路
因为要先机器1加工然后是机器2加工，所以问题的选择也就是机器1加工的零件的选择问题。定义问题的解空间。也就是机器1第一、第二、第三等加工的选择问题。限界函数则是当前节点选择的只能是未加工的零件中选择。因为是求解最优值，所以是有剪枝函数的，剪枝函数则是判断当前的值是否已经大于最优值。
加工顺序.png
三、代码
public class BestMachiningOrder {
public static void main(String[] args) {
// 使用两个数组代表零件在两台机器上的加工时间
int[] workTime3 = new int[]{5, 1, 8, 5, 3, 4};
int[] workTime4 = new int[]{7, 2, 2, 4, 7, 4};
int[] partStatus2 = new int[]{0, 1, 2, 3, 4, 5};
int[] bestValueStatus2 = new int[]{0, 1, 2, 3, 4, 5};
System.out.println(calc(workTime3, workTime4, 0, 0, 0, Integer.MAX_VALUE, partStatus2, bestValueStatus2));
System.out.println(Arrays.toString(bestValueStatus2));
}
/**
* 进行回溯计算
*
* @param workTime1 工作时间1
* @param workTime2 工作时间2
* @param i 当前的节点索引
* @param f1 机器1所需的时间
* @param f2 机器2所需的时间
* @param bestValue 当前值的最优解
* @param partStatus 记录当前零件的选择状态 划分为两个区间，中间点为i 前面的是已经加工的零件的下表存储，后面是还没有进行加工的零件的下标
*/
public static int calc(int[] workTime1, int[] workTime2, int i, int f1, int f2, int bestValue, int[] partStatus, int[] bestValueStatus) {
//进行终点的收集 到达叶子节点代表找到了新的最优值 partStatus记录的加工的顺序
//这里可以进行变种求解所有的加工结果，将剪枝函数去掉，在这里记录结果即可
if (i > workTime1.length - 1) {
bestValue = f2;
for (int j = 0; j < workTime1.length; j++) {
bestValueStatus[j] = partStatus[j];
}
return bestValue;
}
//从i开始搜索，还有length-i个零件还未加工 在未加工区间进行搜寻
for (int j = i; j < workTime1.length; j++) {
//f1 所需的时间直接累加
f1 = f1 + workTime1[partStatus[j]];
//回溯回来的时候使用
int temp = f2;
//机器2所需的时间应该从时间线最大值开始计算
f2 = Math.max(f1 + workTime2[partStatus[j]], f2 + workTime2[partStatus[j]]);
//减枝函数判断 f2 小于当前的最优值才继续进行递归否则结束，回溯进行下条路的判断
if (f2 <= bestValue) {
// 交换j 与i 在partStatus当中的状态,将j交换到已加工区间，这里还有其他的方式，比如数组+标记方式
swap(partStatus, j, i);
bestValue = calc(workTime1, workTime2, i + 1, f1, f2, bestValue, partStatus, bestValueStatus);
//回溯结束 节点状态回退
swap(partStatus, j, i);
}
//将时间回溯
f1 = f1 - workTime1[partStatus[j]];
f2 = temp;
}
return bestValue;
}
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
