常用算法思想（二）——回溯法

  回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

求解步骤

1)针对所给问题，定义问题的解空间；

2)确定易于搜索的解空间结构；

3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用的剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。

下面介绍一个由回溯法解决的问题：

N皇后问题

N皇后问题是指在N*N的棋盘上放置N个皇后，使这N个皇后无法吃掉对方（也就是说两两不在一行，不在一列，也不在对角线上）。

using namespace std;
int queenCount = 0;
//判断第last行上插入皇后的可行性
int check(vector<int>& arr, int last) {
for (int i = 0; i < last;i++) {
if ((arr[i] == arr[last]) || (abs(i - last) == abs(arr[i] - arr[last])))
return false;
}
return true;
}
void queen(vector<int>& arr,int i,int n) {
if (i >= n) {
queenCount++;
}
else {
for (int j = 0; j < n; j++) {
arr[i] = j;
if (check(arr, i)) {
queen(arr, i + 1, n);
}
}
}
}
int main()
{
int n = 8;
vector<int> arr(n,0);
//保存每一行上皇后的列数
queen(arr, 0, 8);
//for_each(arr.begin(), arr.end(), [](int x) { cout << x << ends; });
cout << queenCount << endl;
system("pause");
return 0;
}

最后

以上就是彩色龙猫为你收集整理的常用算法思想（二）——回溯法的全部内容，希望文章能够帮你解决常用算法思想（二）——回溯法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。