双向搜索的理解和板子

"互相奔赴，各司其职。“ ——双向搜索

双搜的要求：

当我们发现，要从一种状态开始，经过很多次操作，来得到一种给定的状态。

这时候，我们就可以考虑用双向搜索。

从起点和终点开始搜。当二者相遇，输出答案即可。

我们需要用到的算法就是bfs。

让我们用一道题来领略一下双搜。

P1379 八数码难题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意很简单，我们需要不断交换0，与其他数的位置，使得其能到达最终状态。

而我们要求到达最终状态的路径最短，所以考虑bfs。

无论0在哪个位置，它都可以往四个方向交换，当然，这里面有很多无效的操作，所以我们考虑剪枝，如果它交换后的坐标，是合法坐标，那么我们认为这次交换时有效的。

2 ?8 ?3
1 ?0 ?4
7 ?6 ?5

在0处，我们上下左右都进行交换，然后判断交换后的0的坐标是否在这个3x3的矩阵里面就行了。

预处理：

记录状态、

由于双向搜索，那么我们需要同时记录每一边的这些信息：

• 走到当前状态时的字符串

• 走到当前状态时的步数

• 走到当前状态时的0的坐标

这些我们可以开一个类/结构体，然后再定义两个队列，数据类型为结构体。

检查状态、

双向搜索时，我们需要判断当前状态是否被另一边搜过了。

所以我们考虑用map来存状态。

map的键就是字符串，map的值就是走到这个字符串的步数。

所以我们只需要判断map里这个键是否存在就可以知道有没有被搜过。

关键步骤：

搜索过程

假如当前状态是：

2 ?8 ?3
1 ?0 ?4
7 ?6 ?5

我们写一个坐标偏移数组:

int Movex[] = { 0,0,-1,1 }; //在字符串中，向左移动，向右移动，向上移动，向下移动。
int Movey[] = { -1,1,0,0}; //在字符串中，向左移动，向右移动，向上移动，向下移动。

然后我们移动之后，判断一下是否在矩形内部：

for(int j=0 ; j<4 ;j++){
?
 ? ?int nowx = x + Movex[j];
 ? ?int nowy = y + Movey[j];
?
 ? ?if (nowx >= 0 and nowx <= 2 and nowy >= 0 and nowy <= 2){
?
 ? ? ? ? ? ? ? ? ? ? ..........
 ?  }
?
}

如果在矩形内部，我们直接通过二维坐标，反解出0在字符串里的位置即可。

2 ?8 ?3
1 ?0 ?4 ?----> 283104765
7 ?6 ?5

然后交换0和移动的位置上的数。

再进行一次判断，判断交换完了之后，是否当前状态被对方搜到过，如果搜到，那么返回答案，否则将新状态加入队列和map中。

步数直接由上一个状态的步数+1.

记得交换完了之后再交换回去。

关键思想

双向搜索，又叫做meet in the middle

为了最大程度减少空间复杂度，所以我们尽可能让两边搜的次数相等。

我们可以设计一个while循环，当哪一边的队列里的元素多了，我们就搜另一边。

假如一边的队列中所有的元素已经弹完了，那么我们只要把剩下一边的队列单独搜完即可。

下面是我写的此题的代码：

#include <iostream>
#include<cstring>
#include <cmath>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
// ?  0 ? 1 ? 2 
// ? __________ ? ? ? 
// 0 | 1 ? 2 ? 3|
// 1 | 8 ? 0 ? 4|
// 2 | 7 ? 6 ? 5|
// ? ___________
?
// 每次走就交换一下两个位置。
// 并且将交换后的字符串，存入map里作为键，然后走到这里的步数作为值。
// 交换完之后，检测一下，当前字符串在对方map里是否存在.
// 如果不存在，说明没被搜过。否则被搜过，我们之间返回二者步数之和。
// 
// 并且，为了meet in mid ， 也就是最省时。
// 我们要保证，两边搜的步数是一致的。
// 
// 如果一边搜索的步数比另一边大，那么，搜另一半，否则搜这一边。
// 
// 如果，其中已经搜空了一边，那就继续搜另一边。
// 
// 
//
?
class Step {// 每一个类实例，都是一种状态
public:
    int num; //这种状态下，用的步数
    string status; // 这种状态下的，字符串
    int x,y; //0在字符串中的位置
    Step(int num, string status, int x,int y) :num(num), status(status), x(x),y(y) {}; //类的初始化列表
};
?
?
queue<Step> q[2]; //开一个二维队列，q[i].push(x), i表示从哪里出发。
map<string, ll> m[2]; //开一个二维map，m[i][string]= step ; 第一个参数0代表从答案出发，1代表从样例出发 ，第二个参数是map的键。
?
string target = "123804765";
string now1;
?
int Movex[] = { 0,0,-1,1 }; //在字符串中，向左移动，向右移动，向上移动，向下移动。
int Movey[] = { -1,1,0,0}; //在字符串中，向左移动，向右移动，向上移动，向下移动。
?
?
void expand(int i) {
?
    Step p = q[i].front(); //取出队头
?
    q[i].pop(); //删除队头
    
    string t = p.status; // 创建一个副本，此时还未交换的状态。
    
    bool judge = m[1-i].count(t); // count函数，用来查找m中是否存在该键。也就是查询状态
    if (judge!=0) {
        cout<< (m[i][t] + m[1-i][t])<<endl; //如果已经相遇了，就不需要更新，直接返回步数即可
        exit(0); //不用return，直接退出
    }
?
    int x = p.x; //0的横坐标
    int y = p.y; // 0的纵坐标
    int pos = 3 * x + y; //0在字符串里的坐标
?
    for (int j = 0; j < 4; j++) {
?
        int nowx = x + Movex[j];
        int nowy = y + Movey[j];
?
        if (nowx >= 0 and nowx <= 2 and nowy >= 0 and nowy <= 2) { //如果这一次的变化在矩阵内部
            
            int nextpos = 3 * nowx + nowy;
            swap(t[pos], t[nextpos]); //我们直接交换0在字符串里的下标
            judge = m[1-i].count(t); // 然后判断一下，这个更新的t是否被对面走过
?
            if (judge == 0) {
?
                Step temp = Step(p.num + 1, t, nowx, nowy); //将一个step变量初始化
                q[i].push(Step(p.num + 1, t, nowx, nowy));
                m[i][t] = p.num + 1; //将新的状态记录到map里
?
            }
            else {
?
                cout << p.num + 1 + m[1 - i][t] << endl;
                exit(0);
?
            }
            swap(t[pos], t[nextpos]);
?
        }
        
    }
?
}
?
?
int main() {
?
?
    cin >> now1;
?
    // 将初始化的0的位置信息，存入队列和map中
    int pos = target.find('0');
    
    Step t = Step(0, target, pos / 3, pos % 3);
    q[0].push(t);
    m[0][target] =0;
?
?
    int pos1 = now1.find('0');
    
    Step t1 = Step(0, now1, pos1 / 3, pos1 % 3);
    q[1].push(t1);
    
    m[1][now1] = 0;
?
    while (!q[0].empty() and !q[1].empty()) {
        if (q[0].size() < q[1].size()) {
            expand(0);
        }
        else expand(1);
    }
    while (!q[0].empty())expand(0);
    while (!q[1].empty())expand(1);
}
?
?