双向搜索的理解和板子

发布时间:2024年01月18日

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

双搜的要求:

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

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

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

我们需要用到的算法就是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);
}
?
?
文章来源:https://blog.csdn.net/louisdlee/article/details/135672711
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。