A*解决八数码问题

Astars算法的基本思想是：
定义合适的代价函数gx和启发式函数hx，当gx和hx都满足条件时，Astars算法就可以保证得到最优解。
我对状态的定义如下：
状态由名为Node的结构体表示，其中包含一个三行三列的二维数组A，A中0的坐标x0、y0，Astars算法相关的fx、gx、hx参数组成。
gx意味到达该状态移动的次数，hx为启发式函数，这里设定为不在位的数字的数量，这个条件从不高估从节点x到目标节点的实际代价。八数字中的0表示空位。

struct Node {
    int A[3][3];
    int x0;
    int y0;
    int gx;
    int hx; // 其实不用存
    int fx;
    bool visited;// 最后版本无用

    Node(Node* existNode) {
        // 复制已有对象
        if (existNode != nullptr) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    this->A[i][j] = existNode->A[i][j];
                }
            }
            this->x0 = existNode->x0;
            this->y0 = existNode->y0;
            this->gx = existNode->gx;
            this->hx = existNode->hx;
            this->fx = existNode->fx;
            this->visited = false;
        }
    }
    Node() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                this->A[i][j] = i + j * 3;
            }
        }
        this->x0 = 0;
        this->y0 = 0;
        this->gx = 0;
        this->hx = 0;
        this->fx = 0;
        this->visited = false;
    }
}

在运行过程中，现对初始状态进行判断，若不是目标状态，进行Astars算法（调用search函数）。先通过x0,y0定位0的位置，进行状态拓展（expand函数，根据当前状态复制一个node，然后调整相关参数，包括移动的两个数字，0的坐标，fx gx hx)。之后通过排序算法选取fx最小的状态，进行判断。
这个过程中涉及到两个关键问题：一是如何避免产生重复的状态，二是排序的效率问题（代码通过洛谷的相应题目进行检验，排序效率过低会Time Limit Exceed）。

对于“如何避免产生重复状态”的问题，8数码问题可以用字符串区分不同状态的字符串。采用同一种方式给各个状态编码。我在Node类内定义了一个序列化函数serialize()，将当前状态的数组转换为一个字符串。额外使用unordered_set对转换后的序列进行哈希存储。当要拓展新状态时，查找unordered_set对象中，是否有与新状态序列化的结果相同的序列。查找到则不拓展这个状态。

unordered_set<string> visitedStates;
Node* newNode = expand(x + 1, y, current, B);
if (visitedStates.find(newNode->serialize()) == visitedStates.end()) {
    nodeQueue.push(newNode);
    visitedStates.insert(newNode->serialize());
}

对于“排序的效率问题”，我先在忽略效率问题的前提下，采用了O(n)的遍历策略。之后（现版本）采用了std标准库中的priority_queue，自定义了CompareNode进行元素优先级的比较。具体定义为：

priority_queue<Node*, vector<Node*>, CompareNode> nodeQueue;

Node表示容器中包含的元素类型为Node；vector<Node*>为优先队列的容器模板；CompareNode为自定义的比较逻辑，不实现时默认使用std::less创造最大堆。我们这里要使fx最小的排最前面，优先取出，因此用Node1->fx > Node2->fx。具体定义为

struct CompareNode {
    // priority_queue默认会调用std::less，最终构成最大堆
    // 当定义比较器为 CompareNode 且 CompareNode::operator() 返回 true 时，
    // priority_queue 会认为第一个参数比第二个参数优先级低，因此不会把它放在堆顶
    bool operator()(Node* a, Node* b) {
        return a->fx > b->fx;
    }
};

各个元素在被取出后从优先队列中删除。
另外，虽然行列的设置只要统一，行列反了也不影响，如果反了，就是在对矩阵转置，目标状态和当前状态对应的两个矩阵都会转置，在解题逻辑中没有影响。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
#include <string>

using namespace std;

// 之后要获取0的位置
struct Node {
    int A[3][3];
    int x0;
    int y0;
    int gx;
    int hx; // 其实不用存
    int fx;

