启发式搜索

还是从最简单的走网格开始吧，现在有一个包含障碍的方形网格，你需要求出从 S 点到 T 点的最短步数

很简单，不是吗？使用 BFS 就可以办到

但是，BFS 是一种盲目的搜索技术，它只会不断遍历周围的点，如果 T 点在 S 点的右上方，作为人的话肯定会把更多的精力放在往右上方搜索，一般这样能更快地找到路径，但是 BFS 并没有这种智能，那么能不能把这种智能交给程序呢？这就是启发式搜索，A*算法是比较简单的一种，可以认为是BFS和贪心的结合

尝试贪心思想

运用贪心法可进行如下处理：在处理队列中的点时，始终选取与终点的曼哈顿距离最短的点优先处理，这样循环往复，就能不断向终点逼近，而那些南辕北辙的点自然会在队列中被挤到后面去，不会浪费搜索资源

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
#include <bits/stdc++.h>
using namespace std;
const int M = 8, N = 10, INF = 0x3f3f3f3f;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int Manhattan_distance(int ax, int ay);
void print();
struct point
{
    int x, y;
    int dist, cost; // 到终点的距离 从起点到目前的距离
    int f = dist;   // 评估函数

    point() {}
    point(int x, int y, int cost) : x(x), y(y), dist(Manhattan_distance(x, y)), cost(cost) {}
    bool operator>(const point &rhs) const  // 运算符重载，根据 f 比较大小
    {
        return f > rhs.f;
    }

} S, T;
int board[M][N];
bool searched[M][N];
void A_start(point start)
{
    priority_queue<point, vector<point>, greater<point>> q; // 优先队列，f 小的排在前面

    q.push(start);
    board[start.x][start.y] = 1;

    while (!q.empty())
    {
        // print();
        point cur = q.top();
        q.pop();
        searched[cur.x][cur.y] = 1;
        for (int i = 0; i < 4; i++)
        {
            point next = point(cur.x + dx[i], cur.y + dy[i], cur.cost + 1);
            if (next.x < 0 || next.x >= M || next.y < 0 || next.y >= N)
                continue;
            if (board[next.x][next.y])
                continue;
            board[next.x][next.y] = next.f;
            q.push(next);
            if (next.x == T.x && next.y == T.y)
                return;
        }
    }
}
void print()
{
    int search_count = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (searched[i][j])
                search_count++;
            if (S.x == i && S.y == j)
                printf(" S");
            else if (T.x == i && T.y == j)
                printf(" T");
            else if (board[i][j] == -1)
                printf(" #");
            // else if(board[i][j])
            //     printf("  1");
            else
            {

                printf(" %d", (int)searched[i][j]);
            }
        }

        printf("\n");
    }
    printf("search_count = %d\n", search_count);
}
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
        {
            char tmp = getchar();
            while (tmp == '\n')
                tmp = getchar();
            if (tmp == '#')
                board[i][j] = -1;
            else if (tmp == 'S')
                S = point(i, j, 0);
            else if (tmp == 'T')
                T = point(i, j, INF);
        }
    A_start(S);
    print();
}
int Manhattan_distance(int ax, int ay)
{
    return abs(ax - T.x) + abs(ay - T.y);
}

听上去很好，不是吗？虽然这里也能找到终点，但是只有贪心还是不够的，这样很容易会陷入到局部最优中，搜一些不需要的点，而且有些题目中甚至无法到达终点

例如对于如下情况

1
2
3
4
5
6
7
8
..........
..........
..........
.S........
...#######
.........T
..........
..........

结果为

1
2
3
4
5
6
7
8
9
 0 0 0 0 0 0 1 1 1 1
 0 0 0 0 0 1 1 1 1 1
 0 0 0 0 0 1 1 1 1 1
 0 S 1 1 1 1 1 1 1 1
 0 0 1 # # # # # # #
 0 0 1 1 1 1 1 1 1 T
 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0
search_count = 31

1 为被处理过，0 为未处理过（包括还在队列里面的），可以看到，右上角的点其实意义不大，但是还是搜索了

A*：综合考虑过去与将来

而如果综合考虑 到当前的代价 与 到目标的距离 ，结果会好很多

1
2
// int f = dist;
int f = dist + cost; // 综合考虑过去与将来（滑稽）
1
2
3
4
5
6
7
8
9
 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0
 0 S 1 1 1 1 1 1 1 1
 0 1 1 # # # # # # #
 0 1 1 1 1 1 1 1 1 T
 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0
search_count = 19

这就是 A* 算法，下面给出它的一般性描述：

在搜索过程中，用一个估值函数对当前情况进行评估，得到最好的状态，从这个状态继续搜索直到到达目标

设 xx 为当前所在的状态，f(x)f(x) 为对 xx 的估值函数，有

f(x)=g(x)+h(x)f(x) = g(x) + h(x)

  • g(x)g(x) 表示从初识状态到 xx 的实际代价，它不体现 xx 和终点的关系

  • h(x)h(x) 表示 xx 到终点的最优路径的评估，它就是“启发式”信息，把 h(x)h(x) 称为启发函数，它决定了 A* 算法的优劣

特别注意的是 h(x)h(x) 不能某掉最优解

在上面的例子中，h(x)h(x) 就是曼哈顿距离，这也是一种简单而且常用的启发函数

通过上面的式子也可以看出 A* 算法同时包含了 BFS 与贪心算法

  • 如果 h(x)=0h(x)=0 ，f(x)=g(x)f(x) = g(x) ，会按距离一圈一圈搜索，这就是朴素 BFS
  • 如果 g(x)=0g(x)=0 ，f(x)=h(x)f(x) = h(x) ，这就是纯贪心

