算法之回溯算法

68 阅读 0 评论 45 点赞

我是靠谱客的博主天真短靴，最近开发中收集的这篇文章主要介绍算法之回溯算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

回溯算法的核心就是迭代，本质上并没有区别。相比较“回溯法”这个名字，我觉得“嗅探法”这个命名对于回溯算法更有描述性，即像一只小动物那样，走一步，嗅探一下，再向“正确”的方向移动，再进行嗅探，直到走到终点。回溯算法并不难掌握，甚至可以总结为一个固定的、适用于许多编程题的套路，至于这个套路是什么，我先不说，大家一步一步看了解会更深一些。

解空间
在展示回溯算法前，有一个概念需要大家了解——解空间。回溯法的解空间是树的形式（不了解什么是树的朋友请自己学习）。对于一个使用回溯算法的题目，如果可以把解空间构造出来，那么这个题就差不多可以解答了。解空间在我们学习的过程中已经有过使用，比如说在学习概率的时候，有许多题都需要用树形结构表示出所有的可能性。比如说摇骰子，摇三次，出现两个4和一个6的概率是多少？根据这个问题我们可以画出一个深度为3（摇三次），每个节点的度为6（骰子六个面）的树，共有6^3种结果，从中选取自己需要的结果。我们从这个例子可以看到使用解空间解决问题有两种作用：列举出所有的情况、选取特殊的结果（剪枝）。这两种操作分别对应了回溯算法的外在和内核。接下来我们用几个例子来了解回溯算法。

红绿灯

有一个红绿灯，上面有三个灯，每个灯有三种颜色，请分别用123表示三种颜色，得到这个红绿灯变色的可能性。
看完这个问题，有些朋友可能已经十指连动，写完了这样的一段代码

void light()
{
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
printf("%d%d%d",i,j,k);
printf("n");
}
}
}
}

这段代码没有问题，三层for循环表示树的深度为3，每个for循环都是从1到3，表示每个节点的度为3，构造出了正确的解空间。虽然这样写是正确的，我们在使用回溯算法时不推荐这样写：3个灯是三层for循环，那么10个灯呢？不能真的写十层for循环吧。所以我们对代码进行改写，使用迭代的方式，但不改变代码的意思。

void light(int n,int z[])
{
if(n==3)
/*迭代三次后停止，打印此时的数组z*/
{
for(int i=0;i<3;i++)
{
printf("%d",z[i]);
}
printf("n");
}
for(int i=1;i<=3;i++)
/*对z[n]赋值，123分别赋值，然后再次迭代，对下一个位置进行赋值*/
{
z[n]=i;
light(n+1,z);
}
}

通过这个例子，我们了解到使用回溯算法时，应该采用迭代的方式编写代码。下面我们通过一个简单的例子来熟悉回溯算法。

全排列

给定一个数组，里面有不重复的n个正整数，求它们的全排列。
求数组的全排列，直白地说，就是对每个数进行讨论：取，还是不取？这样这个问题可以进一步简化为与上面红绿灯问题相近的问题：有n个灯，每个灯有两种颜色，有几种可能性？这并不难，我们直接看代码。

void track(int z[],int n,int j,int A[])
/*数组z为存放n个正整数，数组A为指示数组*/
{
if(j==n)
/*迭代n次后停止迭代，根据指示数组A从数组z中取正整数，打印此时的排列*/
{
for(int i=0;i<n;i++)
{
if(A[i]) printf("%2d",z[i]);
}
printf("n");
}
else
{
A[j]=1;
/*这里本来应该是用for循环的，但只有取和不取两种选择，所以就直接这样分开写*/
track(z,n,j+1,A);
A[j]=0;
track(z,n,j+1,A);
}
}

看到这里，我想大家对回溯算法有了一定的了解，虽然上面的算法并没有体现“回溯”的操作，但整体的框架就是这样，对于回溯算法，个人的理解的一般代码的形式是

