再解八数码 - A*算法

hhh距离上一篇八数码问题已经过去好久了，今天才贴上用A*的解法，不出意外，作为返校前的最后一篇博客

上一篇博客：平淡无奇的八数码难题 已经实现如何用单向bfs + map做八数码，然而这种做法的效率实在是太慢了，所以这里介绍另一种解法：A*算法。

A*算法是一种启发式搜索，引入了一个估价函数：$f(x) = g(x) + h(x)$，每一步搜索的顺序由估值函数的大小决定。

这题估值函数的计算方法为：走到当前状态所经历的步数 + 理想步数，而理想步数我们可以使用曼哈顿距离，即每一个位置的数要走到它相对应的位置的横纵坐标差的绝对值之和。

计算曼哈顿距离：

int f(string state)
{
    int res = 0;
    for (int i = 0; i < state.size(); i ++ )
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }

    return res;
}

完整代码：

相信都看得懂

#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

typedef pair<int, string> PIS;
#define x first
#define y second

int f(string state)
{
    int res = 0;
    for (int i = 0; i < state.size(); i ++ )
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }

    return res;
}

int bfs(string start)
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    string end = "12345678x";

    unordered_map<string, int> dist;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;

    heap.push({f(start), start});
    dist[start] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        string state = t.y;
        if (state == end) return dist[state];

        int x, y;
        for (int i = 0; i < state.size(); i ++ )
            if (state[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        
        string source = state;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(state[x * 3 + y], state[a * 3 + b]);
                if (!dist.count(state) || dist[state] > dist[source] + 1)
                {
                    dist[state] = dist[source] + 1;
                    heap.push({dist[state] + f(state), state});
                }
                swap(state[x * 3 + y], state[a * 3 + b]);
            }
        }
    }

    return -1;
}

int main()
{
    string start, seq;
    char c;
    while (cin >> c)
    {
        start += c;
        if (c != 'x') seq += c;
    }
    
    int cnt = 0;
    for(int i = 0 ; i < 8 ; i ++)
        for(int j = i + 1 ; j < 8 ; j++)
            if(seq[i] > seq[j])
                cnt++;

    if (cnt % 2) cout << "-1" << endl;
    else cout << bfs(start) << endl;

    return 0;
}

Q.E.D.