文档介绍：综合性、设计性实验报告
姓名_________学号__
专业计算机科学与技术班级级班
实验课程名称算法设计与分析
指导教师及职称讲师
开课学期 2009 至 2010 学年上学期
上课时间 2010年 12 月 20 日
一、实验设计方案
实验名称:回溯法实例编程
实验时间: 2010-12-20
小组合作: 是○否●
小组成员:无
1、实验目的:
1)理解回溯法的深度优先搜索策略
2)掌握用回溯法解题的算法框架
3)针对具体问题,能应用回溯法设计有效算法
4)用C++实现算法,并且分析算法的效率
2、实验设备及材料:
硬件设备: pc
机器配置: AMD Athlon(tm)II x2 240 、
操作系统: Windows xp
开发工具: vc++
3、实验内容:
①问题描述
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算
法,为每一个人都分配1 件不同的工作,并使总费用达到最小。
②编程任务
设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。
③样例
例如,现要将3件工作分配给3个人。将工作1分配给3个人所需的费用分别为￥10 、￥2、￥3;将工作2分配给3个人所需的费用分别为￥2、￥3、￥4;将工作3分配给3个人所需的费用分别为￥3 、￥4、￥5。
那么,共有___3___种方案可使总费用达到最少。这些方案分别为:工作1分配给第二个人,工作2分配给第一个人,工作3分配给第三个人;工作1分配给第三个人,工作2分配给第一个人,工作3分配给第二个人;工作1分配给第三个人,工作2分配给第二个人,工作1分配给第一个人。上述方案都可使总费用达到最少,即￥9。
4、实验方法步骤及注意事项:(注意:此部分为本实验的关键部分,请自行填写,不得雷同!)
①实验步骤(参考教材141页第4段自行填写)
一、定义一个解空间,它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。
②解题思路(注意:以下部分仅为提示,请自行填写;若表格不够,可自行拉伸。)
以n=3为例,解空间为{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2)(3,2,1)}
以n=3为例,画出工作分配问题的解空间树。
A
1
B
C
D
E
F
G
H
I
J
K
2
3
2
3
3
L
2
M
N
O
P
3
1
3
1
2
1
1
2
给出使用递归回溯法求解工作分配问题的算法,用C++语言描述。
#include"iostream"
#include"fstream"
using namespace std;
#define NUM 50
int bestV[NUM],job[NUM],value[NUM][NUM];
int MINCOST = 999999999;
void swap(int &job1,int &job2) {
int t ;
t= job1;
job1 = job2;
job2