<link rel="dns-prefetch" href="//www.imooc.com" /> <link rel="dns-prefetch" href="//img.imooc.com" />是什么意思

以下是使用A*算法实现八数码问题的C语言代码，其中使用了优先队列来管理状态节点。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000000

int start[9] = {2, 8, 3, 1, 6, 4, 7, 0, 5}; // 初始状态
int target[9] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; // 目标状态

int f[MAXN]; // f[i]表示第i个状态的估价函数值
int g[MAXN]; // g[i]表示从初始状态到第i个状态的实际代价
int h[MAXN]; // h[i]表示从第i个状态到目标状态的估计代价
int pre[MAXN]; // pre[i]表示第i个状态的前驱状态
int vis[MAXN]; // vis[i]表示第i个状态是否已经访问过

struct node
{
    int state[9];
    int pos; // 空格位置
    int id; // 状态编号
    int f; // 估价函数值
    bool operator<(const node &o) const
    {
        return f > o.f;
    }
};

node q[MAXN]; // 优先队列
int front, rear;

int geth(int *state) // 计算估价函数值h
{
    int res = 0;
    for (int i = 0; i < 9; i++)
        if (state[i] != 0)
            res += abs((state[i] - 1) / 3 - i / 3) + abs((state[i] - 1) % 3 - i % 3);
    return res;
}

int getid(int *state) // 获取状态编号
{
    int res = 0;
    for (int i = 0; i < 9; i++)
        res = res * 10 + state[i];
    return res;
}

void print(int id) // 输出路径
{
    if (pre[id] == -1)
        return;
    print(pre[id]);
    for (int i = 0; i < 9; i++)
        printf("%d%c", q[id].state[i], i == 8 ? '\n' : ' ');
}

void bfs() // A*算法
{
    memset(vis, 0, sizeof(vis));
    memset(f, 0x3f, sizeof(f));
    front = rear = 0;
    q[rear].id = getid(start);
    memcpy(q[rear].state, start, sizeof(start));
    q[rear].pos = 7;
    q[rear].f = f[q[rear].id] = geth(start);
    g[q[rear].id] = 0;
    pre[q[rear].id] = -1;
    rear++;
    while (front < rear)
    {
        node u = q[front++];
        vis[u.id] = 1;
        if (u.id == getid(target))
        {
            print(u.id);
            return;
        }
        int p = u.pos;
        int x = p / 3, y = p % 3;
        if (x > 0) // 上移
        {
            int v[9];
            memcpy(v, u.state, sizeof(u.state));
            v[p] = v[3 * (x - 1) + y];
            v[3 * (x - 1) + y] = 0;
            int id = getid(v);
            if (!vis[id] && f[id] > g[u.id] + geth(v))
            {
                pre[id] = u.id;
                g[id] = g[u.id] + 1;
                h[id] = geth(v);
                f[id] = g[id] + h[id];
                q[rear].id = id;
                memcpy(q[rear].state, v, sizeof(v));
                q[rear].pos = 3 * (x - 1) + y;
                q[rear].f = f[id];
                rear++;
            }
        }
        if (x < 2) // 下移
        {
            int v[9];
            memcpy(v, u.state, sizeof(u.state));
            v[p] = v[3 * (x + 1) + y];
            v[3 * (x + 1) + y] = 0;
            int id = getid(v);
            if (!vis[id] && f[id] > g[u.id] + geth(v))
            {
                pre[id] = u.id;
                g[id] = g[u.id] + 1;
                h[id] = geth(v);
                f[id] = g[id] + h[id];
                q[rear].id = id;
                memcpy(q[rear].state, v, sizeof(v));
                q[rear].pos = 3 * (x + 1) + y;
                q[rear].f = f[id];
                rear++;
            }
        }
        if (y > 0) // 左移
        {
            int v[9];
            memcpy(v, u.state, sizeof(u.state));
            v[p] = v[3 * x + y - 1];
            v[3 * x + y - 1] = 0;
            int id = getid(v);
            if (!vis[id] && f[id] > g[u.id] + geth(v))
            {
                pre[id] = u.id;
                g[id] = g[u.id] + 1;
                h[id] = geth(v);
                f[id] = g[id] + h[id];
                q[rear].id = id;
                memcpy(q[rear].state, v, sizeof(v));
                q[rear].pos = 3 * x + y - 1;
                q[rear].f = f[id];
                rear++;
            }
        }
        if (y < 2) // 右移
        {
            int v[9];
            memcpy(v, u.state, sizeof(u.state));
            v[p] = v[3 * x + y + 1];
            v[3 * x + y + 1] = 0;
            int id = getid(v);
            if (!vis[id] && f[id] > g[u.id] + geth(v))
            {
                pre[id] = u.id;
                g[id] = g[u.id] + 1;
                h[id] = geth(v);
                f[id] = g[id] + h[id];
                q[rear].id = id;
                memcpy(q[rear].state, v, sizeof(v));
                q[rear].pos = 3 * x + y + 1;
                q[rear].f = f[id];
                rear++;
            }
        }
    }
}

int main()
{
    bfs();
    return 0;
}