回溯算法基础---皇后问题，骑士游历，迷宫求解

        回溯法（又叫试探法）是属于穷举的子集，对于许多的问题，当我们需要找到某些解集或者满足某种要求的最优解的时候，回溯法往往是很朴素和简单的一种算法。从数学的角度来说，比较适合一些组合数较大的问题，比如五子棋博弈算法，最短路径（最小代价）等，使用回溯算法往往会得到正确的答案，但是回溯算法由于是采用穷举的方式，所以运行时间一般是很大的，当然可以通过各种优化手段来降低，而许多的问题--------回溯法是最合适（有可能是唯一）的解决方式。

 基本概念

比如n = 3时，0-1背包问题解空间

约束条件：有效解的要求

限界函数：得不到最优解的结点

扩展节点：当前正在产生子结点的结点称为扩展结点

活结点：一个已经被生成的但是还没有生成自己全部子节点的结点

死结点：生成了所有子结点的结点

子集树：当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。

排列树：当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。

回溯法基本思想

（1）针对具体问题，定义问题的解空间（其中至少包含一个（最优）解）。

（2）确定易于所搜的解空间结构，使得能用回溯法方便地搜索整个解空间。（数据结构的选择）

（3）一般以深度优先(DFS)的方式搜索解空间，并且在搜索过程中使用剪枝函数来避免无效的搜索。

回溯法最重要的特点是解空间是在搜索问题的过程中动态产生的。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

一般解空间

1.子树集：比如背包问题，八皇后问题，骑士游历，迷宫求解等

2.排列树：比如旅行售货问题，作业调度等问题

一般提高效率的方法是：

1）约束函数：减去不满足约束的子树

2）限界函数：剪去得不到最优解的子树

一般搜索的方式：递归搜索生成树，非递归迭代

回溯基本框架

1）回溯法（递归）搜索子树集

void search(相关参数)

{

If(搜索到最底层)

打印出结果解;

Else for(遍历当前层解)

{

If(合适解)继续搜索;

撤消当前状态的影响;//回溯

}

} 

2）回溯法（递归）搜索排列树

由于排序树一般可能会涉及到辅助存储，具体的模型需要具体的问题（后面会讨论）

对于回溯法，一般只会保存当前扩展节点到根的路径（用于回溯），而不能将解空间（状态树）存储，如果是五子棋算法，递归16层，存储将达到不可思议的数量级（后面具体计算）。所以才会使用深度优先（DFS）搜索，有时也会使用广度优先（BFS），但是广度优先需要辅助空间支持，而有时候这个辅助空间也会相当的大，所以，在回溯法中，使用做多的还是深度优先搜索。

回溯法应用

1.八皇后问题

               八皇后问题解空间：N叉树子树集

               复杂度：O(Σ(N^i))    i < N 

代码：

#include<stdio.h>void outResult();
void setChessPliece(int i, int j);
int isReasonble(int i, int j);
void recall(int i, int j);int chessboard[8][8];
int const width = 8;//本函数的功能是为第i行选择合适的位置（符合皇后问题的解）
void Trial(int i,int n)
{int j = 0;//其中i是矩阵的第i行，n是矩阵的宽度/** 当i大于n的时候，说明整个皇后问题的一个有效解产生了，* 由于每一层都会进行检测，所以到最后一层一定是有效解*/if(i >= n){outResult();}else for(j = 0; j < n; j++)	//如果不是解，就继续对当前行的所有列元素进行搜索{setChessPliece(i,j);	//放置棋子/** 判断放置的棋子是否合理，相当于剪枝(去掉不满足约束条件)，去掉没有意义的搜索空间*/if(isReasonble(i,j)){/** 如果当前棋子合理，那么继续进行深度优先遍历*/Trial(i + 1,n);}//回溯当前棋子对棋型造成的影响recall(i,j);}}void outResult()
{int i,j;for(i = 0; i < width; i++){for(j = 0; j < width; j++){printf("%d ",chessboard[i][j]);}printf("\n");}printf("\n\n");return ;
}void setChessPliece(int i, int j)
{if(i >= width || j >= width || i < 0 || j < 0)return -1;chessboard[i][j] = 1;return ;
}int isReasonble(int i, int j)
{/*** 对棋子所在的位置进行3个方向的搜索，判断是否存在与* 在同一条线的棋子*/int x = i, y = j;//向上搜索判断while(x >= 0){x--;if(x < 0)break;if(chessboard[x][y] == 1){return 0;}}//向左上搜索判断x = i;while(i >= 0 && j >= 0){x--;y--;if(x < 0 || y < 0)break;if(chessboard[x][y] == 1){return 0;}}//向右上搜索判断x = i;y = j;while(x >= 0 && y < width){x--;y++;if(x < 0 || y >= width)break;if(chessboard[x][y] == 1){return 0;}}//如果都没有返回就表示这个点是合理的return 1;
}void recall(int i, int j)
{if(i >= width || i < 0 || j >= width || j < 0)return -1;chessboard[i][j] = 0;return ;
}int main()
{Trial(0,width);return 0;
}

2.骑士游历问题

由于骑士（中国象棋中的马）走日字，所以在每一个扩展结点有两种选择，要么选择走竖"日",或者走横"日，结合具体的问题可能会有四种走法，但是可以给定约束条件使得效率更高（这样会减少一些解），规定只能向右走，所以抽象一下骑士游历就是一个四叉树的搜索过程。

伪码如下：

//整体采用一个二维数组来存储
void knight(int i,int j) //其中i和j是当前扩展结点的坐标
{if(是目标结点)输出路径;else for(当前节点的另一个子结点){设置下一个扩展结点;if(符合约束条件)knight(下一个结点的坐标);回溯;}}

参考资料：《数据结构》--严蔚敏C语言版