算法篇之回溯法
算法篇之回溯法
--细说回溯法（细说不是胡说）
前言
最近因为复试的原因，对几个算法进行了一定程度的了解，这一篇将详细讲述一下回溯，让大家浅显易懂的明白回溯。
一、什么是回溯法
官方解释：回溯法是一个既带有系统性又带有跳跃性的搜索算法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
通俗来讲：回溯思想其实就是试探思想，有时候我们需要得到问题的解，先从其中某一种情况进行试探，在试探的过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择，然后继续向前试探，反复这样的过程直到求解出问题的解。
二、回溯法模型设计
回溯法一般都有固定的形式，下面给出一般形式
void Trial(ElemType r,......)
{
if(当前所得解r为所求)
输出当前解;
else
{
//前序遍历解空间树
for(i=1;i<=n;i++)
{
//n为解空间的维数
将当前解r在第i维修改;//设置环境
if(修改后的r合法)//需要剪枝
Trial(r);
将r恢复为未修改;//恢复环境【回溯】
}
}
}
例：假设二叉树采用二叉链存储结构存储，试设计一个算法，输出从每个叶子结点到根结点的路径。
三、常见的回溯算法的分类
根据多元素解中第一个元素是否固定，将回溯算法分为两类。一类是有固定起始点的回溯问题，另一类是任意一个元素都可作为起始结点的回溯问题。
1.有固定的起始点
（1）假设二叉树采用二叉链表存储结构存储，试设计一个算法，输出该二叉树中第一条最长的路径长度，并输出此路径上个结点的值。
void LongPath(BTNode *p,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen)
{
int i;
if(p==NULL)
{
if(pathlen>longpathlen)
{
for(int i=pathlen-1;i>=0;i--)
longpath[i]=path[i];
longpathlen=pathlen;
}//此部分为多元素解的处理过程
}
else
{
path[pathlen]=p->data;
pathlen++;//设置环境
LongPath(p->lchild,path,pathlen,longpath,longpathlen);
LongPath(p->rchild,path,pathlen,longpath,longpathlen);
pathlen---;//恢复环境
}
}
（2）假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
int visited[maxsize];
int path[maxsize];
void printAllPath(AGraph *g,int vi,int vj,int d,int L)
{
EdgeNode *p;int i;
if(vi==vj&&d==L)
{
cout<<"一条路径:";
for(i=0;i<=d;i++)
cout<<path[i]<<" ";
}
else
{
++d;
path[d]=vi;
p=g->adjList[vi]->firstEdge;
while(p!=NULL)
{
if(visited[p->adjvex==0])
printAllPath(g,p->adjvex,vj,d,L);
p=p->next;
}
visited[vi]=0;
--d;
}
}
（3）洞穴探宝问题：有一幅藏宝图，设计一个算法要求从入口到出口，并且必须经过“食品”和“财宝”的地方，不得经过“强盗”的地方。
int visited[maxsize];
int path[maxsize];
int d=-1;
int cond(int v1,int v4,int v6)
{
int flag1=0,flag2=0,flag3=1,i;
for(i=0;i<=d;i++)
{
if(path[i]==v1)
{
flag1=1;//此路径经过了食品
break;
}
}
for(i=0;i<=d;i++)
{
if(path[i]==v6)
{
flag2=1;//此路径经过了财宝
break;
}
}
for(i=0;i<=d;i++)
{
if(path[i]==v4)
{
flag3=0;//此路径经过了强盗
break;
}
}
return flag1&&flag2&&flag3;
}
void printPath(AGraph *g,int vi,int vj,int v1,int v4,int v6)
{
EdgeNode *p;int i;
if(vi==vj&&cond(v1,v4,v6))
{
for(i=0;i<=d;i++)
cout<<path[i]<<" ";
}
else
{
++d;
path[d]=vi;
visited[vi]=1;
p=g->adjLsit[i]->firstedge;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
printPath(g,p->adjvex,vj,v1,v4,v6);
p=p->next;
}
visited[vi]=0;
--d;
}
}
2.任意一个元素都可作为起始点
在这类问题中，集合中的每个元素均可以作为解中的第一个元素，排列、组合问题中任一元素均可作为某一解的第一个元素，八皇后问题中某皇后可放在八个位置中的任意一个，四染色问题中某一图形可选用任意一种颜色。这时在回溯过程中要用到for结构，将每个元素换到起始位置，即作为第一个元素。换位后处理方式都一样，所以要用到for来进行代码简化处理。
（1）全排列问题：输入n个不同的字符串，给出它们所有的n个字符的全排列。
void perm(char str[],int k,int n)
{
int i;
char temp;
if(d==n-1)
{
for(i=0;i<d;i++)
cout<<str[i]<<" ";s
cout<<endl;
}
for(i=d;i<n;i++)
{
temp=str[d];//对于k~n-1的i，交换str[i]<<=>>str[k]
str[d]=str[i];
str[i]=temp;
perm(str,d+1,n);//求出k~n-1的全排列
temp=str[i];//k回到原来位置
str[i]=str[d];
str[d]=temp;
}
}
（2）组合问题：从自然数1,2,...,n中任取k个数的所有组合
void combi(int str[],int d,int boundary,int k,int n)
{
int i;
int temp;
if(d==k)
{
for(i=0;i<k;i++)
cout<<str[i]<<" ";
cout<<endl;
}
for(j=boundary;j<=n;j++)
{
temp=str[boundary];
str[boundary]=str[j];
combi(str,d+1,j+1,k,n);
str[boundary]=temp;
}
}
（3）八皇后问题：要求在一个8*8的棋盘上放置8个皇后（问题也可推广到n*n的棋盘上放置n个皇后），使得它们彼此不受攻击。一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何其他棋子。
分析：此题用回溯法解决，由于每个皇后有可能放在1到n中的任何一列，所以是第二类回溯问题。
a.解的表示形式:问题的解可表示为x[1:n]，表示皇后i放在棋盘的第i行的第x[i]列。
b.剪枝条件：要找出“八皇后”问题的解，最可靠的方法就是把各种情况全部检核一遍，将符合条件的解找出来。但这样做，你要有相当耐心才行，这是很费时的。应该在搜索的过程中，将不满足条件要求的分支树减去，可以有效的降低算法的时间复杂性。剪枝条件如下：
x[i]≠x[j],i≠j : 不允许将任何两个皇后放在同一列上；
|j-i|≠x[j]-x[i] : 不允许两个皇后位于同一斜线上。
//定义冲突判定函数如下
int noCollision(int k)//冲突判定函数，判定皇后k与前k-1个皇后是否有冲突
{
int j=1;
while(j<k)
{
if((x[j]==x[k])||(abs(x[j]-x[k])==abs(j-k)))
return 0;
j++;
}
return 1;
}
//求八皇后问题的所有解决方案算法如下
void placeQueen(int k,int n)
//n表示总共的皇后个数，k表示当前放置的皇后序号。初始调用时place(1,8)
{
if(k>n)
print(n);//多元素解的输出
else
{
for(int i=1;i<=n;i++)
{
x[k]=i;//设置环境
if(noCollision(k))//剪枝
placeQueen(k+1,n);//试探第k+1个皇后的位置
x[k]=0;//恢复环境
}
}
}
四、回溯例题求解
1.素数环
题目描述:
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
输入描述:
有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。
输出描述:
每组第一行输出对应的Case序号，从1开始。 如果存在满足题意叙述的素数环，从小到大输出。 否则输出No Answer。
样例输入:
6 8 3 0
样例输出:
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 Case 3: No Answer
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#define maxsize 22
using namespace std;
int a[maxsize];
int vis[maxsize];
int n;
int flag=0;
int sum=1;
//判断素数
int is_prime(int k)
{
if(k==0||k==1)
return 0;
for(int i=2;i<=sqrt(k);i++)
if(k%i==0)
return 0;
return 1;
}
//回溯遍历
void dfs(int cur)
{
int i;
if(cur==n&&is_prime(a[0]+a[cur-1]))
{
flag=1;
for(i=0;i<n;i++)
{
cout<<a[i];
if(i==n-1)
cout<<endl;
else
cout<<" ";
}
return;
}
else
{
for(i=2;i<=n;i++)
{
if(!vis[i]&&is_prime(i+a[cur-1]))
{
vis[i]=1;
a[cur]=i;
dfs(cur+1);
vis[i]=0;
}
}
}
}
int main()
{
while(cin>>n)
{
if(n==0)
break;
flag=0;
memset(vis,0,sizeof(vis));
a[0]=1;
vis[1]=1;
cout<<"Case "<<sum++<<":"<<endl;
if(n==1)
cout<<"1"<<endl;
else if(n%2==1)//奇数时没有答案
cout<<"No Answer"<<endl;
else
{
dfs(1);
if(flag==0)
cout<<"No Answer"<<endl;
}
}
return 0;
}
2.排列组合
题目描述:
小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。
输入描述:
第一行输入整数N（1<N<10）表示多少组测试数据， 每组测试数据第一行两个整数 n m (1<n<9,0<m<=n)
输出描述:
在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例
样例输入:
2 3 1 4 2
样例输出:
1 2 3 12 13 14 21 23 24 31 32 34 41 42 43
#include<iostream>
#include<algorithm>
#define maxsize 10
using namespace std;
int a[maxsize];
int vis[maxsize]={0};
int sum=0;
int n,r;
void dfs(int cur)
{
int i;
if(cur==r+1)
{
sum++;
for(i=1;i<cur;i++)
cout<<a[i];
cout<<endl;
}
else
{
for(i=1;i<=n;i++)
{
if(vis[i]==0)
{
vis[i]=1;
a[cur]=i;
dfs(cur+1);
vis[i]=0;
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
cin>>r;
dfs(1);
}
return 0;
}
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<iostream>
#define maxsize 100001
using namespace std;
int a[maxsize]={1};
int sum=0;
int n;
void print(int cur)
{
sum++;
cout<<n<<"=";
for(int i=1;i<cur;i++)
cout<<a[i]<<"+";
cout<<a[cur]<<endl;
}
void dfs(int s,int cur)
{
for(int i=a[cur-1];i<=s;i++)
{
if(i<n)
{
a[cur]=i;
s-=i;
if(s==0)
print(cur);
else
dfs(s,cur+1);
s+=i;
}
}
}
int main()
{
cin>>n;
dfs(n,1);
cout<<"sum="<<sum<<endl;
return 0;
}