算法设计与分析——回溯法.ppt

算法设计与分析问题的提出八皇后问题是数学家高斯（Gauss）于1850年提出的趣题：问题的求解思路穷举法：应用穷举法设计求解，通常分以下几个步骤：从特殊到一般的思维模式：#include<iostream>
#include<cmath>
usingnamespacestd;
voidFourQueens()
{for(inti=1;i!=5;++i)
{for(intj=1;j!=5;++j)
{for(intk=1;k!=5;++k)
{for(intr=1;r!=5;++r)
{if(i!=j&&j!=k&&k!=r&&k!=i&&r!=i&&r!=j
&&abs(j-i)!=1&&abs(k-j)!=1&&abs(r-k)!=1&&
abs(k-i)!=2&&abs(r-i)!=3&&abs(r-j)!=2)
{cout<<i<<""<<j<<""<<k<<""<<r<<endl;
break;
}}}}}
}
intmain()
{FourQueens(); return0;}当问题所涉及数量非常大时，穷举的工作量
也就相应较大，程序运行时间也就相应较长。为
此，应用穷举求解时，应根据问题的具体情况分
析归纳，寻找简化规律，精简穷举循环，优化穷
举策略。优化穷举法：任意两个皇后不允许处在同一横排，同一纵
列，要求8位数中数字1~8各出现一次，不能重复。
因而解的范围区间应为[12345678，87654321]。
注意到数字1~8的任意一个排列的数字和为9的倍
数，因而穷举a循环的循环步长可优化为9。为了判别数字1~8在8位数a各出现一次，设
置f数组，f（x）统计a中数字x的个数。若f（1）
~f（8）均等于1，即数字1~8在a中各出现一次。
否则，返回测试下一个8位数a。任意两个皇后不允许处在同一与棋盘边框成
45°角的斜线上，设置g数组，若a的第k个数字为
x，则g（k）=x。要求解的8位数的第j个数字与
第k个数字的绝对值不等于j–k（设置j>k）。若
出现：#include<stdio.h>
#include<math.h>
voidmain()
{
ints,k,i,j,t,x,f[9],g[9];
longa,y;
s=0;
printf("高斯8皇后问题的解为:\n");
for(a=12345678;a<=87654321;a=a+9)//步长为9穷举八位数
{
y=a;k=0;
for(i=1;i<=8;i++)f[i]=0;
while(y>0)
{
x=y%10;
f[x]=f[x]+1;
y=y/10;
k++; g[k]=x;
}//分离各数字，用f数组统计
for(t=0,i=1;i<=8;i++)
if(f[i]!=1)t=1;
if(t==1)continue;//数字1—8出现不为1次，返回
for(k=1;k<=7;k++)
for(j=k+1;j<=8;j++)
if(fabs(g[j]-g[k])==j-k)t=1;
if(t==1)continue;//同处在45度角的斜线上，返回
s++;//输出8皇后问题的解
printf("%ld",a);
if(s%6==0)printf("\n");
}
printf("\ns=%d\n",s);
}
回溯法：回溯法的基本做法是试探搜索，是一种组织
得井井有条的、能避免一些不必要搜索的穷举式
搜索法。这种方法适用于一些组合数比较大的问
题。回溯算法在问题的解空间树中，从根结点出
发搜索解空间树，搜索至解空间树的任意一点，
先判断该结点是否包含问题的解；如果肯定不包
含，则跳过对该结点为根的子树的搜索，逐层向
其父结点回溯；否则，进入该子树，继续搜索。与穷举法相比，回溯法的“聪明”之处在于能
适时“回头”，若再往前走不可能得到解，就回溯，
退一步另找线路，这样可省去大量的无效操作。
因此，回溯和穷举相比，回溯更适宜于量比较大，
候选解比较多的问题。思维的发散与拓展printf("\n");
}

voidtackle(inti)
{
intj;
for(j=1;j<=n;j++)
{//列数的移动
if((b[j]==0)&&(c[i+j]==0)&&(d[i-j+n]==0))
{
a[i]=j;//记录下该行的可放列
b[j]=1;//表示该列被占
c[i+j]=1;//表示某斜率为1的对角线被占
d[i-j+n]=1;//表示某斜率为-1的对角线被占

if(i<n) {//小于8则递归
tackle(i+1);
}
else
{//处理完则输出
output()