西南交通大学【算法分析与设计实验3】

实验3.3 任务分配问题

实验目的

（1）理解穷举法典型算法的求解过程。

（2）学习穷举法的时间复杂度分析方法，并通过实验验证算法的执行效率。

（3）学会如何利用穷举法求解具体问题，了解穷举法的局限性。

实验任务

（1）利用穷举法手工完成实验3.3测试用例的求解。

（2）用C++语言实现该算法并进行测试。

（3）撰写实验报告，实验报告内容包括实验目的、实验任务、实验环境、实验步骤、实验结果和实验总结等部分。

实验步骤及结果

实验预习

根据样例输入采用穷举法求出一种总成本最小的分配方案

该问题的解空间树是排列树

约束条件：遍历到的任务没有被执行，如果不满足则continue

目标函数：设每个人执行所分配任务的成本是 xi

则f(x) = min $\sum xi$

样例对应搜索空间树：

其中0代表未分配任务

通过图可以看出第一个人执行第二个任务，第二个人执行第一个任务，第三个人执行第三个任务，第四个人执行第四个任务成本最小。

用C/C++语言实现的源代码

#include <iostream>
using namespace std;
// 任务成本
int c[100][100];
// 人数（任务数），初始化为1
int n = 1;
// 最小成本，初始化为10000
int min_cost = 10000;
// 判断任务是否被执行的数组
int used[100];
// 每个人执行哪个人物的数组
int res[100];
// 回溯
void backtracking(int res[], int used[], int num){
    // 如果res中结果数量达到人数则退出递归
    if(num == n){
        // 计算此种任务分配的成本
        int sum = 0;
        for(int i = 1;i <= n;++i){
            sum += c[i][res[i]];
        }
        // 如果成本比最小成本小更新最小成本
        if(sum < min_cost){
            min_cost = sum;
        }
        return;
    }
    // 遍历used数组往下递归
    for(int i = 1;i <= n;++i){
        // 如果任务已执行continue
        if(used[i] == 1){
            continue;
        }
        // 执行此任务
        used[i] = 1;
        // 执行人数加1
        num++;
        // 将任务分配给此人
        res[num] = i;
        // 向下递归
        backtracking(res, used, num);
        // 回溯
        res[num] = 0;
        num--;
        used[i] = 0;
    }
}
int main(void){
    // 读取第一行数据
    char temp;
    int number = 0;
    // 读取第一行数据得到人数（任务数）
    while(temp = getchar()){
        if(temp == ' '){
            c[1][n] = number;
            number = 0;
            n++;
        }else if(temp == '\n'){
            c[1][n] = number;
            number = 0;
            break;
        }else{
            number = number * 10 + (temp - '0');
        }
    }
    // 读取剩下的数据
    for(int i = 2;i <= n;++i){
        for(int j = 1;j <= n;++j){
            cin>>c[i][j];
        }
    }
    // 初始化res数组和used数组
    for(int i = 1;i <= n;++i){
        res[i] = 0;
        used[i] = 0;
    }
    // 开始递归
    backtracking(res, used, 0);
    // 输出最小成本
    cout<<min_cost<<endl;
    system("pause");
    return 0;
}

上机实验

上机调试，验证你的求解过程是否正确，写出验证过程

在程序添加将每次方案和方案成本输出代码来验证求解过程是否正确，输入已给样例，得到输出截图：