《算法实验报告：回溯法(C语言)》由会员分享，可在线阅读，更多相关《算法实验报告：回溯法(C语言)（6页珍藏版）》请在金锄头文库上搜索。
1、实实 验验 报报 告告（ 2015/2015/ 20162016 学年学年 第第 一一 学期）学期）课程名称算法设计与分析实验名称回溯法实验时间2016年5月5日指导单位计算机软件学院指导教师费宁学生姓名罗熊班级学号B14050123学院(系)自动化专 业自动化实实 验验 报报 告告实验名称实验名称回溯法回溯法指导教师指导教师费宁费宁 实验类型实验类型验证验证实验学时实验学时2 2实验时间实验时间2016.5.52016.5.51、 实验目的和要求实验目的和要求 在算法设计中，回溯法是比贪心法更一般的方法，掌握回溯法的的适用条，熟练 地适用回溯法求解实际问题。在本实验中用回溯法求解 8 皇后问
2、题。二、实验环境实验环境( (实验设备实验设备) )VC+6.03、实验原理及内容实验原理及内容:实验原理：用回溯法求解的问题通常需要给出某些必须满足的约束条件。这些约束 条件分为显式约束和隐式约束。用于规定每个 xi 取值的约束条件称为显示约束，显示约 束规定了所有可能的元组，它们组成了问题的候选解集，称为问题的解空间。隐式约束 给出了判定一个候选解集是否为可行解的一般条。有隐式约束设计一个判定函数 p()，使 得当且仅当 p()为真时，n-元组是问题的满足隐式约束的一个可行解。目标函数用来衡量 每个可行解的优劣，使目标函数去最大值或最小值得可行解为问题的最优解。实验代码#include #
3、include #define max 8 int queenmax, sum=0;void show() int i;printf(“(“);for(i = 0; i max; i+)printf(“ %d“, queeni);printf(“)n“);sum+; int PLACE(int n) int i;for(i = 0; i n; i+) if(queeni = queenn | abs(queeni - queenn) = (n - i)return 1;return 0; void NQUEENS(int n) int i;for(i = 0; i max; i+) queen
4、n = i; if(!PLACE(n) if(n = max - 1)show(); elseNQUEENS(n + 1); int main() NQUEENS(0);printf(“%d“, sum);system(“pause“);return 0; ： 实验结果：4、实验小结实验小结回溯法以深度优先次序生成状态空间树中的结点，并使用剪纸函数减少实际生成的 结点数，回溯法是一种广泛适用的算法设计技术。是要问题的解是元组形式，可用状态 空间树描述，并采用判定函数识别答案结点，就能采用回溯法求解。回溯法使用约束函 数剪去不含可行解的分枝。当使用回溯法求最优化问题时，需要设计界限函数用于剪去分枝。五、指导教师评语五、指导教师评语成成 绩绩批阅人批阅人日日 期期
