回溯法实现n份作业分配给n个人完成的问题

问题描述：

有n份作业分配给n个人去完成，每人完成一份作业。假定第i个人完成第j份作业需要花费cij时间， cij>0,1≦i,j≦n。试设计一个回溯算法，将n份作业分配给n个人完成，使得总花费时间最短。

问题思路：

n分作业分配给n个人，共有A!中排列方式，深度优先遍历其排列数，如果遍历的路径已经比当前最小的话费则舍弃对当前路径的遍历，返回上层节点，寻找合适的路径，即回溯，如果最后可行解比当前的最小话费小，那么就更行最佳的作业安排顺序，同时更新最小的耗费时间。

算法描述：

t :递归的层数

curr :当前的实际时间花费

bestw :当前的最优的时间消耗

arrange：任务的安排

Backtrack(t)

　　if t>=n 

　　　　then if curr<bestw

　　　　　　then bestw <- curr  

　　　　　　　　update arrange

　　　　　　ouput(arrange)

　　else do

　　　　for t to n do

　　　　　　swap the arrange of t and i

　　　　　　compute the current cost of the arrange

　　　　　　if curr<bestw then backtrack（t+1）   

　　　　　　swap the arrange of t and i

　　　　　　give back the arrange t 

 数据结构的选择：使用数组是想对任务工作的安排

算法的复杂度分析：O（n！）

算法的实现：

//backtrack.h
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void backtrack(int t);//t为排列树的深度
void getRslt(char filename[]);//从文件中读取数据，求解结果
void output(int *arrange);//输入最终的任务分配结构
void swap(int &a,int &b);//交换数组中的两个元素

//backtrack.cpp

#include "backtrack.h"
#include <malloc.h>

int *arrange;// 最终的作业分配安排
int dataSize;//任务的个数 和人员的个数相同
int **cost;//邻接矩阵用于存储每个人完成每份作业所需要的时间消耗
int bestw=INT_MAX;//初始为最大的整数 若出现小的则更行
int curr=0;
int *best_arrange;

void getRslt(char filename[])
{
    FILE *fp;
    int i=0;
    int j=0;
//    curr=0;

    fp=fopen(filename,"r");
    if (!fp)
    {
        printf("error,can not open the file%s",filename);
        return;
    }

    fscanf(fp,"%d",&dataSize);
    //开辟数据的空间，并将数据存在空间中
    best_arrange=(int*)malloc(dataSize*sizeof(int));
    cost=(int**)malloc(dataSize*sizeof(int*));
    for (i=0;i<dataSize;i++)
    {
        cost[i]=(int*)malloc(dataSize*sizeof(int));
        if (!cost[i])
        {
            printf("error can not malloc the space!");
        }
    }
    for (i=0;i<dataSize;i++)
    {
        for (j=0;j<dataSize;j++)
        {
            fscanf(fp,"%d",&cost[i][j]);
        }
    }
    arrange=(int *)malloc(dataSize*sizeof(int));
    if (!arrange)
    {
        printf("error,can not malloc a new space!");
    }
    for (i=0;i<dataSize;i++)
    {
        arrange[i]=i;
    }

    backtrack(0);

    output(best_arrange);
    printf("the best time is:%d\n",bestw);
    //释放开辟的空间避免内存泄露
    free(arrange);
    arrange=NULL;
    dataSize=0;
    for (i=0;i<dataSize;i++)
    {
        free(*(cost+i));
    }

    free(cost);

    cost=NULL;
    bestw=INT_MAX;
    curr=0;
    free(best_arrange);
    best_arrange=NULL;
}
void backtrack(int t)//t表示第t个作业cost[i][j]第i个人完成第j个任务所要完成的时间
{
    int i=0;
    int j=0;
    if (t>=dataSize)//已经达到叶子节点 递归出口
    {
        if (curr<bestw)
        {
            bestw=curr;
            for (j=0;j<dataSize;j++)
            {
                best_arrange[j]=arrange[j];
            }
        }
        return;
    }

    else
        for (i=t;i<dataSize;i++)//选取要递归的节点，依次递归节点的每一个孩子
        {
            swap(arrange[t],arrange[i]);//把第t个任务安排给arrang[i] 把第i个任务地第arrange[t]
            curr=curr+cost[arrange[t]][t];//当前时间家让把第t个任务我交给第arrange[i]所花费的时间
            if(curr>bestw)//当前的时间消耗已经超过当前的最佳时间 此时不用再递归其子节点 可以直接返回
            {    
                curr=curr-cost[arrange[t]][t];
                swap(arrange[t],arrange[i]);
                continue;//本次循环结束
            }

            backtrack(t+1);//递归一直到叶节点
            curr=curr-cost[arrange[t]][t];//如果没有解则回溯
            swap(arrange[t],arrange[i]);
        }
}

void output(int *arrange)//打印最终的结果
{
    int i=0;
    printf("the arrange of the work is:\n");
    for (i=0;i<dataSize;i++)
    {
        printf("the task %d is arranged to %d\n",(i+1),arrange[i]+1);
    }

}

void swap(int &a,int &b)//交换两个数的数值
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}

//main.cpp

#include "backtrack.h"
#include <string.h>

int main()
{
    char filename[256]="ddddd";
    while (1)
    {
        printf("please input the name of data file(input ‘exit’to quit the program):\n");
        gets(filename);
        if (!strcmp(filename,"exit"))
        {
            break;
        }
        getRslt(filename);
    }
    return 1;
}