当前位置：文档之家 › 回溯算法实验报告

回溯算法实验报告

  • 格式：docx
  • 大小：31.56 KB
  • 文档页数：2

回溯算法实验报告
一、问题定义
在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规矩，皇后
可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n
格的棋盘上方置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
我们需要求的是可放置的总数。

二、
基本思路

用n元组x[1；n]表示n后问题的解。其中，x[i]表示皇后i放置在棋盘的第i行的第x[i]列。由于不容
许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约
束。对于一般的n后问题，这一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵，
其行号从上到下，列号从左到右依次编号为1,2，...n。从棋盘左上角到右下角的主对角线及其平行线（即
斜率为-1的各斜线）上，2个下标值的差（行号-列号）值相等。同理，斜率为+1的每条斜线上，2个下标
值的和（行号+列号）值相等。因此，若2个皇后放置的位置分别是（i,j）和（k,l）,且 i-j = k -l 或 i+j
= k+l，则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。由此可知，
只要|i-k|=|l-j|成立，就表明2个皇后位于同一条斜线上。

1、从空棋盘起，逐行放置棋子。
2、每在一个布局中放下一个棋子，即推演到一个新的布局。
3、如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。
四、编码

#include
#include
#include
static int n,x[1000];
static long sum;
int Place(int k)
{
for(int j=1;j if((abs(k-j) == abs(x[j]-x[k]))||(x[j]==x[k])) return 0;
return 1;
}
void Backtrak(int t)
{
if(t>n) sum++;
else
for(int i=1; i <= n; i++)
{
x[t] =i;
if(Place(t))Backtrak(t+1);
}
}

int main()
{
int nn;
while(scanf("%d",&nn)!=EOF)
{
n=nn;
sum=0;
for(int i=0;i<=n;i++)
x[i]=0;
Backtrak(1);
printf("%d\n"
,sum);
}
}

五、总结
我感受出了
回溯算法的核心思想：但当探索到某一步时，发现原先选择并不优
或达不到目标，就退回一步重新选择

合集下载

回溯法实验报告

回溯法实验报告

数学与计算机学院实验报告一、实验项目信息项目名称：回溯法实验时间： 2016/06/08 实验学时： 03 学时实验地点：工科楼503 二、实验目的及要求理解回溯法的深度优先搜索策略、掌握用回溯法解题的算法框架、掌握回溯法的设计策略三、实验环境计算机Ubuntu Kylin14.04CodeBlock软件四、实验内容及实验步骤排兵布阵问题某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。

试设计一个布阵方案，使总的攻击力最大。

数据：防卫点角色1 2 3 4 512345回溯法：程序：#include<stdio.h>int position[10];int a[10][10];int check(int k){//每个节点检查的函数int i;for(i=0;i<k;i++)if(position[i]==position[k])return 0;//重复返回0return 1;}void gameSort(int n){int i,k;int max=0;int ans[10];int sum;for(i=0;i<n;i++)position[i]=0;k=0;while(k>=0){sum=0;position[k]=position[k]+1;while(position[k]<=n)if(check(k))break;else position[k]=position[k]+1;if(position[k]<=n && k==n-1){for(i=0;i<n;i++){sum+=a[i][position[i]-1];}if(max<sum){max=sum;for(i=0;i<n;i++)ans[i]=position[i];}}if(position[k]<=n&&k<n-1)k=k+1;elseposition[k--]=0;}printf("answer is:");for(i=0;i<n;i++)printf("(%d,%d) ",i+1,ans[i]);printf("\n");printf("the largest number is:%d",max); }void main(){int i,j,n;printf("please input n:");scanf("%d",&n);for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&a[i][j]);gameSort(n);printf("\n");} 五、实验结果分析程序运行：得到正确结果六、实验总结通过实验对回溯法求解的概念更加熟悉，对回溯法的程序算法深入理解。

实验报告4.回溯算法

实验报告4.回溯算法

算法设计与分析实验报告实验名称_____回溯算法_____学院________数学与计算机学院____ 班级_______信科00000___________ 学号_______6666666666__________ 姓名_____000000________________ 2016年月日{if(((a+b)==24)||((a-b)==24)||((a*b)==24)||(b!=0&&a%b==0&&a/b==24)){//如果经过上面的计算得到解while(!route.empty()){node now=route.front();printf("%d%c%d=%d\n",now.a,now.oper,now.b,now.sum);//依次输出前面的计算过程route.pop();}if((a+b)==24){if(b>a) swap(a,b);printf("%d+%d=%d\n",a,b,a+b);}if((a-b)==24) printf("%d-%d=%d\n",a,b,a-b);if((a*b)==24) {if(b>a) swap(a,b);printf("%d*%d=%d\n",a,b,a*b);}if(a%b==0&&b!=0&&(a/b)==24) printf("%d/%d=%d\n",a,b,a/b);//a/b比较特殊，要求结果必须是整数flag=true;//表示找到解，一旦找到任何一个解就退出}return ;}queue <node> temp=route;node x;x.a=a,x.b=b,x.sum=a+b,x.oper='+';if(b>a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a+b,num[cur+1],temp);//(((a*b)*c)*d) 模型temp=route;x.a=a,x.b=b,x.sum=a*b,x.oper='*';if(b>a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a*b,num[cur+1],temp);temp=route;x.a=a,x.b=b,x.sum=a-b,x.oper='-';temp.push(x);dfs(cur+1,a-b,num[cur+1],temp);if(b!=0&&a%b==0){//a/b需要验证合法性temp=route;x.a=a,x.b=b,x.sum=a/b,x.oper='/';temp.push(x);dfs(cur+1,a/b,num[cur+1],temp);}temp=route;x.a=b,x.b=num[cur+1],x.sum=b+num[cur+1],x.oper='+';if(x.b>x.a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a,b+num[cur+1],temp);//a*((b*c)*d) 模型temp=route;x.a=b,x.b=num[cur+1],x.sum=b*num[cur+1],x.oper='*';if(x.b>x.a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a,b*num[cur+1],temp);temp=route;x.a=b,x.b=num[cur+1],x.sum=b-num[cur+1],x.oper='-';temp.push(x);dfs(cur+1,a,b-num[cur+1],temp);if(num[cur+1]!=0&&b%num[cur+1]==0) {temp=route;x.a=b,x.b=num[cur+1],x.sum=b/num[cur+1],x.oper='/';temp.push(x);dfs(cur+1,a,b/num[cur+1],temp);}}int main(){//freopen("point24.in","r",stdin);//输入输出重定向//freopen("point24.out","w",stdout);queue <node> t;scanf("%d %d %d %d",&num[0],&num[1],&num[2],&num[3]);while(!flag){dfs(1,num[0],num[1],t);printf("%d %d %d %d\n",num[0],num[1],num[2],num[3]);if(!next_permutation(num,num+4)) break;}if(!flag) printf("No answer!\n");system("pause");return 0;}。

回溯法实验报告

回溯法实验报告

综合性、设计性实验报告姓名_________学号__专业计算机科学与技术班级级班实验课程名称算法设计与分析指导教师及职称讲师开课学期2009 至2010 学年上学期上课时间2010年12 月20 日一、实验设计方案实验名称：回溯法实例编程实验时间：2010-12-20小组合作：是○否●小组成员：无1、实验目的：1）理解回溯法的深度优先搜索策略2）掌握用回溯法解题的算法框架3）针对具体问题，能应用回溯法设计有效算法4）用C++实现算法，并且分析算法的效率2、实验设备及材料：硬件设备： pc机器配置： AMD Athlon(tm)II x2 240 2.80GHz 、2.0GB内存操作系统： Windows xp开发工具： vc++6.03、实验内容：①问题描述设有n件工作分配给n个人。

将工作i分配给第j个人所需的费用为c ij。

试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。

②编程任务设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

③样例例如，现要将3件工作分配给3个人。

将工作1分配给3个人所需的费用分别为￥10 、￥2、￥3；将工作2分配给3个人所需的费用分别为￥2、￥3、￥4；将工作3分配给3个人所需的费用分别为￥3 、￥4、￥5。

那么，共有___3___种方案可使总费用达到最少。

这些方案分别为：工作1分配给第二个人，工作2分配给第一个人，工作3分配给第三个人;工作1分配给第三个人，工作2分配给第一个人，工作3分配给第二个人;工作1分配给第三个人，工作2分配给第二个人，工作1分配给第一个人。

上述方案都可使总费用达到最少，即￥9。

4、实验方法步骤及注意事项：（注意：此部分为本实验的关键部分，请自行填写，不得雷同！）①实验步骤（参考教材141页第4段自行填写）一、定义一个解空间，它包含问题的解。

二、利用适于搜索的方法组织解空间。

三、利用深度优先法搜索解空间。

算法实验报告：回溯法(C语言)

算法实验报告：回溯法(C语言)

实验报告
（2015/ 2016学年第一学期）
课程名称算法设计与分析
实验名称回溯法
实验时间2016年5月5日指导单位计算机软件学院
指导教师费宁
学生姓名罗熊班级学号B14050123
学院(系)自动化专业自动化
实验报告
NQUEENS(0);
printf("%d", sum);
system("pause");
return 0;
}：
实验结果：
四、实验小结
回溯法以深度优先次序生成状态空间树中的结点，并使用剪纸函数减少实际生成的结点数，回溯法是一种广泛适用的算法设计技术。

是要问题的解是元组形式，可用状态空间树描述，并采用判定函数识别答案结点，就能采用回溯法求解。

回溯法使用约束函数剪去不含可行解的分枝。

当使用回溯法求最优化问题时，需要设计界限函数用于剪去分枝。

五、指导教师评语
成绩批阅人日期。