算法4 A* 算法和8puzzle

A* 算法(A-start search algorithm)是一种用于图形遍历和路径搜索的启发式搜索算法最佳优先算法,它诞生于一个人工智能项目 Shakey,旨在研发一个能自动走路的智能机器人,此算法于1968年公开,并且在当下也拥有广泛的应用。

A* 算法通过维护始于起始节点的路径树,并一次扩展一条路径直到满足其终止条件,在每次循环中A* 需要确定扩展的路径,即选择最小化路径。选择依据以下成本函数:

其中n是路径上的下一个节点;g(n) 是从起始点到n的路径成本;h(n)是启发式函数,用于估算n到目标节点的最便宜成本。

A* 的典型运用是使用优先队列每次选择最小f(n)(成本)的的节点,此优先队列被称为开放集。在算法的每个步骤中,从队列中删除具有最低成本的节点,并更新其相邻节的fg值后将相邻节点添加到队列中,直到删除的节点是目标节点后结束。

根据不同的启发式函数h(n),得到的路径也不相同,正确的启发式函数才能保证找到最短路径,即h(n)必须小于等于n到目标节点的实际距离,常用的启发式函数是曼哈顿距离

碧蓝航线脚本

这是几年前用按键精灵写的碧蓝航线脚本,用于肝赤城和加贺,每天挂几个小时挂了大半个月才刷出来.....

狗网游们基本都是挂一周就出了,已经可以断定我是个合格的非酋了o(╥﹏╥)o

此脚本比较核心功能之一是它的寻路方式,使用A* 算法避开小怪直达boss。首先是需要识别游戏场景并构成数字地图(二维数组):

  1. 人物初始位置为开始节点start,boss位置为目标节点goal
  2. 绿色的岛屿(障碍物);
  3. 蓝色的海面或者小怪残骸(可行走,成本设为1);
  4. 小怪(可行走,进入战斗且根据不同等级的小怪需要消耗相应的弹药数,所以小怪方格的通过成本可以设的高一些,尽量避免战斗);
  5. 子弹(可行走,并恢复弹药量,可以将弹药方格的行走成本设置为较小的数,例如-1,尽量走经过有弹药路线避免弹尽粮绝,不过为了简单起见,我们不考虑弹尽粮绝的情况);

将地图构成二维数组如下:(0表示可行走的海面,1表示玩家角色,2表示不可行走的岛屿,3表示小怪,4表示boss)

