CedarHomeArchivesTagsCategories
A* 八数码解法
|ACMSEARCH

八数码问题 A* 算法

分析

@ analyse:
对于每一个状态设计对应结构体，
- 状态去重：
每种状态使用decimal number去重
- open表：
使用优先队列（小根堆），选取堆顶元素。
- close表：
使用vector

如果一个状态在open表中和close表中都没有出现，则将该状态加入open表中

如果一个状态只在open表中出现，则检查该状态与表中的状态谁更优，保存更优者

如果一个状态只在close表中出现，检查该状态与close表中的状态谁更优，如果更优，则把当前状态移动至open中，并更新最优值及路径

解决方案及构造

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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
/******************************************
    > File Name: EX_A.cpp
    > Author: universal42
    > Mail: universal42@163.com 
    > Created Time: 2019年05月09日 星期四 08时18分41秒
 ******************************************/
/*
    @ 要求：
        - 输出初始状态到目标状态的过程
        
*/

#include <bits/stdc++.h>
#define ll long long int
#define inf 0x3f3f3f3f
#define LOCAL
#define DEBUG
#define TEST
using namespace std;

/*
    @ attr:
        - state[3][3]:结点状态数组
        - x y        :0坐标位置
        - step       :节点深度
        - key        :结点估值
        - parent     :当前结点的父节点
*/
struct State
{
    int state[3][3];
    int x, y;
    int step;
    int key;
    State *parent;
    friend bool operator<(const State &a, const State &b)
    {
        return a.key > b.key;
    }
} start, goal;
typedef State node;
int goalcode;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void out_Path(node x);

priority_queue<node, vector<node>> open;
vector<node> close;
/*
    @ 编码到结点指针的映射
    @ 没有出现的结点其指针值为0
*/
map<int, node *> open_hash;
map<int, node *> close_hash;
/*
    @ 状态编码 状态压缩
*/
int encode(int state[][3])
{
    int res = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            res = res * 10 + state[i][j];
        }
    }
    return res;
}

int distance(int a[][3])
{
    int res = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            res += !(a[i][j] == goal.state[i][j]);
        }
    }
    return res;
}
void bfs()
{
    start.step = 0;
    start.key = start.step + distance(start.state);
    start.parent = nullptr;
    open.push(start);
    while (!open.empty())
    {
        node *f = new node();
        memcpy(f->state, open.top().state, sizeof(f->state));

        f->parent = open.top().parent;
        f->step = open.top().step;
        f->x = open.top().x;
        f->y = open.top().y;
        f->key = open.top().key;
        open.pop();

        if (encode(f->state) == goalcode)
        {
            out_Path(*f);
            return;
        }

        for (int i = 0; i < 4; i++)
        {
            int fx = f->x + dx[i];
            int fy = f->y + dy[i];
            //检查是否越界
            if (fx >= 0 && fy >= 0 && fx < 3 && fy < 3)
            {
                node t = *f;
                swap(t.state[fx][fy], t.state[t.x][t.y]);
                //移动后结点状态吗
                int code = encode(t.state);
                //两个表中都没出现
                if (!open_hash[code] && !close_hash[code])
                {
                    //add
                    node *x = new node();
                    x->x = fx;
                    x->y = fy;
                    x->step = (t.step + 1);
                    memcpy(x->state, t.state, sizeof(x->state));
                    x->key = t.step + 1 + distance(t.state);
                    x->parent = &(*f);
                    open.push(*x);
                    open_hash[code] = x;
                }
                else if (open_hash[code])
                {
                    //在Open表中，比较最优值
                    node x = *open_hash[code];
                    if (t.step + 1 < x.step)
                    {
                        //更优
                        memcpy(x.state, t.state, sizeof(x.state));
                        x.step = t.step + 1;
                        x.key = t.step + 1 + distance(t.state);
                        x.parent = t.parent;
                        priority_queue<node, vector<node>> tmp;
                        while (!open.empty())
                        {
                            tmp.push(open.top());
                            open.pop();
                        }
                        while (!tmp.empty())
                        {
                            open.push(tmp.top());
                            tmp.pop();
                        }
                    }
                }
                else
                {
                    node x = *close_hash[code];
                    if (t.step + 1 < x.step)
                    {
                        memcpy(x.state, t.state, sizeof(x.state));
                        x.step = t.step + 1;
                        x.key = t.step + 1 + distance(x.state);
                        x.parent = t.parent;
                        open.push(x);
                        close_hash[code] = nullptr;
                        open_hash[code] = &x;
                    }
                }
            }
        }
    }
}
/*
    @ 输出初始状态到目标状态的路径
*/
void out_Path(node x)
{
    int step = 0;
    vector<node> path;
    node *p = &x;
    while (p)
    {
        path.push_back(*p);
        p = p->parent;
    }
    printf("Success!\n");
    for (int cnt = path.size() - 1; cnt >= 0; cnt--)
    {
        printf("Step %d:\n", ++step);
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                printf("%d ", path[cnt].state[i][j]);
            }
            printf("\n");
        }
    }
}
void solve()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%d", &start.state[i][j]);
            if (start.state[i][j] == 0)
            {
                start.x = i;
                start.y = j;
            }
        }
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%d", &goal.state[i][j]);
            if (goal.state[i][j] == 0)
            {
                goal.x = i;
                goal.y = j;
            }
        }
    }