在八数码问题中使用 A* 算法

同样地，也可以在八数码中使用 A*算法

以不在目标位置的数码与目标位置的曼哈顿距离作为估值函数

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
#include <bits/stdc++.h>
// using namespace std;
const int N = 3, M = 4, MAX = 362880, TARGRT = 46233;
const int FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
const int dx[M] = {0, 1, 0, -1};
const int dy[M] = {1, 0, -1, 0};
const char dir[M] = {'r', 'd', 'l', 'u'};

struct Node
{
    int board[N][N]; // 0-8
    int x, y;        // 0的位置
    int g, h;        // g为当前步数，h为估价函数
    int Cantor;      // Cantor展开

    // 重载运算符，用于优先队列
    bool operator<(const Node &a) const
    {
        return g + h < a.g + a.h;
    }
};

struct Path
{
    int pre; // 前驱节点
    int dir; // 前驱节点到当前节点的移动方向
} path[MAX];

bool vis[MAX];

inline void swapNode(Node &a, Node &b)
{
    Node t = a;
    a = b;
    b = t;
}

inline void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

inline int abs(int x)
{
    return x > 0 ? x : -x;
}

// 手写优先队列
struct PriorityQueue
{
    Node q[MAX];
    int size;

    PriorityQueue()
    {
        size = 0;
    }

    void push(Node x)
    {
        q[++size] = x;
        int i = size;
        while (i > 1 && q[i] < q[i / 2])
        {
            swapNode(q[i], q[i / 2]);
            i /= 2;
        }
    }

    void pop()
    {
        q[1] = q[size--];
        int i = 1;
        while (i * 2 <= size)
        {
            int t = i;
            if (q[i * 2] < q[t])
                t = i * 2;
            if (i * 2 + 1 <= size && q[i * 2 + 1] < q[t])
                t = i * 2 + 1;
            if (t == i)
                break;
            swapNode(q[i], q[t]);
            i = t;
        }
    }

    Node top()
    {
        return q[1];
    }

    bool empty()
    {
        return size == 0;
    }

    void clear()
    {
        size = 0;
    }
} q;

inline int getCantor(Node e)
{

    int a[9], k = 0;

    for (int i = 0; i < N; i++) //将数据排成一排，便于计算
    {
        for (int j = 0; j < N; j++)
            a[k++] = e.board[i][j];
    }

    int x = 0;
    for (int i = 0; i < 9; i++)
    {
        int count = 0;
        for (int j = i + 1; j < 9; j++)
        {
            if (a[i] > a[j])
                count++;
        }
        x += FACT[9 - i - 1] * count;
    }
    return x;
}

inline int getH(Node e)
{
    int res = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (e.board[i][j] == 0)
                continue;
            int x = (e.board[i][j] - 1) / N;
            int y = (e.board[i][j] - 1) % N;
            res += abs(x - i) + abs(y - j);
        }
    }
    return res;
}

void printPath(int x)
{
    if (path[x].pre == -1)
    {
        // printf("%c", dir[path[x].dir]);
        return;
    }

    printPath(path[x].pre);
    printf("%c", dir[path[x].dir]);
}

void AStar(Node now)
{
    now.Cantor = getCantor(now);
    now.h = getH(now);
    q.push(now);
    vis[now.Cantor] = true;
    while (!q.empty())
    {
        Node now = q.top();
        q.pop();
        if (now.Cantor == TARGRT)
        {
            printPath(now.Cantor);
            printf("\n");
            return;
        }
        for (int i = 0; i < M; i++)
        {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;
            Node next = now;
            swap(next.board[now.x][now.y], next.board[nx][ny]);
            next.x = nx;
            next.y = ny;
            next.g++;
            next.Cantor = getCantor(next);
            next.h = getH(next);
            if (!vis[next.Cantor])
            {
                vis[next.Cantor] = true;
                path[next.Cantor].pre = now.Cantor;
                path[next.Cantor].dir = i;
                q.push(next);
                if (next.Cantor == TARGRT)
                {
                    printPath(next.Cantor);
                    printf("\n");
                    return;
                }
            }
        }
    }
}

inline void init()
{
    q.clear();
    memset(vis, false, sizeof(vis));
    memset(path, -1, sizeof(path));
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    char tmp[30];
    while (std::cin.getline(tmp, 30))
    {
        // 输入初始状态
        Node start = {0};
        int len = strlen(tmp);
        for (int i = 0, j = 0; i < len; i++)
        {
            if (tmp[i] == ' ')
                continue;
            if (tmp[i] == 'x')
            {
                // x设置为0,e点记录初始的x，y位置
                start.board[j / 3][j % 3] = 0;
                start.x = j / 3;
                start.y = j % 3;
            }
            else
            {
                start.board[j / 3][j % 3] = tmp[i] - '0';
            }
            j++;
        }

        // 初始化
        start.g = 0;
        start.h = getH(start);
        memset(vis, false, sizeof(vis));
        path[getCantor(start)].pre = -1;
        q.clear();

        // 求逆序数
        int k = 0;
        for (int i = 0; i < 9; i++)
        {
            if (start.board[i / 3][i % 3] == 0)
                continue;
            for (int j = 0; j < i; j++)
            {
                if (start.board[j / 3][j % 3] == 0)
                    continue;
                if (start.board[j / 3][j % 3] > start.board[i / 3][i % 3])
                    k++;
            }
        }
        if (k & 1)
        {
            printf("unsolvable\n");
        }
        else
        {
            AStar(start);
        }
    }
    return 0;
}