1
2
3
4
0 0 0 0 0 2 2 2
0 0 0 0 0 0 2 2
2 0 3 0 0 0 0 4
0 0 1 3 0 0 3 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
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
/**
* 使用了algs4.jar:
* MinPQ,可以用PriorityQueue代替。
* StdOut,可以用System.out.println()代替。
* In,可以使用Scanner代替。
*/
public class AzurLane {

private static final int SEA = 0;
private static final int PLAYER = 1;
private static final int ISLAND = 2;
private static final int ZAKU = 3; // 扎古?杂鱼? 233
private static final int BOSS = 4;

private static final int COST_SEA = 1;
private static final int COST_ZAKU = 20;

/**
* 注意map[]保存的是行,即y值;map[][]保存的是列,即x值。
*/
public static int[][] aStar(int[][] map) {
int[] r = findStartAndGoal(map);
Node start = new Node(null, r[0], r[1]);
Node goal = new Node(null, r[2], r[3]);

Map<Node, Integer> gScore = new HashMap<>();
gScore.put(start, 0);

Map<Node, Integer> fScore = new HashMap<>();
fScore.put(start, h(start, goal));

// 最小优先队列,参数中的lambda表达式为Comparator,比较两个节点的f值
MinPQ<Node> openSet = new MinPQ<>((o1, o2) -> fScore.get(o1) - fScore.get(o2));
openSet.insert(start);

while (openSet.size() > 0) {
// 得到f值最小的节点
Node current = openSet.delMin();
// 如果节点是目标节点,表示已经找到一条可达路径,返回此路径
if (current.equals(goal)) return tracePath(current);
// 遍历周边节点
// 1. 如果周边节点是当前节点的父节点,表示走了一条返回的路,跳过此节点
// 2. 如果同一节点的g值小于上一次记录的g值,将节点放入开放列表。反之,表示包含此节点的路径在上次
// 已经估算过,无需重复估算。这也杜绝了没有任何一条路径能抵达目标节点时可能出现死循环的情况。因此
// 可以断定gScroe这个哈希表拥有“closedSet”的功能。
for (Node neighbor : neighbors(map, current)) {
if (neighbor.equals(current.p)) continue;
int tentativeG = gScore.get(current) + cost(map, neighbor);
if (!gScore.containsKey(neighbor) || tentativeG < gScore.get(neighbor)) {
gScore.put(neighbor, tentativeG);
fScore.put(neighbor, tentativeG + h(neighbor, goal));
openSet.insert(neighbor);
}
}
}
// 开放列表中已经没有估算节点,即目标位置不可达。
return null;
}

/**
* 节点的通过成本
*/
private static int cost(int[][] map, Node node) {
return map[node.y][node.x] == ZAKU ? COST_ZAKU : COST_SEA;
}

/**
* 启发式函数,使用曼哈顿距离(Manhattan distance)。
* 因为只能往上下左右四个方向移动,所以曼哈顿距离正好是dx + dy。
*/
private static int h(Node node, Node goal) {
return Math.abs(goal.x - node.x) + Math.abs(goal.y - node.y);
}

/**
* 溯源路径,返回二维数组:{{x1, y1}, {x2, y2}, {x3, y3}, ... }
*/
private static int[][] tracePath(Node node) {
List<Node> nodes = new ArrayList<>();
do {
nodes.add(0, node);
node = node.p;
} while (node != null);

int[][] path = new int[nodes.size()][2];
for (int i = 0; i < nodes.size(); i++) {
Node n = nodes.get(i);
path[i][0] = n.x;
path[i][1] = n.y;
}
return path;
}

/**
* 寻找地图中的开始节点坐标和目标节点坐标:{startX, startY, goalX, goalY}
*/
private static int[] findStartAndGoal(int[][] map) {
// r[0],r[1] 表示角色坐标,r[2],r[3] 表示boss坐标
int[] r = new int[] { -1, -1, -1, -1 };
for (int y = 0; y < map.length; y++) {
for (int x = 0; x < map[y].length; x++) {
switch (map[y][x]) {
case PLAYER:
r[0] = x;
r[1] = y;
break;
case BOSS:
r[2] = x;
r[3] = y;
break;
case ISLAND:
case ZAKU:
case SEA:
break;
default:
throw new IllegalArgumentException("地图错误,包含未知信息!");
}
}
}
if (r[0] == -1 || r[2] == -1)
throw new IllegalArgumentException("地图错误,未找到起始点或终点");
return r;
}

/**
* 查找周边节点,要排除障碍物(岛屿)。
*/
private static List<Node> neighbors(int[][] map, Node node) {
List<Node> neighbors = new ArrayList<>();
int r = node.x + 1;
int t = node.y - 1;
int b = node.y + 1;
int l = node.x - 1;

if (r < map[node.y].length && map[node.y][r] != ISLAND)
neighbors.add(new Node(node, r, node.y));
if (t >= 0 && map[t][node.x] != ISLAND)
neighbors.add(new Node(node, node.x, t));
if (b < map.length && map[b][node.x] != ISLAND)
neighbors.add(new Node(node, node.x, b));
if (l >= 0 && map[node.y][l] != ISLAND)
neighbors.add(new Node(node, l, node.y));

return neighbors;
}

private static final class Node {
private final Node p; // 父节点
private final int y, x; // 坐标

private Node(Node p, int x, int y) {
this.x = x;
this.y = y;
this.p = p;
}

public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return x == node.x && y == node.y;
}

public int hashCode() {
return Objects.hash(x, y);
}
}

