A*解决八数码问题

study
major
发布日期:   2024-11-12
更新日期:   2024-11-12
文章字数:   1.9k
阅读次数:   5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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对象中，是否有与新状态序列化的结果相同的序列。查找到则不拓展这个状态。

1
2
3
4
5
6
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进行元素优先级的比较。具体定义为：

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#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;
}

文章作者: Qijia Huang
文章链接: https://mys109hqj.github.io/2024/11/12/241112A-%E8%A7%A3%E5%86%B3%E5%85%AB%E6%95%B0%E7%A0%81%E9%97%AE%E9%A2%98/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Qijia Huang !
study
  目录