最近考完试了。闲下来就正好刷刷以前没刷完的搜索专题。

简单搜索就没啥好讲的啦。就是暴力bfs和dfs。

这篇博客是kuangbin搜索进阶的专题的总结

八数码问题太经典啦。通过它来学习搜索的进阶技巧就很舒服。

首先是最简单的康拓优化。

康托展开（Hash序列权值,可以用于序列打表：

int jc[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int cantor(int a[])//康托展开
{
    int ans = 0, k;
    for (int i = 0; i < 9; i++)
    {
        k=0;
        for (int j = i+1; j < 9; j++)
            if (a[i] > a[j]) k++;
        ans += k * jc[8-i];
    }
    return ans;
}

 关于八数码的解法：

1.康托展开+逆向BFS预处理

#include <bits/stdc++.h>
using namespace std;
const int N = 400000;
struct path
{
    char oper;
    int fa;
}p[N];
int jc[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int in[9];
int goal[]={1,2,3,4,5,6,7,8,9};
int vis[N];
int dic[4][2] = {1,0, -1,0, 0,1, 0,-1};

struct node
{
    int maze[9];
    int num;
};


int cantor(int a[])//康托展开
{
    int ans = 0, k;
    for (int i = 0; i < 9; i++)
    {
        k = 0;
        for (int j = i+1; j < 9; j++) if (a[i] > a[j]) k++;
        ans += k * jc[8-i];
    }
    return ans;
}

void bfs(int qin[])
{
    queue<node> q;
    vis[cantor(qin)] = 1;
    node st;
    for (int i = 0; i < 9; i++) st.maze[i] = qin[i];
    p[0].fa = -1;
    st.num = 8;
    q.push(st);
    while (!q.empty())
    {
        node top = q.front(); q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = top.num % 3 + dic[i][0];
            int ty = top.num / 3 + dic[i][1];
            if (tx < 0) continue;
            if (tx >= 3) continue;
            if (ty < 0) continue;
            if (ty >= 3) continue;
            node temp;
            memcpy(temp.maze, top.maze, sizeof(top.maze));
            temp.num = ty*3+tx;
            swap(temp.maze[top.num], temp.maze[temp.num]);
            int ct2 = cantor(temp.maze);
            int ct1 = cantor(top.maze);
            if (!vis[ct2])
            {
                vis[ct2] = 1;
                q.push(temp);
                if (i == 0) p[ct2].fa = ct1, p[ct2].oper = 'l';
                else if (i == 1) p[ct2].fa = ct1, p[ct2].oper = 'r';
                else if (i == 2) p[ct2].fa = ct1, p[ct2].oper = 'u';
                else if (i == 3) p[ct2].fa = ct1, p[ct2].oper = 'd';
                //cout << p[ct2].oper << endl;
            }
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    bfs(goal);
    char temp[9];
    while (cin >> temp[0] >> temp[1] >> temp[2] >> temp[3] >> temp[4] >>
           temp[5] >> temp[6] >> temp[7] >> temp[8])
    {
        for (int i = 0; i < 9; i++)
            if (temp[i] == 'x') in[i] = 9;
            else in[i] = temp[i]-'0';

        int cont = cantor(in);
        if (!vis[cont]) cout << "unsolvable" << endl;
        else
        {
            while (p[cont].fa != -1)
            {
                cout << p[cont].oper;
                cont = p[cont].fa;
            }
            cout << endl;
        }
    }
    return 0;
}

2.双向BFS+康托展开+逆序对判断（我之前是拓展再判断结果wa了好久，改成先判断再拓展就一发过了真的服了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 400000;
struct path
{
    char oper;
    int fa;
}p_st[N], p_ed[N];
struct node
{
    int maze[9];
    int num;
}st, ed;

int jc[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int in[9], goal[9] = {1,2,3,4,5,6,7,8,9};
int st_vis[N], ed_vis[N];
int st_mp[N], ed_mp[N];
int st_out, ed_out;
int dic[4][2] = {1,0, -1,0, 0,1, 0,-1};

void output1(int k)
{
    if(p_st[k].fa==-1) return ;
    else
    {
        output1(p_st[k].fa);
        cout << p_st[k].oper;
    }
}

void output2(int k)
{
    if(p_ed[k].fa==-1) return ;
    else
    {
        //cout << k << endl;
        cout << p_ed[k].oper;
        output2(p_ed[k].fa);
    }
}

int cantor(int a[])
{
    int ans = 0, k;
    for (int i = 0; i < 9; i++)
    {
        k = 0;
        for (int j = i+1; j < 9; j++) if (a[i] > a[j]) k++;
        ans += k * jc[8-i];
    }
    return ans;
}

void dbfs()
{
    memset(st_vis, 0, sizeof(st_vis));
    memset(ed_vis, 0, sizeof(ed_vis));
    queue<node> q1, q2;
    for (int i = 0; i < 9; i++) st.maze[i] = in[i], ed.maze[i] = goal[i];
    p_ed[0].fa = -1; ed_vis[0] = 1; ed.num = 8;
    p_st[cantor(st.maze)].fa = -1; st_vis[cantor(st.maze)] = 1;
    q1.push(st); q2.push(ed);

    while (!q1.empty() && !q2.empty())
    {
        node st_top = q1.front(); q1.pop();
        int st_cur = cantor(st_top.maze);
        if (ed_vis[st_cur])
        {
            st_out = st_cur;
            ed_out = st_cur;
            return ;
        }
        for (int i = 0; i < 4; i++)
        {
            int tx = st_top.num % 3 + dic[i][0];
            int ty = st_top.num / 3 + dic[i][1];
            if (tx < 0) continue;
            if (tx >= 3) continue;
            if (ty < 0) continue;
            if (ty >= 3) continue;
            node st_temp;
            memcpy(st_temp.maze, st_top.maze, sizeof(st_top.maze));
            st_temp.num = ty*3+tx;
            swap(st_temp.maze[st_top.num], st_temp.maze[st_temp.num]);
            int aft = cantor(st_temp.maze);

            if (!st_vis[aft])
            {
                st_vis[aft] = 1;
                q1.push(st_temp);
                if (i == 0) p_st[aft].fa = st_cur, p_st[aft].oper = 'r';
                else if (i == 1) p_st[aft].fa = st_cur, p_st[aft].oper = 'l';
                else if (i == 2) p_st[aft].fa = st_cur, p_st[aft].oper = 'd';
                else if (i == 3) p_st[aft].fa = st_cur, p_st[aft].oper = 'u';
            }
        }

        node ed_top = q2.front(); q2.pop();
        int ed_cur = cantor(ed_top.maze);
        if (st_vis[ed_cur])
        {
            st_out = ed_cur;
            ed_out = ed_cur;
            return ;
        }
        for (int i = 0; i < 4; i++)
        {
            int tx = ed_top.num % 3 + dic[i][0];
            int ty = ed_top.num / 3 + dic[i][1];
            if (tx < 0) continue;
            if (tx >= 3) continue;
            if (ty < 0) continue;
            if (ty >= 3) continue;
            node ed_temp;
            memcpy(ed_temp.maze, ed_top.maze, sizeof(ed_top.maze));
            ed_temp.num = ty*3+tx;
            swap(ed_temp.maze[ed_top.num], ed_temp.maze[ed_temp.num]);
            int aft = cantor(ed_temp.maze);
            if (!ed_vis[aft])
            {
                ed_vis[aft] = 1;
                q2.push(ed_temp);
                if (i == 0) p_ed[aft].fa = ed_cur, p_ed[aft].oper = 'l';
                else if (i == 1) p_ed[aft].fa = ed_cur, p_ed[aft].oper = 'r';
                else if (i == 2) p_ed[aft].fa = ed_cur, p_ed[aft].oper = 'u';
            }
        }
    }
}

int main()
{
    char temp[9];
    while (cin >> temp[0] >> temp[1] >> temp[2] >> temp[3] >> temp[4] >>
           temp[5] >> temp[6] >> temp[7] >> temp[8])
    {
        for (int i = 0; i < 9; i++)
            if (temp[i] == 'x') in[i] = 9, st.num = i;
            else in[i] = temp[i]-'0';
        int rev = 0;
        for (int i = 0; i < 9; i++)
            for (int j = i+1; j < 9; j++)
                if (in[i] == 9) continue;
                else if (in[i] > in[j]) rev++;
        if (rev & 1)
            cout << "unsolvable" << endl;
        else
        {
            dbfs();
            output1(st_out);
            output2(ed_out);
            cout << endl;
        }
    }
    return 0;
}