基本思想:回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有位置符合要求,那么就要改变第一个皇后的位置,重新放第2个皇后的位置,直到找到符合条件的位置就可以了。是一种以深度优先搜索带以跳跃性搜索的算法。
回溯算法说白了就是穷举法,只不过在进行穷举的过程中,用剪枝函数跳过了一些不必要的搜索,跳过了一些不可能到达最终状态的子节点,减少状态空间树节点的生成
那么我们进行回溯算法比较疑惑的地方就是,何为状态空间树,状态空间树如何生成,如何根据问题找出非满足的状态,以及剪枝函数如何进行逻辑设定;
回溯法两种方式的伪代码:
1.递归回溯
void Backtrack(int t){
if(t > n) Output(x);//Output 记录或者输出可行解
else{
for( int i = f(n,t); i <= g(n,t); ++i){//f(n,t)和g(n,t)表示在当前结点未搜索过的子树的起始编号和终止编号
x[t] = h(i);
if(constraint(t) && Bound(t)) Backtrack(t+1);//constraint和bound分别是约束函数和界限函数
}
}
}
递归实现回溯非常容易理解,但是执行效率没有迭代高,根据需要,开辟大量的内存空间,来进行递归。
2.迭代回溯:
void IterativeBacktrack(void){
int t = 1;
while(t > 0){
if(f(n,t) < g(n,t)){
for(int i = f(n,t); i <= g(n,t); ++i){//这个for 是遍历各个值的意思,实际中写成for循环会有逻辑错误
x[t] = h(i);
if(constraint(t) && bound(t)){
if(solution(t)) Output(x);//solution 判断是否已经得到问题的解
else t++;
}
else t--;
}
}
}
}
//迭代回溯相比较递归比较难理解,它的迭代过程就是解决问题的逻辑过程,不断进行循环,根据问题的规模,有时候时间复杂度也是不容乐观的。
为了个更好的理解回溯算法的原理,我们以解决n皇后问题为例:
举例:问题就是在 n×n 格的国际象棋上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
此问题如果用单纯的穷举法解决,会搜索出n^n个搜索结果,穷举的时候从所有皇后都放在第 1 行的方案开始,检验皇后之间是否会相互攻击。如果会,把列 H 的皇后挪一格,验证下一个方案。移到底了就 “进位” 到列 G 的皇后挪一格,列 H 的皇后重新试过全部的 n 行,毫无疑问这种方法效率极低,n过大的话直接会把计算机给跑死,所以我们来看回溯算法。
讲算法之前先展示一下何为状态空间树;
这里我们以四皇后问题解释一下何为状态空间树:
以一个4×4的空棋盘为根,先在棋盘的第一行第一列(1,1)处放置一个皇后1,然后观察皇后2的情况,对于皇后2,在第一列和第二列都无法放置,那么尝试第三列,当我们放置皇后2在(2,3)处时,发现皇后3无法放置,进入了死路,这时候我们进行回溯,将皇后2放置在第四列,然后发现皇后3可以放在(3,2)的这个位置,但是此时问题又出现了,皇后4无法防止,进入死路,那么我们继续回溯,回溯到皇后1应当放置的位置,将皇后1放置在第二列,依次类推,直到找到最后的可成立的一个放置解。这就是该算法的搜索状态空间树。
但是以上的只是一部分,仅仅是皇后1到达第二列为止,其他的方式还可以有搜索状态,但是总的思路是一致的。
进行搜索的过程如下(以四皇后为例)
解决皇后问题比较开心的就是,他的状态空间树的每一个节点就是一个二维空间,代码实现的时候,可以很清晰的进行每一步的搜索,符合计算机存储的逻辑。
到这里我们实际上已经搞清楚了,不满足的状态就是,在每一个皇后位置,同行同列对角线即为不满足,我们搜索的过程一旦遇到此种状态,在进行一步步的搜索时,就要用剪枝函数(此题中就是一个if判断)来进行跳跃回溯搜索。
综上我们大致搞清楚了,进行回溯的时候,回溯到底是一个什么逻辑,回溯难在你需要对问题足够的清晰,搞清楚你这个空间树是子集树还是排序树,亦或者其他,在进行代码实现的时候如何模拟你的搜索过程,采取哪种数据结构,运用递归还是迭代实现过程。(常见的比较难的问题时,可以先写一个递归的伪代码,一般是比较容易想出来的,然后在伪代码基础上进行修改)这是我们大体上的解决过程。总归回溯这种思想是很简明易懂的,但是回溯解决问题的时候,代码实现还是有一定的距离的,这就需要我们大量面对问题,多做多练。文章来源:https://www.toymoban.com/news/detail-450855.html
代码实现:
这里只进行了迭代回溯
文章来源地址https://www.toymoban.com/news/detail-450855.html
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
//用一维数组存储,解决行冲突,数组下标为行数,数组值为列数
int x[10]={0};
int count=0;
bool judge(int k)//判断第k行某个皇后是否发生冲突 ,发生冲突就跳过
{
int i=1;
while(i<k) //循环i到k-1之前的皇后;
{
if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))//存在列冲突或者存在对角线冲突(实际上就是一种剪枝)
return false;
i++;
}
return true;
}
void queen(int n)
{
int i,k=1; //k为当前行号,从第一行开始
x[1]=0;//x[k]为第k行皇后所放的列号
while(k>0)
{
x[k]++; //首先从第一列开始判断
while(x[k]<=n&&!judge(k))//推导k行到底选择哪一列,如果当前该列不行则下一列,直到成立即可;
x[k]++;
if(x[k]<=n)
{
if(k==n)//输出所有解
{
for(i=1;i<=n;i++)
printf("第%d行的皇后:在第%d列 ",i,x[i]);
count++;
printf("-------这是其中第%d个解",count);
printf("\n");
}
else//判断下一行
{
k++; x[k]=0;
}
}
else k--;//没找到,回溯
}
return ;
}
int main()
{
int n;
cout<<"请输入你的n皇后: ";
cin>>n;//n最大值不超过10
queen(n);
return 0;
}
到了这里,关于算法:回溯算法(以解决n皇后问题为例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!