问题描述

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

A*思路

A*算法是对BFS的一种优化。

问题可以看作初始状态为$s$，终点状态为$t$，在状态空间内寻找一个从$s\to t$的最短路径。

我们设从起点到终点的实际为距离$f_{*}(x)$，从起点到该状态的实际距离为$g_{*}(x)$，从该状态到终点的实际距离为$h_{*}(x)$，由此我们可以得到$f_{*}(x)=g_{*}(x)+h_{*}(x)$。

但是很明显，我们很难去得到实际距离，所以我们设$f(x),g(x),h(x)$为上述三个值的预估值，即估价函数。

在八数码问题中，我们可以把$g(x)$设计为移动的步数，$h(x)$设计为不在目标位置的数字的数目，由此预估到终点状态的距离。

当$h(x)\leq h_{*}(x)$时，A*总能求出最优解，此时我们称$h$是可接纳的。上述条件下如果$h$满足三角形不等式，则算法不会重复地将节点加入队列。

我们通过建立优先队列，将各状态按照$f(x)$大小建立小根堆。不断拓展$f(x)$最小的$x$，并将合法状态加入队列，直到取出目标状态$t$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int dx[5] = {0, 1, -1, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};

struct Matrix {
    int d[5][5];

    bool operator < (Matrix x) const {
        for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                if ( d[i][j] != x.d[i][j] )
                    return d[i][j] < x.d[i][j];

        return false;
    }
} fi, st;

int h(Matrix x) {
    int ret = 0;
    for ( int i = 1; i <= 3; ++i )
        for ( int j = 1; j <= 3; ++j )
            if ( x.d[i][j] != st.d[i][j] )
                ++ret;

    return ret;
}

struct Node {
    Matrix a;
    int t;
    bool operator < (Node x) const { 
        return t + h(a) > x.t + h(x.a); 
    }
} x;

int fx, fy;
priority_queue<Node> q;
set<Matrix> s;

int main(void) {
    st.d[1][1] = 1;
    st.d[1][2] = 2;
    st.d[1][3] = 3;
    st.d[2][1] = 8;
    st.d[2][2] = 0;
    st.d[2][3] = 4;
    st.d[3][1] = 7;
    st.d[3][2] = 6;
    st.d[3][3] = 5;

    for ( int i = 1; i <= 3; ++i )
        for ( int j = 1; j <= 3; ++j ) {
            fi.d[i][j] = getchar() - '0';
        }

    q.push({fi, 0});

    while ( !q.empty() ) {
        x = q.top();
        q.pop();
        
        if ( !h(x.a) ) {
            cout << x.t;

            return 0;
        }

        for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                if ( !x.a.d[i][j] ) {
                    fx = i;
                    fy = j;
                }

        for ( int i = 1; i <= 4; ++i ) {
            int nx = fx + dx[i];
            int ny = fy + dy[i];

              if ( nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3 ) {
                swap(x.a.d[fx][fy], x.a.d[nx][ny]);

                if ( !s.count(x.a) ) {
                    s.insert(x.a);
                    q.push({x.a, x.t + 1});
                }

                swap(x.a.d[fx][fy], x.a.d[nx][ny]);
            }
        }
    }

    return 0;
}