// test
public static void main(String[] args) {
In in = new In(args[0]);
int row = in.readInt();
int col = in.readInt();
int[][] map = new int[row][col];
StdOut.println(row + " " + col);
for (int y = 0; y < row; y++) {
for (int x = 0; x < col; x++) {
map[y][x] = in.readInt();
StdOut.print(map[y][x] + " ");
}
StdOut.println();
}
StdOut.println();

int[][] path = aStar(map);
if (path == null) {
StdOut.println("no path!");
return;
}

// print the path
for (int i = 0; i < path.length; i++) {
int x = path[i][0];
int y = path[i][1];
map[y][x] = '*';
}
for (int y = 0; y < row; y++) {
for (int x = 0; x < col; x++) {
if (map[y][x] == '*')
StdOut.print("* ");
else StdOut.print(map[y][x] + " ");
}
StdOut.println();
}
}
}

运行方式:准备以下格式的txt,第一行的两个数组表示4x8的二维数组:

1
2
3
4
5
4 8
0 0 0 0 0 2 2 2
0 0 0 0 0 0 2 2
2 0 3 0 0 0 0 4
0 0 1 3 0 0 3 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
40
41
$java-algs4 AzurLane map4x8-01.txt
4 8
0 0 0 0 0 2 2 2
0 0 0 0 0 0 2 2
2 0 3 0 0 0 0 4
0 0 1 3 0 0 3 0

0 0 0 0 0 2 2 2
0 * * * * * 2 2
2 * 3 0 0 * * *
0 * * 3 0 0 3 0

$java-algs4 AzurLane map4x8-unsolvable01.txt
4 8
0 0 0 0 0 2 2 2
0 0 0 0 0 0 2 2
2 0 3 0 0 0 2 4
0 0 1 3 0 0 3 2

no path!

$java-algs4 AzurLane map4x16-01.txt
4 16
0 0 3 2 2 0 2 0 2 0 2 0 0 2 2 2
0 0 0 0 2 0 0 3 0 3 0 3 0 2 4 0
2 0 3 0 3 0 3 0 3 3 0 0 0 2 2 0
1 0 0 3 2 0 0 0 0 2 0 2 0 3 0 0

0 0 3 2 2 0 2 0 2 0 2 0 0 2 2 2
0 * * * 2 * * * * * * 3 0 2 * *
2 * 3 * * * 3 0 3 3 * * * 2 2 *
* * 0 3 2 0 0 0 0 2 0 2 * * * *

java-algs4 AzurLane map4x16-unsolvable01.txt
4 16
0 0 3 2 2 0 2 0 2 0 2 0 0 2 2 2
0 0 0 0 2 0 0 3 0 3 0 3 0 2 4 0
2 0 3 0 3 0 3 0 3 3 0 0 0 2 2 2
1 0 0 3 2 0 0 0 0 2 0 2 0 3 0 0

no path!

强烈推荐这个项目,演示了各类路径搜索算法的动画:https://github.com/qiao/PathFinding.js

注意事项(正确的处理路径不可达的情况)

部分A* 算法的使用了一个closeSet列表,通常是一个集合而非哈希表。它的作用是存储所有已估算过的节点(从openSet中删除后立马放入closed中)。

做法是在扩展路径时,即遍历周边节点时通过判断周边节点是否在closedSet中,如果已在closedSet中则放弃这个周边节点,也是为了避免A*算法找不到目标节点进入死循环的方式。

但是需要注意这样做的代价是极高的!因为判断元素是否在集合中,需要对集合中的每一个节点对象调用equals方法,这直接产生了平方级的额外开销!正确的处理方式应该像上面代码那样使用哈希表,这也是我将g值存储在单独的HashMap而不是Node节点中的主要原因

8puzzle

此案例是coursera上的一个作业,下面相关代码的得分为100。