void example(数组z用来存放信息，数组A作为数组z的指示数组辅助对数组z的操作，整数n用来表示迭代的次数，其他参数）
{
    if(满足一定条件时结束迭代，一般为n到达了树的深度)
    {
        一些操作
    }
    for(根据解空间确定每个节点的度)
    {
        对数组z或数组A进行操作
        一些操作
        if(满足一定的条件才进行下一次迭代(嗅探)，这就是“剪枝”的操作)
        {
            下一次迭代
        }
    }
}

这没什么值得讲解的，可以把它看做一个模板，对于很多题都适用。接下来我们来看一个经典的回溯算法的问题。

8皇后问题

在一个8 * 8的棋盘上放置8个皇后，使她们不能相互攻击，有几种放置方法？
皇后攻击的方法大家可以自己搜索，直白来说就是“米”字，即皇后的同一行、同一列还有斜方向上都不能有别的皇后。这个问题可以说是相当经典，有了模板，大家应该觉得解决这个问题比较简单。
Talk is cheap, show me the code

int isReady(int n,int z[])
{
for(int i=0;i<n;i++)
{
if(i+z[i]==n+z[n]||z[i]==z[n]||i-z[i]==n-z[n]) return(0);
/*条件判断，如果可以攻击，返回0*/
}
return(1);
/*条件判断，不能互相攻击，返回1*/
}
void EightQueen(int n,int z[])
{
int isReady(int n,int z[]);
if(n==8) NUM+=1;
/*列举出一种放置方法后数量加一*/
for(int i=1;i<=8;i++)
/*一列棋盘有八个格子，对应for循环从1到8*/
{
z[n]=i;
/*对于第n列，每一个格子都放置一次*/
if(isReady(n,z))
/*如果当前已经放置的皇后不会相互攻击，则进行下一次迭代*/
{
EightQueen(n+1,z);
}
}
}

8皇后问题经典地展示了回溯算法，代码虽然不长，但完整地展示了使用回溯算法的一般流程。对于下面的例子——走迷宫，代码会显得更加复杂，但内核区别不大。

迷宫问题

给定一个二维数组，用1表示空格，用0表示石块，给定起点与终点，请问有多少条路径可以走出迷宫？
对于迷宫问题，与8皇后问题有一点显著不同的是，迷宫问题没有明确地给定迭代次数，即树的深度，但这个树是确实存在的，因为总的路径是确定的。所以我们不必在函数中引入表示迭代次数的参数，相对的，我们要引入指示数组A来确定每个空格的状态，因为我们迭代的方式是对于每个空格，都尝试它的上下左右四个空格，如果没有指示数组A，我们就会在迷宫中没有限制来回走，刚从v1走到v2，下次在v2迭代，就可以又从v2走到v1，如此反复不会停止；而如果在使用指示数组时，只是简单地把走过的空格标注出来也不可以，因为这样的话，对于一些岔路，有多个路径要共用一个空格，而这个空格在第一个路径通过的时候已被标记，剩下的路径就无法到达终点了。所以，在使用指示数组A时，要做到事了拂身去，不对别的路径产生影响，开始时标记一次，结束时取消标记。

int z[5][10]={
{0,0,0,0,0,0,1,1,1,0},
{0,0,0,0,0,0,1,0,1,0},
{1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,0,0,1},
{0,0,0,0,0,0,1,1,1,1}
};
/*设置迷宫，入口为z[2][0]，出口为z[2][9]，1表示空格，0表示石块*/
int A[5][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}
};
/*设置指示数组，0表示未走过，1表示已走过*/
void Maze(int y,int x,int z[5][10],int A[5][10])
{
if(y==2&&x==9) NUM+=1;
/*每走到终点总数加一*/
if(x+1<=9&&z[y][x+1]&&A[y][x+1]==0)
/*下面四个if代替了for循环，进行下一个迭代的条件都是：下一个格子不超范围且是空格且没走过*/
{
A[y][x+1]=1;
Maze(y,x+1,z,A);
A[y][x+1]=0;
/*当讨论完这个空格后的所有路径后，将这个空格取消标记，这个过程有些像是出栈*/
}
if(x-1>=0&&z[y][x-1]&&A[y][x-1]==0)
{
A[y][x-1]=1;
Maze(y,x-1,z,A);
A[y][x-1]=0;
}
if(y-1>=0&&z[y-1][x]&&A[y-1][x]==0)
{
A[y-1][x]=1;
Maze(y-1,x,z,A);
A[y-1][x]=0;
}
if(y+1<=4&&z[y+1][x]&&A[y+1][x]==0)
{
A[y+1][x]=1;
Maze(y+1,x,z,A);
A[y+1][x]=0;
}
}