【OI学习笔记】状态图搜索

• BFS搜索处理的对象有很多种（根据题目而定），除了数它还可能是一个状态，对于状态空间的就叫做状态图搜索。

• 状态空间搜索一般是找到一条从初始状态到最终状态的一条最优路径，可以归结为隐式图的搜索问题，图中的节点就是在搜索过程中的状态。

八数码问题

• 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格（输入用‘0’表示）。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局（如图5.1.1-1所示），任务1：问最小移动步数，若无法到达输出-1；任务2：给出数码的移动序列。该问题称八数码难题或者重排九宫问题。

• 输入样例：
  1 2 3 0 8 4 7 6 5
  1 0 3 8 2 4 7 6 5

• 输出样例：
  2

• 不难把八数码问题归结为图上的最短路问题，图的“结点”就是9个格子中的滑块编号（从上到下、从左到右把它们放到一个包含9个元素的数组中）。无权图上的最短路问题可以用BFS求解。从初始状态出发，每次搜索转移状态，一层层搜索，渐渐接近目标状态，那么到达目标状态时经过的步数就是最短路径。

• 这道题目主要的难点就是判断重复，显然直接判断矩阵最坏情况是比较9!*9!（9!=362880）次，如此暴力判断重复不可行，一定会超时，故使用哈希方法，字符串存储数码，然后使用康托展开来判断重复。

*康拓展开

• 康托展开是一个全排列到一个自然数的双射，常用于构建Hash表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，设有n个数{1,2,3,...,n}，可以有组成不同(n!种)的排列组合，康托展开表示的就是在n个不同元素的全排列中, 比当前排列组合小的个数，那么也可以表示当前排列组合在n个不同元素的全排列中的名次（当前的名次 = 比当前排列组合小的个数 + 1）。因此也是可逆的，先给出康托展开的公式：

$x = a[n] \times (n - 1)! + a[n - 1] \times (n - 2)! + ...+ a[i] \times (i- 1)! + ... + a[1] * 0!$

• 其中, a[i]为整数，（注意：i从右往左数）并且0 <= a[i] <= i, 0 <= i < n, 表示当前未出现的的元素中排第几个，这就是康托展开。

• 假设有一个排列{1,2,3}，则其排列组合及其相应的康托展开值如下：

• 举个例子，在(1,2,3,4,5)5个数的排列组合中，计算 34152的康托展开值。

• 首位是3，则小于3的数有两个，为1和2，a[5] = 2，则首位小于3的所有排列组合为 $a[5] \times (5-1)!$

• 第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此 a[4] = 2

• 第三位是1，则在其之后小于1的数有0个，所以 a[3] = 0

• 第四位是5，则在其之后小于5的数有1个，为2，所以 a[2] = 1

• 最后一位就不用计算啦，因为在它之后已经没有数了，所以 a[1] 固定为0

• 根据公式：
  $x = 2 \times 4! + 2 \times 3! + 0 \times 2! + 1 \times 1! + 0 \times 0! = 2 \times 24 + 2 \times 6 + 1 = 61$

• 所以比 34152 小的组合有61个，即34152是排第62。

*逆康托展开

• 一开始已经提过了，康托展开是一个全排列到一个自然数的双射，因此是可逆的。即对于上述例子，在(1,2,3,4,5)给出61可以算出起排列组合为34152。由上述的计算过程可以容易的逆推回来，具体过程如下：

• 用 61 / 4! = 2余13，说明 a[5] = 2 ,说明比首位小的数有2个，所以首位为3。

• 用 13 / 3! = 2余1，说明 a[4] = 2 ，说明在第二位之后小于第二位的数有2个，所以第二位为4。

• 用 1 / 2! = 0余1，说明 a[3] = 0 ，说明在第三位之后没有小于第三位的数，所以第三位为1。

• 用 1 / 1! = 1余0，说明 a[2] = 1 ，说明在第二位之后小于第四位的数有1个，所以第四位为5。

• 最后一位自然就是剩下的数2啦。

• 通过以上分析，所求排列组合为 34152。

- 如下面的程序就用“BFS+Cantor”就解决了八数码问题：

• （BFS中用STL的queue实现）

//DC Songxingan
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int LEN = 362888; //状态共9!=362880种
struct node
{
    int state[9]; //记录一个八数码的排列，即一个状态
    int dis;      //记录到起点的距离
};

int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
//左、上、右、下顺时针方向。左上角坐标是(0,0)
int visited[LEN] = {0};
//与每个状态对应的记录，Cantor函数对它置数，并判重
int start[9]; //开始状态
int goal[9];  //目标状态
long int factory[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
//Cantor用到的常数
bool Cantor(int str[], int n)
{ //用康托展开判重
    long result = 0;
    for (int i = 0; i < n; i++)
    {
        int counted = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (str[i] > str[j]) //当前未出现的元素中是排在第几个
                ++counted;
        }
        result += counted * factory[n - i - 1];
    }
    if (!visited[result])
    { //没有被访问过
        visited[result] = 1;
        return 1;
    }
    else
        return 0;
}
int bfs()
{
    node head;
    memcpy(head.state, start, sizeof(head.state)); //复制起点的状态
    head.dis = 0;
    queue<node> q; //队列中放状态
    Cantor(head.state, 9);
    //用康托展开判重，目的是对起点的visited[]赋初值
    q.push(head); //第一个进队列的是起点状态

    while (!q.empty())
    { //处理队列
        head = q.front();
        q.pop();
        //可在此处打印head.state，看弹出队列的情况
        int z;
        for (z = 0; z < 9; z++)     //找这个状态中元素0的位置
            if (head.state[z] == 0) //找到了
                break;
        //转化为二维，左上角是原点(0, 0)。
        int x = z % 3; //横坐标
        int y = z / 3; //纵坐标
        for (int i = 0; i < 4; i++)
        {
            //上、下、左、右最多可能有4个新状态
            int newx = x + dir[i][0]; //元素0转移后的新坐标
            int newy = y + dir[i][1];
            int nz = newx + 3 * newy; //转化为一维
            if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3)
            { //未越界
                node newnode;
                memcpy(&newnode, &head, sizeof(struct node));
                //复制这新的状态
                swap(newnode.state[z], newnode.state[nz]);
                //把0移动到新的位置
                newnode.dis++;
                if (memcmp(newnode.state, goal, sizeof(goal)) == 0)
                    //与目标状态对比
                    return newnode.dis;       //到达目标状态，返回距离，结束
                if (Cantor(newnode.state, 9)) //用康托展开判重
                    q.push(newnode);          //把新的状态放进队列
            }
        }
    }
    return -1; //没找到
}
int main()
{
    for (int i = 0; i < 9; i++)
        cin >> start[i]; //初始状态
    for (int i = 0; i < 9; i++)
        cin >> goal[i]; //目标状态
    int num = bfs();
    if (num != -1)
        cout << num << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}

• 注意到这一道题，其实有很多方法解决，例如：双向广搜、A*、IDA等等。八数码问题只有9！种状态，对于更大的问题，例如44的15数码问题，就有16!≈2×1013种状态，就需要更好的方法，具体可见：https://www.cnblogs.com/zufezzt/p/5659276.html（八境界）