算法思想之回溯法

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

算法知识点

回溯法是比贪心法和动态规划法更一般的方法。
解为n-元组(x0,x1,…,xn-1)形式。
通过搜索状态空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。
使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数。通常情况下，回溯法是为了找出满足约束条件的所有可行解。回溯法要求问题的解向量具有n-元组(x0,x1,…,xn-1)的形式，每个解分量xi从一个给定的集合Si取值。显式约束：规定每个xi取值的约束条件。
状态空间树状态空间树：描述问题解空间的树形结构。
.树中每个结点称为一个问题状态；
若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；
若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；
如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。

算法题目来源

n-皇后

算法题目描述

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

做题思路

迭代回溯算法框架
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

相关算法题型题目总结

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