算法实验报告四 回溯法实验 姓名：孙月欣 学号：408109070414 一、实验目的及要求 利用回溯方法设计指派问题的算法，掌握回溯法的基本思想和算法设计的基 本步骤。 要求：设计指派问题的回溯算法，注意回溯算法解决此问题要找出问题所有 的可行解，然后一次比较保留问题的最优解(即最少耗费的解)，并输出结果。利 用 c 语言（c++语言）实现算法，给出程序的正确运行结果。（必须完成） 指派问题描述： n 个雇员被指派做 n 件工作，使得指派第 i 个人做第 i 件工作的耗费为 ci,j, 找出一种指派使得总耗费最少。 二、算法描述 输入：各个人做各项工作的耗费(C[i,j]行代表工作，列代表雇员) 输出：输出当前指派和当前耗费，最小耗费 cost 1、for k =1 to 4 2、a[k]=0; 3、end for; 4、k=1; 5、while k>=1 6、 while a[k]<=3 7、 a[k]=a[k]+1; v=v+c[k][a[k]]; 8、 for(j=1;j<=k-1;j++) 9、 10、 if(a[k]!=a[j]) 11、 12、 13、 else if a[k]为部分解 then k=k+1｛前进｝ 14、end while; 15、a[k]=0; 16、k=k-1; 17、v=v-c[k][a[k]];｛回溯｝ 18、end while; 19、输出每次求得的耗费，求出最小的即调用 min(s[]，m)函数，并将最小耗费 cost 输出 20、结束 三、调试过程及运行结果 else 标记非法解，剪掉部分； If a[k]为合法解 then 输出当前指派和当前耗费 then 标记合法与部分解； 调试过程中出现的问题：开始按照回溯算法所给的模式写完了程序，却无法 出现预想的结果。经单步调试发现是我的程序结构混乱，部分解和合法解还有非 法解之间的条件处理有问题，导致输出结果错误。通过单步调试改正了条件错误。 

四、实验总结 通过本次实验加深了我对回溯算法模式的理解，同时将回溯算法应用到一个 实际应用中。回溯算法非递归的模式通用，用它解决问题的关键是找出合法解与 部分解的判断条件，算法执行的 n 元组及其定义域。在回溯法应用时，注意要认 真分析合法解和部分解的判断条件，条件的分析不清就导致整个程序结果的错 误。 五、附录 #include #include #define n 4 #define max 30 int min(int s[],int m); void main() { int c[max][max];//耗费数组，第 i 个人做第 j 项工作的耗费 

for(j=1;j<=n;j++) { cin>>c[i][j]; } } for(i=1;i<=n;i++) { a[i]=0; for(j=1;j<=n;j++) { s[j]=0; int a[max]; int s[max]; int t=0; int v=0;//当前耗费 int cost=0;//最小耗费 int i,j,k; int times=0;//记录求最少耗费的次数; bool flag; cout<<"请输入各个人做各项工作的耗费(行代表工作，列代表雇员)"<=1) { while(a[k]<=n-1) { a[k]=a[k]+1; v=v+c[k][a[k]]; if(cost!=0) flag=false; 

if(k==1) flag=true; for(j=1;j<=k-1;j++) { if(a[k]!=a[j]) { flag=true; } else { } 当前指派的耗费为："; flag=false; v=v-c[k][a[k]]; break; } if(k==n && flag==true) { cout<<"当前指派为："; for(i=1;i<=n;i++) cout<

{ cout<s[i]) x=s[i]; } return x; } 教师评语： 成绩：优 良 中 及格 不及格