资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
实实 验验 报报 告告( 2015/2015/ 20162016 学年学年 第第 一一 学期)学期)课程名称算法设计与分析实验名称回溯法实验时间2016年5月5日指导单位计算机软件学院指导教师费宁学生姓名罗熊班级学号B14050123学院(系)自动化专 业自动化实实 验验 报报 告告实验名称实验名称回溯法回溯法指导教师指导教师费宁费宁 实验类型实验类型验证验证实验学时实验学时2 2实验时间实验时间2016.5.52016.5.51、 实验目的和要求实验目的和要求 在算法设计中,回溯法是比贪心法更一般的方法,掌握回溯法的的适用条,熟练 地适用回溯法求解实际问题。在本实验中用回溯法求解 8 皇后问题。二、实验环境实验环境( (实验设备实验设备) )VC+6.03、实验原理及内容实验原理及内容:实验原理:用回溯法求解的问题通常需要给出某些必须满足的约束条件。这些约束 条件分为显式约束和隐式约束。用于规定每个 xi 取值的约束条件称为显示约束,显示约 束规定了所有可能的元组,它们组成了问题的候选解集,称为问题的解空间。隐式约束 给出了判定一个候选解集是否为可行解的一般条。有隐式约束设计一个判定函数 p(),使 得当且仅当 p()为真时,n-元组是问题的满足隐式约束的一个可行解。目标函数用来衡量 每个可行解的优劣,使目标函数去最大值或最小值得可行解为问题的最优解。实验代码#include #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+) queenn = i; if(!PLACE(n) if(n = max - 1)show(); elseNQUEENS(n + 1); int main() NQUEENS(0);printf(“%d“, sum);system(“pause“);return 0; : 实验结果:4、实验小结实验小结回溯法以深度优先次序生成状态空间树中的结点,并使用剪纸函数减少实际生成的 结点数,回溯法是一种广泛适用的算法设计技术。是要问题的解是元组形式,可用状态 空间树描述,并采用判定函数识别答案结点,就能采用回溯法求解。回溯法使用约束函 数剪去不含可行解的分枝。当使用回溯法求最优化问题时,需要设计界限函数用于剪去分枝。五、指导教师评语五、指导教师评语成成 绩绩批阅人批阅人日日 期期
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号