相信大部分人小时候都玩过这类游戏(15puzzle在线试玩: https://15puzzle.netlify.app/):

我们的目标是用A* 算法求出 解决puzzle 的最短步骤和路径,例如:

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
~> java-algs4 Solver puzzle04.txt
Minimum number of moves = 4
3
0 1 3
4 2 5
7 8 6

3
1 0 3
4 2 5
7 8 6

3
1 2 3
4 0 5
7 8 6

3
1 2 3
4 5 0
7 8 6

3
1 2 3
4 5 6
7 8 0

实现分析

可以将每种排列方式看成一个节点,而周边节点则是滑块移动后可能出现的排列方式:

而启发式函数我们有两种选择:

  • 汉明距离:错位位置的方块数量。
  • 曼哈顿距离:错误位置的方块与其正确位置的距离。

处理不可解的情况

puzzle存在不可解的情况,例如:

1
2
3
1 2 3
4 5 6
8 7 0

如何判断一个puzzle是否可解,涉及到抽象代数(近世代数),目前我没有相关的数学知识,所以这里我直接给出一些结论:

  • 边长为k的puzzle游戏和交错群 同构(其中An由n!/2个不同排列的集合组成);

  • 由上面结论得:Npuzzle游戏可解的排序方式有 (N+1)!/2种,即所有排列方式的一半;

  • 交换puzzle中的任意两个滑块的位置(不包括空白),即可将puzzle变为可解或变为不可解;

https://en.wikipedia.org/wiki/15_puzzle 中有相关论文。

对于能否判断puzzle是否可解在接下来的A* 算法中是非常重要的,因为每一种排列方式都可能作为A* 算法的节点,而15puzzle不可解的情况有 ~ 种;意味着使用A*算法去解一个不可解的15puzzle将使得程序无法停下,并在短的时间内将内存撑爆,因为A* 算法会遍历完这~ 种排列。

为了避免这种情况,我们需要交换puzzle中的任意一对元素获得puzzle2,同时对这两个puzzle进行A* 搜索,其中一个puzzle必然得到解决。

代码实现

实现方式和上面的碧蓝航线脚本基本一致,区别puzzle存在判断是否可解的方式,所以没有使用“closedSet”,而是同时对两个puzzle进行搜索。

下面代码在Coursera上为满分,测试数据可到上面给出的作业地址上下载项目取得。

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
public class Board {

private final int n;
private final int[][] data;
private int hamming;
private int manhattan;
private int blankRow = 0;
private int blankCol = 0;
private List<Board> neighbors;

// create a board from an n-by-n array of tiles,
// where tiles[row][col] = tile at (row, col)
public Board(int[][] tiles) {
if (tiles == null) throw new IllegalArgumentException();
n = tiles.length;
data = new int[n][n];
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
data[i][j] = tiles[i][j];
if (data[i][j] != ++k && data[i][j] != 0) hamming++;
int number = data[i][j];
if (number == 0) {
blankRow = i;
blankCol = j;
continue;
}
int row = (number - 1) / n;
int col = (number - 1) % n;
manhattan += Math.abs(row - i) + Math.abs(col - j);
}
}
}

// string representation of this board
public String toString() {
if (n == 0) return "0";
StringBuilder sb = new StringBuilder();
sb.append(n + "\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
sb.append(" " + data[i][j] + " ");
if (i < n - 1) sb.append("\n");
}
return sb.toString();
}

// board dimension n
public int dimension() {
return n;
}

// number of tiles out of place
public int hamming() {
return hamming;
}

// sum of Manhattan distances between tiles and goal
public int manhattan() {
return manhattan;
}

// is this board the goal board?
public boolean isGoal() {
return hamming == 0;
}

// does this board equal y?
public boolean equals(Object y) {
if (this == y) return true;
if (y == null || getClass() != y.getClass()) return false;
Board board = (Board) y;
if (n != board.n) return false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (data[i][j] != board.data[i][j]) {
return false;
}
}
}
return true;
}

