浏览 7398 次
|
锁定老帖子 主题：ACM典例分析之工作分配问题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-12-18
最后修改：2010-12-18
ACM中的工作分配问题是一个典型的回溯问题，利用回溯思想能很准确地得到问题的解。下面就这个问题好好分析下。
问题描述： 设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。 解题思路： 由于每个人都必须分配到工作，在这里可以建一个二维数组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 假定一个变量count表示工作费用总和，初始为0，变量i表示第i号工人，初始为1。n表示总的工作量，这里是取3。c[i][j]表示i号工人完成j号工作的费用，x[j]表示j号工作是否被分配。算法如下：
void work(int i,int count){
if(i>n)
return ;
for(int j=1;j<=n;j++)
if(x[j] == 0){
x[j] = 1;
work(i+1,count+c[i][j]);
x[j] = 0;
}
}
那么在这里，用回溯法的思想就是，首先分配的工作是： 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，就没必要再往下分配了，因为这时得到的解必然不是最优解。
#include<iostream>
using namespace std;
int n,cost=0;
int x[100],c[100][100];
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;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
x[j] = 0;
}
cost+=c[i][i];
}
work(1,0);
cout<<cost<<endl;
system("pause");
return 0;
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-12-31
最后修改：2010-12-31
果然只能回溯么。。。。
自己想了另一个算法，结果不对，也一起拿上来把
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 8
#define BOLD "\033[31m\033[1m"
#define NORM "\033[0m"
int cost[N][N];
int aux[N];
int cur[N];
int best[N];
int mincost;
void init(void)
{
int i, j;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
cost[i][j] = (rand() >> 3) % 100;
}
aux[i] = 0;
}
mincost = 999999;
}
void dumpcost(void)
{
int i, j;
printf("-------- Cost Dump --------\n");
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(best[i] == j) {
printf(BOLD "%4d " NORM, cost[i][j]);
} else {
printf("%4d ", cost[i][j]);
}
}
printf("\n");
}
printf("---------------------------\n\n");
}
void backtrack(int i, int c)
{
int j;
if(i == N) {
if(c < mincost) {
mincost = c;
memcpy(best, cur, sizeof(cur));
printf("Min = %d\n", c);
}
return;
}
for(j=0; j<N; j++) {
if(aux[j]) continue;
if(c + cost[i][j] > mincost) continue;
aux[j] = 1;
cur[i] = j;
backtrack(i+1, c + cost[i][j]);
aux[j] = 0;
}
}
void swapping(void)
{
int i, j, t;
for(i=0; i<N; i++) {
best[i] = i;
}
for(;;) {
t = 0;
for(i=0; i<N-1; i++) {
for(j=i+1; j<N; j++) {
if(cost[i][best[i]] + cost[j][best[j]] >
cost[i][best[j]] + cost[j][best[i]])
{
t = best[i];
best[i] = best[j];
best[j] = t;
t = 1;
}
}
}
if(!t) goto done;
}
done:
for(t=0, i=0; i<N; i++) {
t += cost[i][best[i]];
}
printf("Min = %d\n", t);
}
int main(void)
{
srand(time(NULL));
init();
backtrack(0, 0);
dumpcost();
swapping();
dumpcost();
return 0;
}
|
| 返回顶楼 | |
|
发表时间：2011-01-06
匈牙利算法不是更好？
|
| 返回顶楼 | |
|
发表时间：2011-01-07
大概理解了思路，想问一下代码里面只给出了总的cost，每个人该分配哪一件任务该怎么获得呢？
|
| 返回顶楼 | |
|
发表时间：2011-01-07
最后修改：2011-01-07
贴个我自己用JAVA写的，貌似还有待优化：
package cn.com.lbn.acm;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ResourcePlanTest {
private static int[][] resourcePlanView;
static {
resourcePlanView = new int[3][3];
resourcePlanView[0] = new int[]{1,4,9};
resourcePlanView[1] = new int[]{2,7,6};
resourcePlanView[2] = new int[]{3,1,5};
}
public static void main(String[] args) {
List path = caculate(new ArrayList(), new ArrayList());
System.out.println(path);
System.out.println(sumWork(path));
}
private static List caculate(List excludeRows, List excludeCols) {
List results = new ArrayList();
for(int row = 0; row < resourcePlanView.length; row++) {
if(excludeRows != null && !excludeRows.isEmpty() && excludeRows.contains(row)) {
continue;
}
for(int col = 0; col < resourcePlanView[0].length; col++) {
if(excludeCols != null && !excludeCols.isEmpty() && excludeCols.contains(col)) {
continue;
}
Position p = new Position(row, col);
List excludeRowsForSub = new ArrayList(excludeRows);
excludeRowsForSub.add(p.getRow());
List excludeColsForSub = new ArrayList(excludeCols);
excludeColsForSub.add(p.getCol());
List subPath = caculate(excludeRowsForSub, excludeColsForSub);
subPath.add(p);
results.add(subPath);
}
}
return selectMinWorkPath(results);
}
private static List selectMinWorkPath(List paths) {
int minSum = Integer.MAX_VALUE;
List minPath = new ArrayList();
for(Iterator iter = paths.iterator(); iter.hasNext();) {
List path = (List)iter.next();
int sum = sumWork(path);
if(sum < minSum) {
minSum = sum;
minPath = path;
}
}
return minPath;
}
private static int sumWork(List path) {
int sum = 0;
for(Iterator iter = path.iterator(); iter.hasNext();) {
Position pos = (Position)iter.next();
sum += resourcePlanView[pos.getRow()][pos.getCol()];
}
return sum;
}
}
class Position {
private int row;
private int col;
public Position() {
}
public Position(int row, int col) {
super();
this.row = row;
this.col = col;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public String toString() {
return "[" +row + "]" + "[" + col + "]" + "\n";
}
}
|
| 返回顶楼 | |
|
发表时间：2011-04-03
shediao 写道 匈牙利算法不是更好？
就是啊，搞ACM的，应该一看就知道是个二分图最优匹配问题，这种回溯解法还来“ACM典例分析”，ACM什么时候堕落成这样了 |
| 返回顶楼 | |
