BFS状态图搜索

BFS状态图搜索 八数码问题 

指定初始状态和目标状态，计算最少移动步数

如图输入样例
2 8 3 1 6 4 7 0 5
1 2 3 8 0 4 7 6 5
输出样例
5

在BFS里最重要的就是判重，在这道题里，从初始状态开始，每一移动一步都是新的状态，总共有9! = 362880 种状态，如果不去掉重复的状态，复杂度大大增加，必定会超时。那么状态图如何判重呢，定义 visited[9][9][9][9][9][9][9][9][9] 或 visited[876543210] 用来记录已走过的状态都不太现实，可以使用数学方法 ” 康托展开(Cantor expansion) ” 来判重。

康托展开

定义 visited[362880] ，0~8 这 9 个数字全排列共 9! = 362880 个，其中最小的是 012345678，放在第0个位置，即 visited[0] ，最大的是 876543210，放在最后一个位置，即 visited[362880-1]。对于不同的状态，我们只需要计算出他在这些数字组合中排多大。

举例：判断 2031 在 0~3 这4个数字全排列中排多大

2 → 比 2 小的有 0、1
        当该位为 0 时，后面 3 位有 3! 种组合 (0123、0132、0213、0231、0312、0321)
        当该位为 1 时，后面 3 位有 3! 种组合 (1023、1032、1203、1230、1302、1320)
0 → 非 2 且比 0 小的没有
3 → 非 2、0 且比 3 小的有 1
        当该位为 1 时，后面 1 位有 1! 种组合 (2013)
1 → 非 2、0、3 且比 1 小的没有

2 × 3! + 0 × 2! + 1 × 1! + 0 × 0! = 13，所以2031是第14大的数 

C++代码实现

#include 

using namespace std;

const int LEN = 362880; //9!=362880个状态
struct node { //状态图结构
    int state[9];
    int dis; //记录到起点距离，即移动次数
};
//以左上角为(0,0)
int dir[4][2] = {{0,  -1}, //dir[0][]上
                 {0,  1}, //dir[1][]下
                 {-1, 0}, //dir[2][]左
                 {1,  0}}; //dir[3][]右
int visited[LEN] = {0}; //记录某状态是否已走过
int start[9]; //初始状态
int goal[9]; //目标状态
int factory[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; //factory[n]=n!
bool Cantor(int str[], int n); //康托展开函数，用于判重
int bfs();

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;
}

//康托展开判重
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]) //访问过返回0
        return 0;
    else { //未访问过返回1且标记已访问
        visited[result] = 1;
        return 1;
    }
}

int bfs() {
    node head;
    memcpy(head.state, start, sizeof(head.state)); //状态数组复制
    head.dis = 0;
    queue q;
    Cantor(head.state, 9); //起点标记已访问
    q.push(head);
    while (!q.empty()) {
        head = q.front();
        q.pop();
        if (memcmp(head.state, goal, sizeof(goal)) == 0) //判断是否已经是目标状态
            return head.dis;
        //若不是目标状态则开始移动
        int i; //记录0元素位置
        for (i = 0; i < 9; ++i)
            if (head.state[i] == 0)
                break;
        //一维转二维
        int x = i % 3;
        int y = i / 3;
        for (int j = 0; j < 4; ++j) { //每次移动都有四种选择，即上下左右
            int xx = x + dir[j][0];
            int yy = y + dir[j][1];
            int ii = xx + 3 * yy; //二维转一维
            if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) {
                node newnode;
                memcpy(&newnode, &head, sizeof(node)); 
                swap(newnode.state[i], newnode.state[ii]); //移动，即交换0元素和其他元素
                newnode.dis++;
                if (Cantor(newnode.state, 9)) //康托展开判重
                    q.push(newnode);
            }
        }
    }
    return -1;
}

---

参考罗勇军《算法竞赛从入门到进阶》