概述
定义
在程序设计中，有相当一类求一组解，或求全部解或求最优解的问题，例如读者熟悉的八皇后问题，不是根据某种特定的计算法则，而是利用试探和回溯的搜索技术求解。回溯法也是设计递归过程的一种重要方法，它的求解过程实质上是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。
---《数据结构》(严蔚敏)
怎么理解这段话呢？
首先，某种问题的解我们很难去找规律计算出来，没有公式可循，只能列出所有可能的解，然后一个个检查每个解是否符合我们要找的条件，也就是通常说的遍历。而解空间很多是树型的，就是树的遍历。
其次，树的先序遍历，也就是根是先被检查的，二叉树的先序遍历是根，左子树，右子树的顺序被输出。如果把树看做一种特殊的图的话，DFS就是先序遍历。所以，回溯和DFS是联系非常紧密的，可以认为回溯是DFS的一种应用场景。另外，DFS有个好处，它只存储深度，不存储广度。所以空间复杂度较小，而时间复杂度较大。
最后，某些解空间是非常大的，可以认为是一个非常庞大的树，此时完全遍历的时间复杂度是难以忍受的。此时可以在遍历的同时检查一些条件，当遍历某分支的时候，若发现条件不满足，则退回到根节点进入下一个分支的遍历。这就是“回溯”这个词的来源。而根据条件有选择的遍历，叫做剪枝或分枝定界。
DFS
首先看DFS，下面是算法导论上DFS的伪代码，值得一行行的去品味。需要注意染色的过程，因为图有可能是有环的，所以需要记录那些节点被访问过了，那些没有，而树的遍历是没有染色过程的。而且它用 π[m]来记录m的父节点，也就可以记录DFS时的路径。
DFS(G)1 for each vertex u ∈ V [G]
2 do color[u] ← WHITE
3 π[u] ← NIL
4 time ← 0
5 for each vertex u ∈ V [G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)
DFS-VISIT(u)
1 color[u] ← GRAY
2 time ← time +1
3 d[u] <-time
4 for each v ∈ Adj[u]
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] <-BLACK
例子
例一：求幂集问题，就是返回一个集合所有的子集。为什么叫幂集呢？因为一个集合有n个元素，那么它的所有的子集数是2^n个。比如[1,2,3]的子集是[]，[1]，[2]，[3]，[1,2]，[1,3]，[2,3]，[1,2,3]。
也就是下面这棵树的叶子节点：
那问题就变成了如何输出一棵树的叶子节点。那就需要知道现在到底遍历到哪一层了。方法有很多，可以用全局变量记录，也可以用递归函数的参数记录。
A）这里是用全局变量记录，在进入函数的时候level++，退出函数的时候level--
int level=0;
vector<vector<int> > result;
vector<int> temp;
void dfs(vector<int>& S){
level++;
if(level>S.size()){
result.push_back(temp);
level--;
return;
}
temp.push_back(S[level-1]);
dfs(S);
temp.pop_back();
dfs(S);
level--;
return;
}
vector<vector<int> > subsets(vector<int>& S){
sort(S.begin(),S.end());
dfs(S);
reverse(result.begin(),result.end());
return result;
}
B）这里记录层数用的是函数参数
vector<vector<int> > result;
vector<int> temp;
void dfs(vector<int>& S, int i){
if(i==S.size()){
result.push_back(temp);
return;
}
temp.push_back(S[i]);
dfs(S,i+1);
temp.pop_back();
dfs(S,i+1);
return;
}
vector<vector<int> > subsets(vector<int>& S){
dfs(S,0);
reverse(result.begin(),result.end());
return result;
}
总结一下，伪代码就是：
void dfs(层数){
if(条件){
输出；
}
else{
左子树的处理；
dfs(层数+1)；
右子树的处理；
dfs(层数+1)；
}
}
例二：皇后问题，比如8*8的棋盘，能摆放多少个皇后呢？国际象棋规则，皇后在同一行，同一列，同一斜线均可互相攻击。
伪代码如下：int a[n];
void try(int i)
{
if(i==n){
输出结果;
}
else
{
for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
{
if(fun(j)) // 满足限界函数和约束条件
{
a[i] = 1;
... // 其他操作
try(i+1);
a[j] = 0;
}
}
}
}
void dfs(int level){
if(level==N){
output();
}
else{
for(int i=0;i<N;i++){
if(check(level+1,i+1)){
m[level][i]=1;
dfs(level+1);
m[level][i]=0;
}
}
}
}
完整代码：
int N;
vector<vector<int> > m;
vector<vector<string> > result;
bool check(int row,int column){
if(row==1) return true;
int i,j;
for(i=0;i<=row-2;i++){
if(m[i][column-1]==1) return false;
}
i = row-2;
j = i-(row-column);
while(i>=0&&j>=0){
if(m[i][j]==1) return false;
i--;
j--;
}
i = row-2;
j = row+column-i-2;
while(i>=0&&j<=N-1){
if(m[i][j]==1) return false;
i--;
j++;
}
return true;
}
void output()
{
vector<string> vec;
for(int i=0;i<N;i++){
string s;
for(int j=0;j<N;j++){
if(m[i][j]==1)
s.push_back('Q');
else
s.push_back('.');
}
vec.push_back(s);
}
result.push_back(vec);
}
void dfs(int level){
if(level==N){
output();
}
else{
for(int i=0;i<N;i++){
if(check(level+1,i+1)){
m[level][i]=1;
dfs(level+1);
m[level][i]=0;
}
}
}
}
vector<vector<string> > solveNQueens(int n) {
N=n;
for(int i=0;i<n;i++){
vector<int> a(n,0);
m.push_back(a);
}
dfs(0);
return result;
}例三： 数独问题，就是给出一个数独，解决它。
比如给出：
求解：
解空间是这样的：
由于数独都是9*9的，所以解空间有81层，每层有9个分支，我们做的就是遍历这个解空间。
如果只求一个解，那我们可以在得到解之后返回，而标记是否得到解可以用全局变量或返回值来做，
用全局变量的话，代码如下：
bool flag= false;
bool check(int k, vector<vector<char> > &board){
int x=k/9;
int y=k%9;
for (int i = 0; i < 9; i++)
if (i != x && board[i][y] == board[x][y])
return false;
for (int j = 0; j < 9; j++)
if (j != y && board[x][j] == board[x][y])
return false;
for (int i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
for (int j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
if (i != x && j != y && board[i][j] == board[x][y])
return false;
return true;
}
void dfs(int num,vector<vector<char> > &board){
if(num==81){
flag=true;
return;
}
else{
int x=num/9;
int y=num%9;
if(board[x][y]=='.'){
for(int i=1;i<=9;i++){
board[x][y]=i+'0';
if(check(num,board)){
dfs(num+1,board);
if(flag)
return;
}
}
board[x][y]='.';
}
else{
dfs(num+1,board);
}
}
}
void solveSudoku(vector<vector<char> > &board) {
dfs(0,board);
} bool f(int i, vector<vector<char> > &board){
if(i==n*m)
return true;
if(board[i/n][i%m]=='.'){
for(int k=1;k<=9;k++){
board[i/n][i%m]=k+'0';
if(check(i,board) && f(i+1,board))
return true;
}
board[i/n][i%m]='.';
return false;
}
else
return f(i+1,board);
}要求得到所有解的话，可以在解出现的时候存下来：
vector<vector<vector<char> >> sum;
bool check(int k, vector<vector<char> > &board){
int x=k/9;
int y=k%9;
for (int i = 0; i < 9; i++)
if (i != x && board[i][y] == board[x][y])
return false;
for (int j = 0; j < 9; j++)
if (j != y && board[x][j] == board[x][y])
return false;
for (int i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
for (int j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
if (i != x && j != y && board[i][j] == board[x][y])
return false;
return true;
}
void dfs(int num,vector<vector<char> > &board){
if(num==81){
sum.push_back(board);
return;
}
else{
int x=num/9;
int y=num%9;
if(board[x][y]=='.'){
for(int i=1;i<=9;i++){
board[x][y]=i+'0';
if(check(num,board)){
dfs(num+1,board);
//if(flag)
//
return;
}
}
board[x][y]='.';
}
else{
dfs(num+1,board);
}
}
}
void solveSudoku(vector<vector<char> > &board) {
dfs(0,board);
}
int main()
{
vector<string> myboard({"...748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."});
vector<char> temp(9,'.');
vector<vector<char> > board(9,temp);
for(int i=0;i<myboard.size();i++){
for(int j=0;j<myboard[i].length();j++){
board[i][j]=myboard[i][j];
}
}
solveSudoku(board);
for(int k=0;k<sum.size();k++){
for(int i=0;i<sum[k].size();i++){
for(int j=0;j<sum[k][i].size();j++){
cout<<sum[k][i][j]<<" ";
}
cout<<endl;
}
cout<<"######"<<endl;
}
cout<<"sum is "<<sum.size()<<endl;
cout << "Hello world!" << endl;
return 0;
}最终，我们得到了8个解。
wiki上有一张图片形象的表达了这个回溯的过程：
最后
以上就是精明荔枝为你收集整理的彻头彻尾的理解回溯算法的全部内容，希望文章能够帮你解决彻头彻尾的理解回溯算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复