算法思想之回溯法

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~

算法知识点

回溯法是比贪心法和动态规划法更一般的方法。
解为n-元组(x0,x1,…,xn-1)形式。
通过搜索状态空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。
回溯法是一种选优搜索法，按照选优条件深度优先搜索，以达到目标。当搜索到某一步时，发现原先选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态称为“回溯点”。
.树中每个结点称为一个问题状态；
若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；
若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；
如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。

算法题目来源

n-皇后
回溯法是从初始状态出发，按照深度优先搜索的方式，根据产生子结点的条件约束，搜索问题的解。当发现当前结点不满足求解条件时，就回溯，尝试其他的路径。回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。

算法题目描述

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

做题思路

用回溯法解决实际问题时，首先要确定解的形式，定义问题的解空间。
什么是解空间呢？
（1）解空间
·解的组织形式：回溯法解的组织形式可以规范为一个n元组{x1，x2，…，xn}，例如3个物品的0-1背包问题，解的组织形式为{x1，x2，x3}。
·显约束：对解分量的取值范围的限定。
例如有3个物品的0-1背包问题，解的组织形式为{x1，x2，x3}。它的解分量xi的取值范围很简单，xi=0或者xi=1。xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包，因此xi∈{0，1}。
3个物品的0-1背包问题，其所有可能解有：{0，0，0}，{0，0，1}，{0，1，0}，{0，1，1}，{1，0，0}，{1，0，1}，{1，1，0}，{1，1，1}。
·解空间：顾名思义，就是由所有可能解组成的空间。
解空间越小，搜索效率越高。解空间越大，搜索的效率越低。犹如大海捞针，在海里捞针相当困难，如果把解空间缩小到一平方米的海底就容易很多了。
迭代回溯算法框架
void IBacktrack(int n)
{ int k=0;
while (k>=0) {
if (还剩下尚未检测的x[k],使得x[k]∈T(x[0],…,x[k-1])&&Bk(x[0],…,x[k])
{ if ((x[0],x[1],…,x[k])是一个可行解)
输出(x[0],x[1],…,x[k]);//输出可行解
k++;//深度优先进入下一层
}
elsek–;//回溯到上一层
}
}

模板代码

 void RBacktrack (int k)
{   for(每个x[k],使得x[k]∈T(x[0],...,x[k-1])&&(Bk(x[0],...,x[k]))
{
// T(x0,x1,...,xk-1)表示沿路径(x0,x1,...,xk-1)从根到某个问题状态时，孩子结点xk可取值的集合。
// Bk(x0,x1,...,xk)为约束函数。若子树上不含任何答案状态，则为false；否则,为true。
if ((x[0],x[1],...,x[k])是一个可行解)//判断是否可行解
输出(x[0],x[1],...,x[k]);//输出可行解
RBacktrack(k+1);//深度优先进入下一层
}
}
1
2
3
4
5
6
7
8
9
10

做题过程中遇到的bug及解决方案

解向量：(x0, x1, … , xn-1),其中xi表示第i行的皇后所处的列号。
（采用第二种显式约束观点的）
约束函数：当i≠j时，要求
1）不同列：xi≠xj
2）不处于同一正、反对角线：|i-j|≠|xi-xj|
4-皇后问题状态空间树——见P180 图8-3（排列树）
解向量：(x0, x1, … , xn-1),其中xi表示第i行的皇后所处的列号。
设计约束函数：
对0≤i,j

bool Place(int k,inti,int *x)//约束函数（隐式）
{//判断当前第k行皇后是否可放在第i列位置
for (int j=0;j<k;j++)
if ((x[j]==i)||(abs(x[j]-i)==abs(j-k))) return false;
//检查与前面已选定的0~k-1 行皇后是否冲突。若有皇后（j行x[j]列）
//与当前皇后(k行i列）在同一列或斜线上，则冲突，返回false。
return true;
} 
void NQueens(intk,int n,int *x)  //为第k行皇后选择可放置的列
{   for (int i=0;i<n;i++) //显式约束（尝试所有可选列数0~n-1）
{if (Place(k,i,x))//约束函数（隐式）
{   x[k]=i;
if(k==n-1)
{    for (i=0;i<n;i++) cout<<x[i]<<“ ”;    //输出一个可行解
cout<<endl;
}
elseNQueens(k+1,n,x);//深度优先进入下一层
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

相关算法题型题目总结

隐约束（剪枝函数）包括约束函数和限界函数。
对能否得到问题的可行解的约束称为约束函数，对能否得到最优解的约束称为限界函数。有了剪枝函数，我们就可以剪掉得不到可行解或最优解的分支，避免无效搜索，提高搜索的效率。剪枝函数设计得好，搜索效率就高。解空间的大小和剪枝函数的好坏都直接影响搜索效率，因此这两项是搜索算法的关键。
在搜索解空间时，有几个术语需要说明。
·扩展结点：一个正在生成孩子的结点。
·活结点：一个自身已生成，但孩子还没有全部生成的结点。
·死结点：一个所有孩子都已经生成的结点。
·子孙：结点E的子树上所有结点都是E的子孙。
·祖宗：从结点E到树根路径上的所有结点都是E的祖宗。

0/1背包问题
0/1背包问题的解用n-元组表示：X=(x0,x1,…,xn-1) xi=0或1（0≤i template
class Knapsack
{
public:
T BKnapsack(int *x);
protected:
void BKnapsack(int k,T cp,Tcw,T &fp,int *x,int *y);
T Bound(int k,T cp,T cw);//Bound为上界函数bp
T m,*w,*p;//已按p[i]/w[i]≥p[i+1]/w[i+1]排序
int n;
}；

template <class T>
void Knapsack<T>::BKnapsack(int k,T cp,T cw,T &fp,int *x,int *y)
{  //cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号
//fp是当前最大收益
//考察左孩子结点
int j;  T bp;
if (cw+w[k]<=m)//左子树，需重新计算约束函数，上界函数无需计算
{
y[k]=1;
if (k<n-1) //未到底
BKnapsack(k+1,cp+p[k],cw+w[k],fp,x,y);
if (cp+p[k]>fp && k==n-1)//到最底层
{fp=cp+p[k];//更新最优解下界估计值
for (j=0;j<=k;j++) x[j]=y[j];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

template <class T>
void Knapsack<T>::BKnapsack(int k,T cp,T cw,T &fp,int *x,int *y)
{  //cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号
//fp是当前最大收益
。。。。。。
//考察右孩子结点
if (Bound(k,cp,cw)>=fp) //右子树，需重新计算上界函数，约束函数无需计算
{
y[k]=0;
if (k<n-1) //未到底
BKnapsack(k+1,cp,cw,fp,x,y);
if (cp>fp && k==n-1)//到最底层
{fp=cp;//更新最优解下界估计值
for (j=0;j<=k;j++) x[j]=y[j];
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结：用回溯法解决问题时，首先要考虑如下3个问题。
（1）定义合适的解空间
因为解空间的大小对搜索效率有很大的影响，因此使用回溯法首先要定义合适的解空间，确定解空间包括解的组织形式和显约束。
·解的组织形式：解的组织形式都规范为一个n元组{x1，x2，…，xn}，只是具体问题表达的含义不同而已。
·显约束：显约束是对解分量的取值范围的限定，显约束可以控制解空间的大小。
（2）确定解空间的组织结构
解空间的组织结构通常用解空间树形象的表达，根据解空间树的不同，解空间分为子集树、排列树、m叉树等。
（3）搜索解空间
回溯法是按照深度优先搜索策略，根据隐约束（约束函数和限界函数），在解空间中搜索问题的可行解或最优解。当发现当前结点不满足求解条件时，就回溯，尝试其他的路径。“能进则进，进不了则换，换不了则退”。
如果问题只是要求可行解，则只需要设定约束函数即可；如果要求最优解，则需要设定约束函数和限界函数。
解空间的大小和剪枝函数的好坏是影响搜索效率的关键。
显约束可以控制解空间的大小，剪枝函数决定剪枝的效率。
所以回溯法解题的关键是设计有效的显约束和隐约束。