回溯法回溯法有“通用的解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法是一种即带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其它祖先节点回溯。否则，进入该子树，继续按照深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题的算法称为回溯法，它是用于解组合数大的问题。
问题的解空间用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。例如对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。该解空间包含对变量的所有可能的0-1赋值。例如n=3时，其解空间是
解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶子的任一路径表示解空间中的一个元素。例如，从根节点到节点H的路径相当与解空间中的元素(1,1,1)。
回溯法的基本思想确定了解空间的组织结构后，回溯法从根节点出发，以深度优先搜索方式搜索整个解空间。回溯法以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间所有解都被遍历过为止。 回溯法解题通常包含以下三个步骤： 1.针对所给问题，定义问题的解空间；
递归回溯回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。一般函数结构如下：  1 void Bcktrack(int t) //参数t表示当前递归深度 2 { 3 if(t>n)Output(x); //遍历到解，则将解输出或其他处理 4 else 5 { 6 //f(n,t)和g(n,t)表示当前节点（扩展节点）处未搜索过的子树的起始编号和中指编号 7 for(int i=f(n,t);i<=g(n,t);i++) 8 { 9 x[t]=h(i); //h(i)表示当前节点（扩展节点）处x[i]的第i个可选值 10 if(Constarint(t)&&Bound(t)) //剪枝函数：约束函数，限界函数 11 Bcktrack(t+1); 12 } 13 } 14 }
迭代回溯采用树的非递归深度优先算法遍历算法，也可以将回溯法表示为一个非递归的迭代过程。一般函数形式如下： 1 void IterativeBacktrack(void) 2 { 3 int t=1; //t表示当前递归深度 4 while(t>0) 5 { 6 if(f(n,t)<=g(n,t)) 7 { 8 //f(n,t)和g(n,t)表示当前节点（扩展节点）处未搜索过的子树的起始编号和中指编号 9 for(int i=f(n,t);i<=g(n,t);i++) 10 { 11 x[t]=h(i); 12 if(Constraint(t)&&Bound(t)) //剪枝函数：约束函数，限界函数 13 { 14 if(Solution(t)) Output(x); //判断当前节点是否已经得到问题的可行解 15 else t++ 16 } 17 } 18 } 19 else t--; 20 } 21 }
算法复杂度用回溯法解体的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根节点到当前节点（扩展节点）的路径。如果解空间树从根节点到叶节点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。
经典例子：八皇后问题八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。 以下是n后问题的例子代码： 
1 //八皇后问题 2 3 // Queen.cpp : 定义控制台应用程序的入口点。 4 // 5 6 #include "stdafx.h" 7 #include "stdio.h" 8 9 class Queen{ //类Queen记录解空间中的节点信息 10 friend int nQueen(int); 11 private: 12 bool Place(int k); //剪枝函数 13 void Backtrack(int t); //递归函数 14 int n; //皇后个数 15 int *x; //当前解 16 long sum; //当前可行的方案数 17 }; 18 19 int abs(int ab)//求绝对值 20 { 21 return ab>0ab:-ab; 22 } 23 24 bool Queen::Place(int k) //剪枝函数 25 { 26 for(int j=1;j<k;j++) 27 { 28 //剪枝条件：如果在同一行，同一列或者同斜线上 29 if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) 30 return false; 31 } 32 return true; 33 } 34 35 void Queen::Backtrack(int t) //递归回溯核心 36 { 37 if(t>n) sum++; //如果遍历到叶子，说明求出了一个解 38 else 39 for(int i=1;i<=n;i++) 40 { 41 x[t]=i; 42 if(Place(t)) Backtrack(t+1); //函数Place为剪枝函数 43 } 44 } 45 46 int nQueen(int n)//初始化数据 47 { 48 Queen X; 49 X.n=n; 50 X.sum=0; 51 int *p=new int[n+1]; 52 for(int i=0;i<=n;i++) 53 { 54 p[i]=0; 55 } 56 X.x=p; 57 X.Backtrack(1); 58 delete []p; 59 return X.sum; 60 } 61 62 63 int _tmain(int argc, _TCHAR* argv[]) 64 { 65 printf("%d",nQueen(8));//传入参数8，即八皇后问题 66 return 0; 67 }
|
|
|
