一、回溯算法的定义：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：
1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
下面通过一个具体实例加深大家对回溯算法的认识。 二、回溯算法的应用举例：
例1：马的遍历
中国象棋半张棋盘如图1(a)所示。马自左下角往向右上角跳。规定只许往右跳，不许往左跳，马只能走日字。比如图1(a)所示为一种跳行路线，并将所经路线打印出来，打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8。找出所有路径。
【算法分析】
如图1（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：
1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略：
S1:Ａ[１]:=(0,0);
S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下
一个到达的顶点；
S3:打印路径。 【算法设计】 #include
using namespace std; int a[100][100],t=0; int x[4]={2,1,-1,-2}, y[4]={1,2,2,1}; int search(int); int print(int); int main() {
a[1][1]=0;a[1][2]=0; search(2);
system(\}
int search(int i) {
for(int j=0;j<=3;j++)
if(a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4&&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]<=8) {
a[i][1]=a[i-1][1]+x[j]; a[i][2]=a[i-1][2]+y[j];
if(a[i][1]==4&&a[i][2]==8) print(i); else search(i+1); } }
int print(int ii) { {
t++;
cout< for(int i=1;i<=ii-1;i++) cout< 例2：选书 学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。 输出结果： zhang: C wang: A liu: B sun: D li: E 【算法分析】 可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5！=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。 为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，??，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。 【算法设计】 S1：产生5个数字的一个全排列； S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来； S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1； S4：结束。 上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同学的书，1 是不可能的，因为张只喜欢第3、4 本书。这就是说，1××××一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少3/5的运算量。同理，选定了第一个数字后，也不应该把其他4个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。 综上所述，改进后的算法应该是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用回溯算法。算法设计如下： procedure try(i); begin for j:=1 to 5 do begin if 第i 个同学分给第j本书符合条件 then begin 记录第i 个数 if i =5 then 打印一个解 else try(i+1); 删去第i 个数字 end; end; end; 【参考程序】 #include flag[6],like[6][6]={{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,0,0,1},{0,0,1,1,0,0}, {0,0,0,0,1,0},{0,0,1,0,0,1}};; int search(int); int print(); int main() { for(int i=1;i<=5;i++) flag[i]=1; search(1); system(\} int search(int i) { for(int j=1;j<=5;j++) if(flag[j]&&like[i][j]) { flag[j]=0; book[i]=j; if(i==5) print(); else search(i+1); flag[j]=1; book[i]=0; } } int print() { c++; cout<<\ for(int i=1;i<=5;i++) cout< 例3：八皇后问题 【问题描述】 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相\冲\（在每一横列竖列斜列只有一个皇后）。 【问题分析】 这道题可以用回溯算法来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题： 1、冲突。包括行、列、两条对角线： （1）列：规定每一列放一个皇后，不会造成列上的冲突； （2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； （3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2、数据结构。 （1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8 （2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8 （3）对角线冲突标记数组C、D。 C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7 D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16 【算法流程】 １、数据初始化。 ２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领），如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。 ３、当n>8时，便一一打印出结果。 【参考程序】 #include bool d[100]={0},b[100]={0},c[100]={0}; int sum=0,a[100]; int print() { int i; sum++; cout<<\ for(i=1;i<=8;i++) cout< int main() { search(1); system(\} 例4、自然数拆分 【问题描述】输入自然数n，然后将其拆分成若干数相加的形式，参与加法运算的数可以重复。 输入：待拆分的自然数n 输出：若干数的加法式子 【样例输入】 5 【样例输出】 5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3 【问题分析】 算法分析：等式中后一个数必须大于等于前一个数，因为这个可以1、避免重复2提高效率我们用一个数组a[i]来记录拆分的数字，用b[i]记录剩下的数字。K记录第几个拆分的