双向宽度搜索

  从正反两个方向进行宽度优先搜搜，可以大大减少搜索量，提高搜索速度。

  从初始状态和目标状态两个方向同时进行扩展，如果两颗解答树在某个节点第一次发生重合，即可终止此搜索过程，则该节点所连接的两条路径所拼成的路径就是最优解。

搜索方式

通常有两种搜索方式

1.两个方向交替扩展

2.选择节点个数较少的那个方向先扩展

方法2只需要略加修改控制结构，每次while循环时只扩展正反两个方向中节点数目较少的那一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

很明显，方法2优于方法1

code

int head[2],tail[2],ans; struct s{int x,y;} q[2][maxn];//队列 int v[2][maxn][maxn];//记录访问节点的数组 int dis[2][maxn][maxn];//寻找最短路径时记录数组 int dx[10],dy[10];//扩展方向 int expand(int k)//对k队列进行扩展 { int h,t,d,x,y; x=q[k][head[k]].x; y=q[k][head[k]].y; d=dis[k][x][y]; for(int i=0;i<8;++i) { int nx=x+dx[i]; int ny=y+dy[i]; if(judge()&&!v[k][nx][ny]) { v[k][nx][ny]=1; tail[k]++; q[k][tail[k]].x=nx; q[k][tail[k]].y=ny; dis[k][nx][ny]=d+1; if(v[k^1][nx][ny]) { ans=dis[k][nx][ny]+dis[k^1][nx][ny]; return 1;//找到了 } } } return 0; } void BFS() { q[0][1] //这里特判一下是不是起点等于终点 if(judge()){ans=0; return;} q[0][1].x=startx; q[0][1].y=starty; q[1][1].x=endx; q[1][1].y=endy; v[0][q[0][1].x][q[0][1].y]=1; v[1][q[1][1].x][q[1][1].y]=1; tail[0]=head[0]=tail[1]=head[1]=1; while(head[0]<=tail[0]&&head[1]<=tail[1]) { if(tail[0]-head[0]<tail[1]-head[1]) { expand(0); head[0]++; } else { expand(1); head[1]++; } //方法二，择优扩展 } return; }

这种包装的暴力也就我这种不会正解蒟蒻用吧

转载于:https://www.cnblogs.com/Liuz8848/p/10419920.html

相关资源：八数码问题—双向广度优先搜索（C 实现）