04双向广度优先搜索：八数码难题

双向广度优先搜索：八数码难题

八数码难题

题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

双向广度优先搜索：

我们常常会面临这样一类搜索问题：起点是给出的，终点也是已知的，需要确定能否从起点到达终点，如果可以，需要多少步。

如果我们用常规的搜索方法，从起点开始往下搜，那得到的解答树可能非常庞大，这样漫无目的的搜索就像大海捞针。

要从庞大的解答树中找到一根“针”，即终点，用蓝色表示

让我们切换一下思路，既然终点是已知的，我们何必让它闲着呢？我们完全可以分别从起点和终点出发，看它们能否相遇：

从起点和终点分别展开搜索，解答树瞬间缩小了很多

如果原本的解答树规模是  ，使用双向搜索后，规模立刻缩小到了约  ，当  较大时优化非常可观。

双向搜索主要有两种，双向BFS和双向迭代加深。

双向BFS

与普通的BFS不同，双向BFS维护两个而不是一个队列，然后轮流拓展两个队列。同时，用数组（如果状态可以被表示为较小的整数）或哈希表记录当前的搜索情况，给从两个方向拓展的节点以不同的标记。当某点被两种标记同时标记时，搜索结束。

主要代码部分思想

queue<T> Q[3]; // T要替换为用来表示状态的类型，可能为int，string还有bitset等
bool found = false;
Q[1].push(st); // st为起始状态
Q[2].push(ed); // ed为终止状态
for (int d = 0; d < D + 2; ++d) // 这个我也不知道为什么这么写，
//应该是设计一个最大深度
{
    int dir = (d & 1) + 1, sz = Q[dir].size(); // 记录一下当前的搜索方向，1为正向，2为反向
    for (int i = 0; i < sz; ++i)
    {
        auto x = Q[dir].front();
        Q[dir].pop();
        if (H[x] + dir == 3) // H是数组或哈希表，若H[x]+dir==3说明两个方向都搜到过这个点
            found = true;
        H[x] = dir;
        // 这里需要把当前状态能够转移到的新状态压入队列
    }
    if (found)
        // ...
}

本题代码

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
#define int long long
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
unordered_map<string,int> H;//建立一个哈希表H用于记录当前状态是否被搜索过
queue<string> q[3];//建立一个q[1],q[2]分别用于表示从前广搜和从后广搜的经历过的状态
string justswap(string temp,int pos,int topos)
{//本函数用于交换字符串temp中pos位置和topos位置的值，返回一个字符串
    if(topos<pos)//如果顺序不对，换一下，保证pos<topos
    {
        int temp=topos;
        topos=pos;
        pos=temp;
    }
    //切片，返回即可
    string ret1=temp.substr(0,pos);
    string ret2=temp.substr(pos+1,topos-pos-1);
    string ret3=temp.substr(topos+1,temp.size()-topos);
    return ret1+temp[topos]+ret2+temp[pos]+ret3;
}
signed main(void)
{
    string st;
    string ed = "123804765";
    cin>>st;
    q[1].push(st);//1表示正向搜索
    q[2].push(ed);//2表示反向搜索
    int co=0;
    while(!q[1].empty() || !q[2].empty())//这个终止条件没什么用在这里
    {
        int direct=co%2+1;//co用于计数
        int qs=q[direct].size();//要提前取出队列大小，不然一边向队列里
                    //添加元素，一边删元素，会出现混乱
        for(int i=0;i<qs;i++)
        {//对direct方向的队列元素进行拓展
            string temp=q[direct].front();
            q[direct].pop();
            if(H.count(temp))//如果temp状态已经被走过了
            {//如果没有被走过进不了下面这个if，则不处理，直接考察q[direct]的下一个元素
                if(H[temp]+direct==3)//如果temp已经被另一个方向走过了
                {
                    cout<<co-1<<endl;//输出步数，注意是co-1；
//因为交汇的状态算了两次
                    exit(0);
                }
            }
            else //如果没有走过
            {
                H.insert({temp,direct});//插入键值对
                int pos=temp.find('0');//找到0的位置
                for(int i=0;i<=3;i++)//在temp基础上往四个方向拓展
                {
                    if((pos%3)+dx[i]<0 || (pos%3)+dx[i]>2 || pos+dy[i]*3<0 || pos+dy[i]*3>=9)continue;
                    //处理越界情况
                    string t=justswap(temp,pos,pos+dx[i]+dy[i]*3);
                    //往四个方向拓展
                    q[direct].push(t);
                    //压入队列
                }
            }
        }
        co++;
    }
    return 0;
}

一般形式（节选自oiwiki）(用一个队列写的方式，但是不适用于本题)

将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
 从 q.front() 扩展出新的 s 个结点
 如果 新扩展出的结点已经被其他数字标记过
 那么 表示搜索的两端碰撞
 那么 循环结束
 如果 新的 s 个结点是从开始结点扩展来的
 那么 将这个 s 个结点标记为 1 并且入队 q 
如果 新的 s 个结点是从目标结点扩展来的
 那么 将这个 s 个结点标记为 2 并且入队 q
}