本系列为C++算法学习系列,会介绍 算法概念与描述,入门算法,基础算法,数值处理算法,排序算法,搜索算法,图论算法, 动态规划等相关内容。本文为搜索算法部分。
【 5 】深度优先搜索 【 5 】广度优先搜索
现假设有n个整数,分别是1~n,现在将这n个数进行排列,每一个整数只能并且一定要出现一次,求它们的全排列。
每次选数的时候,都有n种可能,因为不能选重复的数,所以不一定所选的数都能成功的选上。 那么怎么办呢?我们不妨可以设置一个做标记的数组book[11](我们经常使用的数组标记法),用作标记1-n你这n个数是否被选上的状态。 如果当前数字已经被选过,那么则选下一个数字。否则就选择当前数字,那下一步仍然用同样的方法进行筛选了! ! ! 那显然我们首先想到的就是枚举,那么当n=10时,就是使用10个循环来枚举这10个数,当然是可以的,但这代码量…
for(i = 1;i <= n;i++)
{
a[step] = i;//将i号扑克牌放入到第step个盒子中
}
这里的数组a是用来表示小盒子的,变量step表示当前正处在第step个小盒子面前。a[step] = i;就是将第i号扑克牌,放入到第step个盒子中。 这里有一个问题就是,如果一张扑克牌已经放到别的小盒子中了,那么此时就不能再放入同样的扑克牌到别的盒子中了,因为此时手里已经没有扑克牌了。因此还需要一个数组book来标记哪些牌已经使用了。
for(i = 1;i <= n;i++)
{
if(book[i] == false) //等于false,表示第i号牌没有被使用过
{
a[step] = i; //把i号牌放入到第step个盒子中
book[i] = true; //把book[i] 设为true,表示已经用过了i号牌
}
}
我们现在已经处理完第step个小盒子了,接下来需要往下走一步,去处理第step+1个小盒子。 如何处理呢? 处理方法其实和我们刚刚处理第step个小盒子的方法相同。 把它封装成一个函数
void dfs(int step) // 表示站在第step个小盒子面前
{
for(int i = 1; i <= n;i++)
{
if(book[i] == false) // 判断扑克牌是否用过
{
a[step] = i; //没用过就把第i号扑克牌放入第step个小盒子
book[i] = true;//book[i]设为true,表示第i号扑克牌我们已经用过
}
}
}
把这个过程变成函数以后,就好处理第step + 1 个盒子了 就是 dfs(step + 1),来看代码
void dfs(int step) // 表示站在第step个小盒子面前
{
for(int i = 1; i <= n;i++)
{
if(book[i] == false) // 判断扑克牌是否用过
{
a[step] = i; //没用过就把第i号扑克牌放入第step个小盒子
book[i] = true;//book[i]设为true,表示第i号扑克牌我们已经用过
dfs(step + 1);//通过函数递归来实现(函数自己调用自己)
book[i] = false;
//这里是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
}
}
}
book[i] = false; 这一步非常重要,也就是我们上面说的回溯,回溯要恢复到原来的场景。 也就是我们把扑克牌收回,否则无法进行下一次的摆放。 现在还有一个问题,就是什么时候输出一个满足要求的序列呢? 其实当我们处理第n + 1个小盒子的时候(即step = n + 1),说明前n个小盒子已经放好扑克牌了,这里将1~n个小盒子中的扑克牌编号打印出来就可以了。注意!打印完毕之后一定要return,否则程序就会永无止境地进行下去了,也就是要有递归的终止条件。
void dfs(int step) // step 表示现在站在第几个盒子面前
{
if(step == n + 1) //如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌
{
//输出一种排列,即 1 ~ n 号盒子中扑克牌编号
for(int i = 1;i <= n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
return; // 返回之前的一步(最近一次调用dfs的地方)
}
for(int i = 1;i <= n;i++)
{
if(book[i] == false) // 判断扑克牌i是否已经用过
{
a[step] = i; //如果没用过,就把i号牌放在第step个盒子
book[i] = true;//i号牌记录为已经用过
dfs(step + 1);//处理第step+1个盒子,函数递归实现
book[i] = false;//将刚才的扑克牌收回,才能进行下一次尝试
}
}
}
#include <iostream>
using namespace std;
//int a[N];//开辟的盒子
int a[11],book[11],n,sum=0;
// 把n个扑克牌放在n个盒子中
void dfs(int t) //t表示现在站在第几个盒子面前
{
if(t==n+1) //如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌
{
cout<<"进入t=n+1中"<<endl;
sum++;
//输出一种排列,即 1 ~ n 号盒子中扑克牌编号
for(int i=1;i<=n;i++)
{
cout<<a[i];
}
cout<<endl;
return; //返回之前的一步(最近一次调用dfs的地方)
}
for(int i=1;i<=n;i++)
{
if(book[i]==0) //判断扑克牌i是否已经用过
{
a[t]=i;//选择该数,保存 //如果没用过,就把i号牌放在第step个盒子
book[i]=1; //i号牌记录为已经用过
cout<<" dfs(t+1)之前 t-->"<<t<<"i-->"<<i<<endl;
cout<<" dfs(t+1)之前 book[i]"<<i<<book[i]<<endl;
dfs(t+1);//下一步筛选 //处理第step+1个盒子,函数递归实现
cout<<" dfs(t+1)之后 t-->"<<t<<"i-->"<<i<<endl;
cout<<" dfs(t+1)之后book[i]"<<i<<"--"<<book[i]<<endl;
book[i]=0;// 回溯到上一部的状态 将刚才的扑克牌收回,才能进行下一次尝试
cout<<" dfs(t+1)之后 book[i]=0之后"<<i<<"--"<<book[i]<<endl;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<sum;
return 0;
}
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。 输入格式
共一行,包含整数 n。
输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。 每个方案输出完成后,输出一个空行。 注意:行末不能有多余空格。 输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
#include<iostream>
using namespace std;
const int N = 20;//对角线的个数是2n - 1
char g[N][N];//存储当前的图
bool col[N], dg[N], udg[N];//列和对角线以及反对角线是否有皇后(true 有,false无)
int n;
void dfs(int u)
{
if(u == n)//表示已经搜了n行,故输出这条路径
{
for(int i = 0; i < n; i ++)puts(g[i]);
puts("");//puts输出字符串
return;
}
for(int i = 0; i < n; i ++)
{
if(!col[i] && !dg[u + i] && !udg[n - u + i])//对角线为 n- u + i, 反对角线下标为 u + i
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
//还原现场
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
}
int main()
{
cin >> n; // 几个皇后
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
g[i][j] = '.';
dfs(0);
return 0;
}
//dfs与递归类似
在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。