工作分配问题（回溯法）

92 阅读 0 评论 61 点赞

我是靠谱客的博主幸福店员，最近开发中收集的这篇文章主要介绍工作分配问题（回溯法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

工作分配问题
设有n件工作要分配给n个人去完成，将工作i分配给第j个人所需费用为。试设计一个算法，为每个人分配1件不同的工作，并使总费用达到最小。

package ustc.test;
import java.util.Scanner;
public class distribution {
static int n = 0;
static int cost = 0;
static int[] x = new int[100];
static int[][] c = new int[100][100];
public static void main(String[] args){
System.out.println("设置工作（人数）：");
Scanner in = new Scanner(System.in);
n = in.nextInt();
System.out.println("设置费用：");
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
c[i][j] = in.nextInt();
x[j] = 0;
}
cost += c[i][i];
}
work(1, 0);
System.out.println("费用最小为：" + cost);
}
//
public static void work(int i, int count){
if(i > n && count < cost ){
cost = count;
return ;
}
if(count < cost){
for(int j = 1; j <= n; j++){
if(x[j] == 0){
x[j] = 1;
work(i + 1, count + c[i][j]);
x[j] = 0;
}
}
}
}
}

由于每个人都必须分配到工作，在这里可以建一个二维数组c[i][j]，用以表示i号工人完成j号工作所需的费用。给定一个循环，从第1个工人开始循环分配工作，直到所有工人都分配到。为第i个工人分配工作时，再循环检查每个工作是否已被分配，没有则分配给i号工人，否则检查下一个工作。可以用一个一维数组x[j]来表示第j 号工作是否被分配，未分配则x[j]=0，否则x[j]=1。利用回溯思想，在工人循环结束后回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配为止。这样，一直回溯到第1个工人后，就能得到所有的可行解。在检查工作分配时，其实就是判断取得可行解时的二维数组的一下标都不相同，二下标同样不相同。

样例分析：
给定3件工作，i号工人完成j号工作的费用如下：
10 2 3
2 3 4
3 4 5
那么在这里，用回溯法的思想就是，首先分配的工作是：
10:c[1][1] 3:c[2][2] 5:c[3][3] count=18;

此时，所有工人分配结束，然后回溯到第2个工人重新分配：

10:c[1][1] 4:c[2][3] 4:c[3][2] count=18;

第2个工人已经回溯到n，再回溯到第1个工人重新分配：

2:c[1][2] 2:c[2][1] 5:c[3][3] count=9;

回溯到第2个工人，重新分配：

2:c[1][2] 4:c[2][3] 3:c[3][1] count=9;

再次回溯到第1个工人，重新分配：

3:c[1][3] 2:c[2][1] 4:c[3][2] count=9;

回溯到第2个工人，重新分配：

3:c[1][3] 3:c[2][2] 3:c[3][1] count=9;

这样，就得到了所有的可行解。而我们是要得到最少的费用，即可行解中和最小的一个，故需要再定义一个全局变量cost表示最终的总费用，初始cost为c[i][i]之和，即对角线费用相加。在所有工人分配完工作时，比较count与cost的大小，如果count小于cost,证明在回溯时找到了一个最优解，此时就把count赋给cost。
到这里，整个算法差不多也快结束了，已经能得到最终结果了。但考虑到算法的复杂度，这里还有一个剪枝优化的工作可以做。就是在每次计算局部费用变量count的值时，如果判断count已经大于cost，就没必要再往下分配了，因为这时得到的解必然不是最优解。