文档介绍：实验报告
( 2015/ 2016学年第一学期)
课程名称
算法设计与分析
实验名称
回溯法
实验时间
2016
年
5
月
5
日
指导单位
计算机软件学院
指导教师
费宁
学生姓名
罗熊
班级学号
B14050123
学院(系)
自动化
专业
自动化
实验报告
实验名称
回溯法
指导教师
费宁
实验类型
验证
实验学时
2
实验时间
实验目的和要求
在算法设计中,回溯法是比贪心法更一般的方法,掌握回溯法的的适用条,熟练
地适用回溯法求解实际问题。在本实验中用回溯法求解8皇后问题。
二、实验环境(实验设备)
VC++
实验原理及内容:
实验原理:用回溯法求解的问题通常需要给出某些必须满足的约束条件。这些约束条件分为显式约束和隐式约束。用于规定每个xi取值的约束条件称为显示约束,显示约束规定了所有可能的元组,它们组成了问题的候选解集,称为问题的解空间。隐式约束给出了判定一个候选解集是否为可行解的一般条。有隐式约束设计一个判定函数p(),使得当且仅当p()为真时,n-元组是问题的满足隐式约束的一个可行解。目标函数用来衡量每个可行解的优劣,使目标函数去最大值或最小值得可行解为问题的最优解。
实验代码#include <>
#include <>
#define max 8
int queen[max], sum=0;
void show()
{
int i;
printf("(");
for(i = 0; i < max; i++)
{
printf(" %d", queen[i]);
}
printf(")\n");
sum++;
}
int PLACE(int n)
{
int i;
for(i = 0; i < n; i++)
{
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
{
return 1;
}
}
return 0;
}
void NQUEENS(int n)
{
int i;
for(i