    Node(Node* existNode) {
        // 复制已有对象
        if (existNode != nullptr) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    this->A[i][j] = existNode->A[i][j];
                }
            }
            this->x0 = existNode->x0;
            this->y0 = existNode->y0;
            this->gx = existNode->gx;
            this->hx = existNode->hx;
            this->fx = existNode->fx;
        }
    }
    Node() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                this->A[i][j] = i + j * 3;
            }
        }
        this->x0 = 0;
        this->y0 = 0;
        this->gx = 0;
        this->hx = 0;
        this->fx = 0;
    }

    // 序列化状态为一个字符串，用于哈希集合存储
    string serialize() const {
        string s;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                s += to_string(A[i][j]);
            }
        }
        return s;
    }
};

struct CompareNode {
    // priority_queue默认会调用<，最终构成最大堆
    // 当定义比较器为 CompareNode 且 CompareNode::operator() 返回 true 时，
    // priority_queue 会认为第一个参数比第二个参数优先级低，因此不会把它放在堆顶
    bool operator()(Node* a, Node* b) {
        return a->fx > b->fx;
    }
};

int compareMap(Node* node, int target[3][3]) {
    // 比较
    int count = 0;
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 3; i++) {
            // 由于数组插入的差异，二者横纵相反
            if (target[i][j] != 0 && node->A[i][j] != target[i][j]) {
                count += 1;
            }
        }
    }
    return count;
}

Node* expand(int tx, int ty, Node* node, int target[3][3]) {
    Node* newNode = new Node(node);
    newNode->A[node->x0][node->y0] = newNode->A[tx][ty];
    newNode->A[tx][ty] = 0;
    newNode->x0 = tx;
    newNode->y0 = ty;
    newNode->gx = node->gx + 1; // 步数加一
    newNode->hx = compareMap(newNode, target);
    newNode->fx = newNode->gx + newNode->hx;
    return newNode;
}

int search(Node* node, int target[3][3]) {
    // 初始状态非目标状态，开始搜索
    priority_queue<Node*, vector<Node*>, CompareNode> nodeQueue;
    unordered_set<string> visitedStates;

    nodeQueue.push(node);
    visitedStates.insert(node->serialize());

    while (!nodeQueue.empty()) {
        Node* current = nodeQueue.top();
        nodeQueue.pop();

        if (compareMap(current, target) == 0)
            return current->gx;

        int x = current->x0;
        int y = current->y0;

        if (x <= 1) {
            Node* newNode = expand(x + 1, y, current, target);
            if (visitedStates.find(newNode->serialize()) == visitedStates.end()) {
                nodeQueue.push(newNode);
                visitedStates.insert(newNode->serialize());
            }
            else {
                delete newNode;
            }
        }
        if (x >= 1) {
            Node* newNode = expand(x - 1, y, current, target);
            if (visitedStates.find(newNode->serialize()) == visitedStates.end()) {
                nodeQueue.push(newNode);
                visitedStates.insert(newNode->serialize());
            }
            else {
                delete newNode;
            }
        }
        if (y <= 1) {
            Node* newNode = expand(x, y + 1, current, target);
            if (visitedStates.find(newNode->serialize()) == visitedStates.end()) {
                nodeQueue.push(newNode);
                visitedStates.insert(newNode->serialize());
            }
            else {
                delete newNode;
            }
        }
        if (y >= 1) {
            Node* newNode = expand(x, y - 1, current, target);
            if (visitedStates.find(newNode->serialize()) == visitedStates.end()) {
                nodeQueue.push(newNode);
                visitedStates.insert(newNode->serialize());
            }
            else {
                delete newNode;
            }
        }
        // 删除当前结点
        delete current;

    }
    // 理论上不会到这，未找到解决方案
    return -1;
}

int main() {
    Node* initS = new Node;
    char temp = '0';
    for (int i = 0; i < 3; i++) {//行循环
        for (int j = 0; j < 3; j++) {//列循环
            //cin >> initS->A[i][j];
            cin >> temp;
            initS->A[i][j] = (int)temp - (int)'0';
            if (initS->A[i][j] == 0) {
                initS->x0 = i;
                initS->y0 = j;
            }
        }
    }

    // 洛谷题中定义的状态
    int C[9] = { 1, 2, 3, 8, 0, 4, 7, 6, 5 };
    // 其实用数组预定义后，由于用i+3*j访问数组，遍历先后顺序都是一样的赋值情况。
    int B2[3][3];
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 3; i++) {
            // i是行，j是列
            B2[i][j] = C[3 * i + j];
        }
    }

    initS->gx = 0;
    initS->hx = compareMap(initS, B2);
    cout << search(initS, B2) << endl;

    return 0;
}