// all neighboring boards
public Iterable<Board> neighbors() {
if (neighbors != null) return neighbors;
neighbors = new ArrayList<>();
int top = blankRow - 1;
int bottom = blankRow + 1;
int left = blankCol - 1;
int right = blankCol + 1;
if (right < n) neighbors.add(createNeighbor(blankRow, right));
if (bottom < n) neighbors.add(createNeighbor(bottom, blankCol));
if (left >= 0) neighbors.add(createNeighbor(blankRow, left));
if (top >= 0) neighbors.add(createNeighbor(top, blankCol));
return neighbors;
}

private Board createNeighbor(int row, int col) {
return copy(blankRow, blankCol, row, col);
}

private Board copy(int row, int col, int row2, int col2) {
exch(data, row, col, row2, col2);
Board result = new Board(data);
exch(data, row, col, row2, col2);
return result;
}

// a board that is obtained by exchanging any pair of tiles
public Board twin() {
int ai = -1, aj = -1, bi = -1, bj = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (data[i][j] == 0) continue;
if (ai == -1) {
ai = i;
aj = j;
}
else if (bi == -1) {
bi = i;
bj = j;
}
else break;
}
}
return ai >= 0 && bi >= 0 ? copy(ai, aj, bi, bj) : new Board(data);
}

private static void exch(int[][] a, int ai, int aj, int bi, int bj) {
int temp = a[ai][aj];
a[ai][aj] = a[bi][bj];
a[bi][bj] = temp;
}
}
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
public class Solver {

private List<Board> solution;
private boolean isSolvable;

// find a solution to the initial board (using the A* algorithm)
public Solver(Board start) {
if (start == null) throw new IllegalArgumentException();
Board twin = start.twin();
MinPQ<Node> openSet1 = new MinPQ<>();
MinPQ<Node> openSet2 = new MinPQ<>();
openSet1.insert(new Node(start, null));
openSet2.insert(new Node(twin, null));
while (openSet1.size() > 0 && openSet2.size() > 0) {
Node current1 = openSet1.delMin();
Node current2 = openSet2.delMin();
if (current1.board.isGoal()) {
isSolvable = true;
reconstructPath(current1);
return;
}
if (current2.board.isGoal()) {
isSolvable = false;
return;
}

for (Board neighbor : current1.board.neighbors()) {
if (current1.p != null && neighbor.equals(current1.p.board)) continue;
openSet1.insert(new Node(neighbor, current1));
}

for (Board neighbor : current2.board.neighbors()) {
if (current2.p != null && neighbor.equals(current2.p.board)) continue;
openSet2.insert(new Node(neighbor, current2));
}
}
}

private void reconstructPath(Node node) {
solution = new ArrayList<>();
do {
solution.add(0, node.board);
node = node.p;
} while (node != null);
}

// is the initial board solvable? (see below)
public boolean isSolvable() {
return isSolvable;
}

// min number of moves to solve initial board; -1 if unsolvable
public int moves() {
return solution == null ? -1 : solution.size() - 1;
}

// sequence of boards in a shortest solution; null if unsolvable
public Iterable<Board> solution() {
return solution;
}

private static class Node implements Comparable<Node> {
private final Board board;
private final int g;
private final int f;
private final Node p;

public Node(Board board, Node p) {
this.board = board;
this.p = p;
g = p == null ? 1 : p.g + 1;
f = g + board.manhattan();
}

public int compareTo(Node y) {
return f - y.f;
}
}

// test client (see below)
public static void main(String[] args) {
// create initial board from file
In in = new In(args[0]);
int n = in.readInt();
int[][] tiles = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
tiles[i][j] = in.readInt();
Board initial = new Board(tiles);

// solve the puzzle
Solver solver = new Solver(initial);

// print solution to standard output
if (!solver.isSolvable())
StdOut.println("No solution possible");
else {
StdOut.println("Minimum number of moves = " + solver.moves());
for (Board board : solver.solution())
StdOut.println(board);
}
}
}