目录
搜索与回溯算法
搜索与回溯是计算机解题过程中常用的算法，很多问题无法根据某种确定的计算机法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
迷宫问题：
进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走。这时，首先看其他方向是否还有路可走：如果有，则沿该方向再次向前试探；否则退回一步，再看其他方向是否还有路可走。按此原则下不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
递归回溯算法框架1
int search(int k){
for(i=1;i<=算符种数;i++){
if(满足条件)｛
保存结果;
if(到目的地)输出解;
else search(k+1);
//恢复：保存结果之前的状态
｝
}
}
递归回溯算法框架2
int search(int k){
if(到目的地)输出解;
else
for(i=1;i<=算符种数;i++){
if(满足条件)｛
保存结果;
search(k+1);
//恢复：保存结果之前的状态
｝
}
}
例5.1素数环：将1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
【算法分析】
非常明显，这是一道回溯的题目。将1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否是素数。
【算法流程】
（1）数据初始化；（2）递归填数：判断第i个数是否合法。
- 如果合法：填数；判断是否达到目标（20个已填完）：是，打印结果；不是递归填下一个。
- 如果不合法：选择下一种可能。
【参考程序】
//由于20个数的素数环方案太多，该代码以6个数为例（仅两种方案）
#include<bits/stdc++.h>
using namespace std;
bool b[21]={0,1};//判断是否可用
int total=0,a[21]={0,1};//计数、存储数据
int search(int );//回溯过程
int print();//输出方案
bool pd(int ,int );//判断素数
int n=20;
int main(){
search(2);
cout<<total<<endl;
return 0;
}
int search(int t){
int i;
for(i=2;i<=n;i++){//有20个数可选
if(pd(a[t-1],i)&&(!b[i])){//判断与前一个数是否构成素数及该数是否可用
a[t]=i;
b[i]=1;
if(t==n){if(pd(a[n],a[1]))print();}
else search(t+1);
b[i]=0;
}
}
}
int print()
{
total++;cout<<"<"<<total<<">";
for(int j=1;j<=n;j++)
cout<<a[j]<<" ";
cout<<endl;
}
bool pd(int x,int y){
int k=2,i=x+y;
while(k<sqrt(i)&&i%k!=0)k++;
if(k>sqrt(i)) return 1;
else return 0;
}
例5.2：设有n个整数的集合｛1,2，……，n｝，从中任意取出r个数进行排列（r<n）,试列出所有的排列。
【参考程序】
#include<bits/stdc++.h>
using namespace std;
int num=0,a[10001]={0},n,r;
bool b[10001]={0};
int search(int);
int print();
int main(){
cout<<"input n,r:";
cin>>n>>r;
search(1);
cout<<"number="<<num<<endl;
return 0;
}
int search(int k){
int i;
for(i=1;i<=n;i++){//有20个数可选
if(!b[i]){//判断与前一个数是否构成素数及该数是否可用
a[k]=i;
b[i]=1;
if(k==r){print();}
else search(k+1);
b[i]=0;
}
}
}
int print()
{
num++;
for(int j=1;j<=r;j++)
cout<<setw(3)<<a[j];
cout<<endl;
}
例5.3： 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7，有14种拆法。
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
【参考程序】
#include<bits/stdc++.h>
using namespace std;
int a[10001]={1},n,total;
int search(int ,int);//递归回溯算法
int print(int);//输出
int main(){
cin>>n;
search(n,1);//将要拆分的n传递给s
cout<<"total="<<total<<endl;//输出拆分的方案数
return 0;
}
int search(int s,int t){
int i;
for(i=a[t-1];i<=s;i++){
if(i<n){//当前数i要大于等于前1位数，且不超过n
a[t]=i;//保存当前拆分的数i
s-=i;//s减去数i，s的值将继续拆分。
if(s==0){print(t);}//当s=0时，拆分输出结果
else search(s,t+1);//当s>0时，继续递归。
s+=i;//回溯：加上拆分之前的数，以便产生所有可能的拆分。
}
}
}
int print(int t)
{
cout<<n<<"=";
for(int i=1;i<=t-1;i++)
cout<<a[i]<<"+";
cout<<a[t]<<endl;
total++;
}