回溯法
所谓”搜索“是指利用计算机的高性能有目的地穷举一个问题的部分或所有的解（候选解），然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到满足某种条件所需要的解。
回溯法的基本概念
回溯和分枝定界是目前搜索算法中比较常用的两种控制策略。通过它们可以避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，回溯和分枝定界法都能够用来求规模很大的问题。回溯是所有基本搜索算法中最为基本的一种算法，采用”走不通就掉头“思想作为其控制结构。基于回溯机制的搜索相当于树的先根遍历，可用于求一个可行解、求所有解、甚至求最优解。
回溯法也称为试探法，它首先暂时放弃关于问题规模大小的限制，并将问题的候选解按照某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外，已能满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以便继续进行试探的过程称为向前试探。
eg：老鼠走迷宫问题。
回溯法的基本思想
为了实现回溯，首先需要为问题定义一个解空间，这个空间必须至少包含问题的一个解（可能是最优的）。然后，先选择某一种可能情况向前搜索，在搜索过程中，一旦发现原来的选择不优或不能达到目标，就退回上一步重新选择，并继续向前搜素。如此反复进行，直至得到解或证明无解。
实际运用中，当把问题的解空间组织成一颗树结构时，回溯法对树的搜索过程类似于图的深度优先搜索。它先从根结点开始出发，以深度优先方式搜索整个解空间。回溯法适用于求解一些组合数较大的问题。
回溯法求解问题的步骤：
（1）确定问题的解空间
为实现回溯，首先需要为问题定义一个解空间，该空间必须至少包含问题的一个解（可能是最优的）。例如走迷宫老鼠问题中，可以定义一个包含从入口到出口的所有路径的解空间。问题的解空间通常是在搜索问题的解的过程中动态产生的。
（2）按照易于搜索的策略组织解空间结构
当定义好问题的解空间后，应该将解空间很好的组织起来，使得能用回溯法方便地搜索整个解空间，通常将解空间组织成树或图的形式。
（3）以深度优先方式搜索解空间
在搜索解空间时，通常采用两种策略避免无效搜索。一种是约束函数在扩展点处剪除不满足约束的子树；二是用限定函数剪去得不到最优解的子树。这两类函数称为剪枝函数（也称为约束函数），这里剪枝函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，剪枝函数是对于解空间树上的任何一个节点都是有效和等价的。
由于深度优先搜索是将路径逐一求出的，通过在求路径的过程中去除不合法节点即可省去求所有子节点所花费的时间。因此，回溯法是对解空间搜索一般都采用深度优先搜索法。
在回溯法中，一般采用非递归方法对解空间实施搜索，这主要通过采用栈结构来实现。此时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和实现回溯过程。
回溯法通常在解空间树上进行搜索，而解空间树通常有子集树和排列树。针对两个问题，算法的框架有2种：搜索子集合框架和搜索排列问题。
框架一：搜索子集合，用回溯法搜索子集合树的一般框架。
void backtrack(int t) {
if(t>n) output(x);
else {
for(int i=f(n,t);i<=g(n,t);i++) {
x[t]=h(i);
if(constraint(t)&& bound(t)) backtrack(t+1);
}
}
}
框架二：搜索排列，用回溯法搜索排列树的一般框架。
void backtrack(int t) {
if(t>n) output(x);
else {
for(int i=f(n,t);i<=g(n,t);i++) {
swap(x[t],x[i]);
if(constraint(t)&&bound(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
}
其中f(n,t)，g(n,t)表示当前扩展结点处未搜索过的子树的起始标号和终止标号，h(i)表示当前扩展结点处，x[t]第i个可选值。constraint(t)和bound(t)是当前扩展结点处的约束函数和界限函数。constraint(t)返回true时，在当前扩展结点x[1:t]取值满足约束条件，否则不满足约束条件，可减去相应的子树。bound(t)返回的值为true时，在当前扩展结点x[1:x]处取值未使目标函数越界，还需由backtrack(t+1)对其相应的子树进一步搜索。
用回溯法其实质上提供了搜索解空间的方法，当能够搜索解遍解空间时，就能够找到最优解的或者满足条件的解，效率可以通过剪枝函数来提高。但是，一旦解空间的结构确定，很大程度上时间复杂度也就确定了，所以选择易于搜索的解空间很重要。
回溯法应用举例：
小老鼠走迷宫问题。
二维数组M*N表示迷宫，使用1表示墙，即老鼠无法从此通行，使用0表示可以通行。迷宫中，老鼠走法有上下左右4个方向，在每前进一格之后就选一个方向前进，无法前进就退回刚走过的位置并选择下一个前进的方法，如此在二维数组阵列中依次测试4个方向，直到走出出口为止。
使用栈记录走过的每一步，如果走不通，就回溯，让走过的路点出栈，直到找到上一次分支点。
#include<iostream> using namespace std; #define Maxsize 100 #define N 10 #define M 10 int mg[M+1][N+1]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,0,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,1,1,1,1,0,1,1,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; class stac { public: int i;//表示迷宫的行与列 int j; int dir;//标识哪些已经被找过的路径 }; stac stack[Maxsize]; int top=-1;//栈的指针 void Maze() { int ii,jj,di,find; top++; stack[top].i=1; stack[top].j=1; stack[top].dir=-1; mg[1][1]=-1; while(top>-1) { ii=stack[top].i;//当前位置的行与列 jj=stack[top].j; di=stack[top].dir;//位置0 1 2 3表示上右下左 if(ii==M-2 && jj==N-2) {//到了目的地 cout<<"迷宫通路："<<endl; for(int k=0;k<=top;k++) { cout<<"("<<stack[k].i<<","<<stack[k].j<<")";//将存储在栈中的位置输出 if((k+1)%5==0) cout<<endl; } cout<<endl; return; cout<<endl; } find=0;//还没有发现目的地 while(di<4 && find==0) {//循环四面的方块看看哪个是0 di++; switch(di) { case 0:ii=stack[top].i-1; jj=stack[top].j; break;//上 case 1:ii=stack[top].i; jj=stack[top].j+1; break;//右 case 2:ii=stack[top].i+1; jj=stack[top].j; break;//下 case 3:ii=stack[top].i; jj=stack[top].j-1; break;//左 } if(find==1) {//找到就进栈 stack[top].dir=di; top++; stack[top].i=ii;//行 stack[top].j=jj; cout<<"进栈：("<<ii<<","<<jj<<","<<di<<")"<<endl; stack[top].dir=-1; } else { cout<<"出栈："<<stack[top].i<<","<<stack[top].j<<endl; mg[stack[top].i][stack[top].j]=0; top--; } } cout<<"没有路可走"<<endl; } } int main() { Maze(); return 0; }
此处的测试结果与书上不同！！！
个人感觉这种迷宫问题没有《啊哈！算法》中的迷宫问题简单好懂！
http://blog.csdn.net/wangdd_199326/article/details/70473581