明天就开始ZJU ACM预赛了，昨晚和队员一起做了些题，自卑不已。有一道回溯的题，我们居然一点想法也没有。故下午认真的重温了下回溯这一通用算法，下三段程序算是下午的成果吧。
回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 运用回溯法解题通常包含以下三个步骤：
- 针对所给问题，定义问题的解空间；
- 确定易于搜索的解空间结构；
- 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：
procedure try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
end;
end;
说明：
i是递归深度；n是深度控制，即解空间树的的高度；- 可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；
搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,…xi），i< n, 则添加x(i+1)属于s(i+2)。
检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、(i+2)。
若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,…x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解
例子
例1、八皇后问题
要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。
提示：皇后能吃同一行、同一列、同一对角线的任意棋子。
#include <iostream.h>
#include <math.h>
int n; // number of queens
int x; // the outcome
long sum; // the count of outcome
bool place(int k );
void backtrack(int t );
int main()
{
cin >> n;
sum = 0;
x = new int [n];
for ( int i=0; i<n; i++)
{
x[i] = 0;
}
backtrack(0);
return 0;
}
bool place(int k )
{
for ( int i=0; i<k; i++)
{
if ( abs(k-i) == abs(x[i]-x[k]) || x[i] == x[k] )
{
return false;
}
}
return true;
}
void backtrack(int t )
{
if (t >= n)
{
for ( int i=0; i<n; i++)
{
cout << x[i] << " ";
}
cout << endl << "sum:" << ++sum << endl;
}
else
{
for ( int i=0; i<n; i++)
{
x[t] = i;
if (place(t))
{
backtrack(t+1);
}
}
}
}
例2、跳马问题
在55格的棋盘上，有一个国家象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘后再条回出发点。
#include <iostream.h>
#include <iostream.h>
#include <math.h>
int n; // number of queens
int x; // the outcome
long sum; // the count of outcome
bool place(int k );
void backtrack(int t );
int main()
{
cin >> n;
sum = 0;
x = new int [n];
for ( int i=0; i<n; i++)
{
x[i] = 0;
}
backtrack(0);
return 0;
}
bool place(int k )
{
for ( int i=0; i<k; i++)
{
if ( abs(k-i) == abs(x[i]-x[k]) || x[i] == x[k] )
{
return false;
}
}
return true;
}
void backtrack(int t )
{
if (t >= n)
{
for ( int i=0; i<n; i++)
{
cout << x[i] << " ";
}
cout << endl << "sum:" << ++sum << endl;
}
else
{
for ( int i=0; i<n; i++)
{
x[t] = i;
if (place(t))
{
backtrack(t+1);
}
}
}
}
short x[] = {2,1,-1,-2,-2,-1,1,2}; //the direction
short y[] = {1,2,2,1,-1,-2,-2,-1};
int nn; //the size of square
int num = 0; //
int *horse; //dynamic array of two dimension for storing the path
void printway();
void tryway(int m, int n, int count);
int main()
{
int i, j;
cin >> nn;
horse = new int* [nn]; //apply for space
for ( i=0; i<nn; i++)
{
horse[i] = new int [nn];
}
for ( i=0; i<nn; i++)
{
for ( j=0; j<nn; j++)
{
horse[i][j] = 0;
}
}
horse[0][0] = 1; //the beginning point
tryway(0,0,2);
for ( i=0; i<nn; i++) //free the space
{
delete[] horse[i];
}
delete[] horse;
return 0;
}
void tryway(int m, int n, int count)
{
int u, v;
if ( count > nnnn)
{
printway();
return;
}
for ( int i=0; i<8; i++)
{
u = m + x[i];
v = n + y[i];
if ( u>=0 && u<nn && v>=0 && v<nn && !horse[u][v] )
{
horse[u][v] = count;
tryway(u,v,count+1);
horse[u][v] = 0;
}
}
}
void printway()
{
for ( int i=0; i<nn; i++)
{
for ( int j=0; j<nn; j++)
{
cout << " " << horse[i][j];
}
cout << endl;
}
cout << "NUM:" << ++num << endl;
}
例3：素数环
把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
〖问题分析〗
非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法： 与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。
〖算法流程〗
- 数据初始化；
- 递归填数：
- 判断第J种可能是否合法； 1. 如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个； 1. 如果不合法：选择下一种可能；
#include <iostream.h>
#include <math.h>
#include <process.h>
bool IsPrime(int t);
void backtrack(int t);
short path[20];
int main()
{
path[0] = 1;
// cout << IsPrime(9);
backtrack(2);
return 0;
}
bool IsPrime(int t)
{
if (t==0 || t==1)
{
return false;
}
for (int i=2; i<=sqrt(t); i++ )
{
if (t%i == 0 )
{
return false;
}
}
return true;
}
void backtrack(int t)
{
int i,j;
bool IsValid;
for (i=2; i<21; i++)
{
IsValid = true;
for (j=1; j<t-1; j++)
{
if (path[j] == i)
{
IsValid = false;
break;
}
}
if (IsValid && IsPrime(i+path[t-2]))
{
if (t == 20)
{
if (IsPrime(i+path[0])) //get the outcome,print the result
{
path[t-1] = i;
static long count = 0;
for (i=0; i<20; i++)
{
cout << " " << path[i];
}
cout << "\nCOUNT:" << ++count << endl;
exit(0); //if remove this line,you can get all outcome.
return;
}
}
else
{
path[t-1] = i;
backtrack(t+1);
}
}
}
}
#include <iostream.h>
//#define MAX 10
short x[] = {2,1,-1,-2,-2,-1,1,2}; //the direction
short y[] = {1,2,2,1,-1,-2,-2,-1};
int nn; //the size of square
int num = 0; //
int *horse; //dynamic array of two dimension for storing the path
void printway();
void tryway(int m, int n, int count);
int main()
{
int i, j;
cin >> nn;
horse = new int* [nn]; //apply for space
for ( i=0; i<nn; i++)
{
horse[i] = new int [nn];
}
for ( i=0; i<nn; i++)
{
for ( j=0; j<nn; j++)
{
horse[i][j] = 0;
}
}
horse[0][0] = 1; //the beginning point
tryway(0,0,2);
for ( i=0; i<nn; i++) //free the space
{
delete[] horse[i];
}
delete[] horse;
return 0;
}
void tryway(int m, int n, int count)
{
int u, v;
if ( count > nn*nn)
{
printway();
return;
}
for ( int i=0; i<8; i++)
{
u = m + x[i];
v = n + y[i];
if ( u>=0 && u<nn && v>=0 && v<nn && !horse[u][v] )
{
horse[u][v] = count;
tryway(u,v,count+1);
horse[u][v] = 0;
}
}
}
void printway()
{
for ( int i=0; i<nn; i++)
{
for ( int j=0; j<nn; j++)
{
cout << " " << horse[i][j];
}
cout << endl;
}
cout << "NUM:" << ++num << endl;
}