广搜入门题,经典八数码 题库中已经说的很清楚了,这题是用广搜(又称宽搜),那么,何为宽搜,它与深搜区别何在?
1.深搜与广搜
这两种搜索的全名分别是: 深搜——深度优先搜索 广搜——广度优先搜索 其英文缩写分别是 dfs 与 bfs ,虽然只差一个字母,不过却有所不同 深搜的特点是短而难想 广搜的特点是长且难写 我们就根据八数码这道题,说一下深搜与广搜的区别,先看看下面这张图:
0
/ | | \
上 下 左 右(最优解)
/ | | \
上 下 左 右(次右解)
如果你是用深搜他会这么寻找: 0->上->上->返回上一层->下->返回上一层->左->返回上一层->右(次优解)->返回上一层->下-》……最优解
然而广搜是这个样子的 0->上->下->左->右(最优解)->进入下一层-》上-》下-》左-》右-》次优解
以上应该就可以很明白的看出,深搜是将一步搜索到底再回头,广搜是在每一层搜索,所以广搜第一个搜到的一定是最优解。 不过为什么会右这样的差距,这就要看广搜的原理了
2.何为广搜
广度优先搜索
3.题目&思路&部分代码
题目链接: http://caioj.cn/problem.php?id=1046首先我们知道,这个题我们就是要模拟上下左右,也就是说我们读入初始与截止情况,将初始情况放入队列首,先来看看队列怎么写吧
struct FUCK{
int a[4][4],x,y,deep;
}dl[400000],ed;
- int a[][] 临时储存数码图
- x,y 0 的坐标
- deep 深度,也就是步数
while(l<=r){
for(int i=0;i<4;i++){
FUCK fir=dl[l];
fir.x=dl[l].x+dx[i];
fir.y=dl[l].y+dy[i];
if(fir.x>=1&&fir.x<=3&&fir.y>=1&&fir.y<=3){
int temp=fir.a[fir.x][fir.y];
fir.a[fir.x][fir.y]=fir.a[dl[l].x][dl[l].y];
fir.a[dl[l].x][dl[l].y]=temp;
int temp_kt=zys(fir);
fir.deep=dl[l].deep+1;
if(!xd[temp_kt]){
xd[temp_kt]=true;
r++;
dl[r]=fir;
if(temp_kt==z){
printf("%d\n",fir.deep);
return 0;
}
}
}
}
l++;
}
其中 l 是队列首指针, r 是队列尾指针, for 循环对应的就是 dx[] , dy[] 这两个增量然后我们就交换变量,