实验5 回溯算法

班级 通信一班 学号14082300943姓名 张博 成绩 分

一、设计目的

1.掌握回溯法解题的基本思想； 2.掌握回溯算法的设计方法；

3.针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。

二、设计内容

分派问题: 给n个人分派n件作业, 把工作j分派给第i个人的成本为cost(i, j), 设计、编程、测试回溯算法, 在给每个人分派一件不同工作的情况下使得总成本最小。 1.阐述用回溯法求解的状态空间树结构：

画出部分树，说明节点、边、到根节点的路径的意义，给

出答案节点的定义。

2.阐述用回溯法求解的基本思想：

设计并说明规范函数，扼要阐述搜索过程。 3.画出搜索过程的主要流程图。 4.说明输入数据的表示方法、主要的数据变量、主要的函数功能。 5.写出各函数的伪C语言代码。

三、设计数据

假设有三个人完成不同的三个作业，他们对完成不同的作业所需 要的成本是不同的，集体情况如下表所示:

工人 作业 1 成本：1 成本：3 成本：4 2 成本：2 成本：1 成本：5 3 成本：3 成本：4 成本：1 1 2 3 四、设计结果

1.设计的状态空间树结构： 工人1 作业：1 成本：1 1 作业：3 作业：2 成本：3 成本：4 工人2 作业：2 成本：1 2 7 作业：3 成本：5 作业：1 成本：2 作业：3 成本：5 作业：1 成本：2 12 作业：2 成本：1 工人3 3 5 作业：2 成本：4 8 作业：3 成本：1 10 作业：1 成本：3 13 作业：2 成本：4 15 作业：1 成本：3 作业： 3 成本：1 4 成本： 3 6 10 9

11 11 14 16 6 10 8 上图中前一、二、三层分别为工人1、2、3，工人1可以先有3

中作业选择，然后工人2在剩下的2个作业中选1个作业，剩下的自然就是工人3要做的作业。图中已经在标记处标明了每个工人所做的作业及其所用成本，以及最后每种情况所需的成本的结果。

2.阐述用回溯法求解的基本思想：

(1)规范函数

int Place(int k) //Place判断在第 k 个人是否可以做x[k]的事 {int i;

for(i = 1; i < k; i++) if(x[i]==x[k]) return 0; return 1;}

(2)设计一个成本的最大值minsum，然后在每次遍历工人作业的成本，把较小的成本覆盖minsum，直到最后把最小的成本来找到。 (3)在遍历每个工人所作作业的成本的时候都和minsum进行比较，如果当时的成本已经比minsum大了就没有必要继续往下走了，就返回到上一个节点，继续另外的情况。这便是回溯算法的本质。 3.画出搜索过程的主要流程图。

当前成本：2 1 当前成本：0 2 当前成本：1 7 当前成本：3 12 当前成本：4 3 4 5 当前成本：6 1 当前成本：2 1 当前成本：5 当前成本：3 最小成本：3

4.说明输入数据的表示方法、主要的数据变量、主要的函数功能。 int n//表示有n个工人和n个作业

int sumcost//存放成本总和 int minsum//存放最小成本

int cost[i][j]//表示工人i做作业j做需要的成本。

int Place(int k) //Place判断在第 k 个人是否可以做x[k]的事

void NQueens(int k, int sumcost)//遍历每种情况，比较每种情况下的成本，得出最小成本。 5.写出各函数的伪C语言代码。

int Place(int k) //Place判断在第 k 个人是否可以做x[k]的事 { int i;

for(i = 1; i < k; i++)

if(x[i]==x[k]) return 0; return 1; }

void NQueens(int k, int sumcost)

{ if(sumcost > mincost) return ;x[k] = 0; while(1) { x[k]++;

while((x[k]<=n)&&(!Place(k))) x[k]=x[k]+1; if(x[k] <= n) {

sumcost += cost[k][x[k]]; if(k < n)

NQueens(k+1, sumcost);

else {

if(sumcost < mincost) mincost = sumcost;

}

sumcost -= cost[k][x[k]]; }

else return ;

} }

6.运行结果

程序时用C代码写的，并在VC++6.0上面运行成功。

五、设计总结与讨论

通过此次算法设计对回溯算法有了更进一步的理解，对之前的状态空间树很模糊，不知道怎么弄，但是通过实验我有了很好的理解。在这过程中，我又仔细阅读了教科书，以及回忆老师上课所讲解的知识，把回溯算法的思路进行了理清，最后用C代码实现了它，本次的感悟是只要我们学生愿意花时间去思考，就能学到我们的知识，并且实践它。

六、程序代码

#include

int cost[100][100],x[100]; int mincost,n;

int Place(int k) //Place判断在第 k 个人是否可以做x[k]的事 { int i;

for(i = 1; i < k; i++) if(x[i]==x[k]) return 0; return 1;}

void NQueens(int k, int sumcost)//搜索最小成本函数 { if(sumcost > mincost) return ;x[k] = 0; while(1){ x[k]++;

while((x[k]<=n)&&(!Place(k))) x[k]=x[k]+1; if(x[k] <= n)

{sumcost += cost[k][x[k]]; if(k < n)

NQueens(k+1, sumcost); else

{if(sumcost < mincost) mincost = sumcost;} sumcost -= cost[k][x[k]];}

Else return ; } }

int main() {

int i,j;

mincost = 0x7fffffff; printf(\"输入n:\"); scanf(\"%d\

printf(\"依次输入第i个人做第j作业的成本:\\n\"); for(i=1;i<=n;i++) for(j=1;j<=n;j++)

scanf(\"%d\

printf(\"\\n以上从键盘输入的数组的意思是:行代表人，列代表作业的成本\\n\");

printf(\"第i行第j列表示:工人i做作业j所需要的成本！\\n\\n\");

NQueens(1,0);

printf(\"最小总成本为: %d\\n\

printf(\"\\n\\n感谢谢老师！算法设计很有趣！！08通信一班 张博 14082300943\\n\"); return 0;

}