目录

• 搜索与回溯算法
  •   迷宫问题：
  • 例5.1素数环：将1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
  • 例5.2：设有n个整数的集合｛1,2，……，n｝，从中任意取出r个数进行排列（r
  • 例5.3： 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

搜索与回溯算法

搜索与回溯是计算机解题过程中常用的算法，很多问题无法根据某种确定的计算机法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

迷宫问题：

进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走。这时，首先看其他方向是否还有路可走：如果有，则沿该方向再次向前试探；否则退回一步，再看其他方向是否还有路可走。按此原则下不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

递归回溯算法框架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++;	}