#ifdef DEBUGa
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            printf("%d", goal.state[i][j]);
        }
    }
#endif
    goalcode = encode(goal.state);
    bfs();

#ifdef TESTi
    // do something.
    node s1, s2, s3;
    s1.parent = nullptr;
    int cnt = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            s1.state[i][j] = ++cnt;
        }
    }
    s2.parent = &s1;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            s2.state[i][j] = ++cnt;
        }
    }
    s3.parent = &s2;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            s3.state[i][j] = ++cnt;
        }
    }
    out_Path(s3);
#endif
}
int main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
#endif
    solve();
    return 0;
}

版本二

这里给出另外一个版本的A*八数码问题的C++代码，不保证正确性（笔者在某些样例中并没有获得结果）。

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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

#define N 3
#include "stdlib.h"
#include <cstdio>
static int B[N][N] = {{3,1,2}, {8, 4, 5}, {6, 7, 0}};

typedef struct node
{
    int s[N][N];
    int value;
    int parent;
} state;
state open[100], close[100];
int f, r, f1, r1;

void change(int a[N][N], state b[], int l)
{
    int i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            a[i][j] = b[l].s[i][j];
}
int com(int A[N][N], int C[N][N])
{
    int i, j, a;
    a = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (A[i][j] != C[i][j])
                a++;
    return (a);
}
int depth(state A[], int i)
{
    int a;
    a = 0;
    while (i != 0)
    {
        i = A[i].parent;
        a++;
    }
    return (a + 1);
}
void sort()
{
    int i, j, k, l, l1, l2;
    state A;
    for (i = f; i < r - 1; i++)
    {
        k = i;
        for (j = i + 1; j < r; j++)
            if (open[j].value < open[k].value)
                k = j;
        for (l1 = 0; l1 < N; l1++)
            for (l2 = 0; l2 < N; l2++)
            {
                A.s[l1][l2] = open[k].s[l1][l2];
                open[k].s[l1][l2] = open[i].s[l1][l2];
                open[i].s[l1][l2] = A.s[l1][l2];
            }
        A.value = open[k].value;
        open[k].value = open[i].value;
        open[i].value = A.value;
        A.parent = open[k].parent;
        open[k].parent = open[i].parent;
        open[i].parent = A.parent;
        for (l = f; l < r; l++)
            if (open[l].parent == k)
                open[l].parent = i;
    }
}
void heuristic_search1(int A[N][N])
{
    int i, j, k, l, l1, l2, val;
    i = j = 0;
    //open 表中查找当前状态current_state
    while (i < r)
        if (com(A, open[i].s) != 0)
            i++;
        else
            break;
    //close 表中查找当前状态current_state
    while (j < r1)
        if (com(A, close[i].s) != 0)
            j++;
        else
            break;
    //当前状态A既不在open中，也不在close中
    if (i >= r && j >= r1)
    {
        //计算启发值
        val = com(A, B) + depth(open, f - 1) + 1;
        for (l1 = 0; l1 < N; l1++)
            for (l2 = 0; l2 < N; l2++)
                open[r].s[l1][l2] = A[l1][l2];
        //当前状态入队
        open[r].value = val;
        open[r].parent = f - 1;
        r++;
    }
    else if (i < r) //当前状态在open表中
    {
        if (depth(open, f - 1) + 1 < depth(open, i))
        {
            //当前结点价值更优，
            r++;
            for (l1 = 0; l1 < N; l1++)
                for (l2 = 0; l2 < N; l2++)
                    open[i].s[l1][l2] = A[l1][l2];
            open[i].value = val;
            open[r].parent = f - 1;//修改指针
        }
    }
    else //当前状态在close表中
    {
        if (depth(close, f1) + 1 < depth(close, j))
        {
            //
            r++;
            for (l1 = 0; l1 < N; l1++)
                for (l2 = 0; l2 < N; l2++)
                    open[r].s[l1][l2] = A[l1][l2];
            open[r].value = val;
            open[r].parent = f - 1;
            for (l = j; l < r1; l++)
            {
                for (l1 = 0; l1 < N; l1++)
                    for (l2 = 0; l2 < N; l2++)
                        close[l].s[l1][l2] = close[l + 1].s[l1][l2];
                close[l].value = close[l + 1].value;
                close[l].parent = close[l + 1].parent;
                r1--;
            }
        }
    }
}
void heuristic_search(int search[N][N])
{
    int i, j, k, A[N][N], h, b, c, d, e, val;
    int l1, l2, road[20];
    //像open表中加入初始状态
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
        {
            open[0].s[i][j] = search[i][j];
            close[0].s[i][j] = 0;
        }
    //状态的价值为 当前节点深度+距离估值
    open[0].value = depth(open, 0) + com(open[0].s, B);
    //初始状态父节点为-1
    open[0].parent = -1;
    f = f1 = r1 = 0;
    r = 1;
    while (f != r)
    {
        e = f;
        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                close[r1].s[i][j] = open[f].s[i][j];
        close[r1].value = open[f].value;
        close[r1].parent = open[f].parent;
        r1++;
        f++;
        change(A, open, e);
        if (com(A, B) == 0)
        {
            printf("\n  success!");
            k = e;
            l1 = 0;
            while (k != -1)
            {
                road[l1] = k;
                l1++;
                k = open[k].parent;
            }
            for (k = l1; k >= 0; k--)
            {
                printf("\tStep %d\n", l1 - k);
                for (i = 0; i < N; i++)
                {
                    for (j = 0; j < N; j++)
                        if (open[road[k]].s[i][j] != 0)
                            printf("\t%d", open[road[k]].s[i][j]);
                        else
                            printf("\t ");
                    printf("\n");
                }
            }
            return;
        }
        for (i = 0; i < N; i++)
        {
            for (j = 0; j < N; j++)
                if (A[i][j] == 0)
                    break;
            if (j < N)
                break;
        }
        //down
        if (i + 1 < N)
        {
            //三变量交换
            b = A[i + 1][j];
            A[i + 1][j] = A[i][j];
            A[i][j] = b;
            //处理新状态
            heuristic_search1(A);
        }
        //e=f
        //open中首元素赋值
        change(A, open, e);
        //up
        if (i - 1 > -1)
        {
            b = A[i - 1][j];
            A[i - 1][j] = A[i][j];
            A[i][j] = b;
            heuristic_search1(A);
        }
        change(A, open, e);
        //right
        if (j + 1 < N)
        {
            b = A[i][j + 1];
            A[i][j + 1] = A[i][j];
            A[i][j] = b;
            heuristic_search1(A);
        }
        change(A, open, e);
        //left
        if (j - 1 > -1)
        {
            b = A[i][j - 1];
            A[i][j - 1] = A[i][j];
            A[i][j] = b;
            heuristic_search1(A);
        }
        change(A, open, e);
        //提取最优值到队首
        sort();
    }
    printf("\n   failure");
}
int main()
{
    int A[N][N], i, j;
    printf("\n please input the original state:\n");
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            scanf("%d", &A[i][j]);
    heuristic_search(A);
    return 0;
}

以上代码添加少许注释，方便阅读（我拿到的时候没有任何注释，笔者凭靠自己的理解所写，如有错误可以联系我反馈，再次感谢）。
上述两份代码均采用了同位置的数字不同的个数来作为启发函数的一部分，另一部分采用节点深度，即结构体中的step（与普通bfs的步数一致），也可使用parent属性遍历获取深度

1
2
3
4
5
6
7
8
9
int getDepth(node x){
    int depth=0;
    node *p=&x;
    while(p!=null){
        depth++;
        p=p->parent;
    }
    return depth;
}

A*估价函数

八数码的问题还可以使用曼哈顿距离来构造估值函数，在此不再赘述。

Author: universal42
Link: https://universal4s.github.io/2019/05/10/A-star-eight/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
SEARCHAIBFS