实验3.3 任务分配问题
实验目的
(1)理解穷举法典型算法的求解过程。
(2)学习穷举法的时间复杂度分析方法,并通过实验验证算法的执行效率。
(3)学会如何利用穷举法求解具体问题,了解穷举法的局限性。
实验任务
(1)利用穷举法手工完成实验3.3测试用例的求解。
(2)用C++语言实现该算法并进行测试。
(3)撰写实验报告,实验报告内容包括实验目的、实验任务、实验环境、实验步骤、实验结果和实验总结等部分。
实验步骤及结果
实验预习
根据样例输入采用穷举法求出一种总成本最小的分配方案
该问题的解空间树是排列树
约束条件:遍历到的任务没有被执行,如果不满足则continue
目标函数:设每个人执行所分配任务的成本是 xi
则f(x) = min
样例对应搜索空间树:
其中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;
}
上机实验
上机调试,验证你的求解过程是否正确,写出验证过程
在程序添加将每次方案和方案成本输出代码来验证求解过程是否正确,输入已给样例,得到输出截图:
通过输出截图可知求解过程正确
设计新的测试用例,对程序进行进一步验证
用例输入:
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
输出截图(方案过多直接输出最小成本):
通过输出截图易知算法正确
完成实验3.2的实验预习1
实验总结
通过具体学习了排列这种典型的穷举算法的求解过程以及程序框架,分析了其算法的求解过程,时间复杂度分析方法,以及如何设计穷举法解决实际问题。通过此次实验,正确理解了穷举法的特点以及实际运用中的局限性,并为以后得学习打下基础。