A*算法解决15数码问题详细解析(附完整代码)_a*搜索算法求解 15 数码问题

一、15数码问题

15数码问题：一个4*4的16宫格棋盘上，摆放有15个将牌，每一个都刻有1-15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。所要求解的问题：是给定一种初始布局(初始状态)和一个目标布局(目标状态),问如何移动数码实现从初始状态到目标状态的转变。

二、A*算法

2.1 什么是A*算法？

A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到达到目标。在搜索过程中需要根据启发函数来帮助选择搜索路径。

2.2 启发函数设计

• 启发函数：f(n) = g(n) + P(n)
  g(n):从初始结点 s 到结点 n 路径的耗散值
  P(n):每一个数码与其目标位置间的距离的总和

三、解决思路

①将初始状态结点加入OPEN
②找到OPEN中f(n)最小的结点 n
③如果该结点（n）达到目标状态，回溯结果进行输出，程序结束。否则进行下一步
④从OPEN中移除结点n，加入CLOSED，遍历n所有邻近结点（即可以移动到达的位置所对应的状态），设置这些邻近结点父结点为n，并给其它字段赋值，判断邻近结点是否在CLOSED，若在则不进行操作，否则进行下一步
⑤将该邻近结点加入OPEN，返回②

四、详细代码

4.1Github代码下载地址

Github仓库，点击进入

4.2 定义每次状态的结点类Node：

import java.util.Arrays;

/**
 * @program: A*
 * @description:
 * @author: wtongxue
 * @create: 2021-11-29 12:35
 **/
public class Node {

    /**
     * 0数码坐标行
     */
    private int row;

    /**
     * 0数码坐标列
     */
    private int col;

    /**
     * f(n)
     */
    private int f;

    /**
     * g(n)
     */
    private int g;

    /**
     * 结点状态矩阵
     */
    private int[][] matrix;

    /**
     * 父结点
     */
    Node parent;

    public Node(){}

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public Node(int row, int col, int[][] matrix) {
        this.row = row;
        this.col = col;
        this.matrix = matrix;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }

    public int getG() {
        return g;
    }

    public void setG(int g) {
        this.g = g;
    }

    public int getF() {
        return f;
    }

    public void setF(int f) {
        this.f = f;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

}

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

4.3 解决类

import java.util.*;

/**
 * @program: A*
 * @description:
 * @author: wtongxue
 * @create: 2021-11-28 13:50
 **/
public class Solution {

    /*
        启发函数：f(n) = g(n) + P(n)
        g(n):从初始结点 s 到结点 n 路径的耗散值
        P(n):每一个数码与其目标位置间的距离的总和
     */

    /**
     * 初始状态
     */
    int[][] matrix = {{5, 1, 2, 4}, {9, 6, 3, 8}, {13, 15, 10, 11}, {14, 0, 7, 12}};

    /**
     * 目标状态
     */
    int[][] result = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 0}};

    /**
     * OPEN表
     */
    ArrayList<Node> open = new ArrayList<>();

    /**
     * CLOSED表
     */
    ArrayList<Node> closed = new ArrayList<>();

    public Solution() {
        int row=0;
        int col=0;
        //查找初始状态中空位数码0的坐标
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==0){
                    row = i;
                    col = j;
                    break;
                }
            }
        }
        //构造初始状态结点加入OPEN表
        Node initStateNode = new Node(row, col, matrix);
        open.add(initStateNode);
    }

    /**
     * 以矩阵形式输出结点
     *
     * @param matrix
     */
    private void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.printf("%-6d", matrix[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    /**
     * 复制矩阵
     *
     * @param matrix
     * @return
     */
    private int[][] cloneMatrix(int[][] matrix) {
        int[][] newMatrix = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < newMatrix.length; i++) {
            for (int j = 0; j < newMatrix[0].length; j++) {
                newMatrix[i][j] = matrix[i][j];
            }
        }
        return newMatrix;
    }

    /**
     * 计算f(n)
     *
     * @return
     */
    private int calculate(Node node) {
        int pN = 0;
        //计算P(n)
        int[][] matrix = node.getMatrix();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0 && matrix[i][j] != (4 * i) + j + 1) {
                    //目标坐标行数
                    int targetRow = matrix[i][j] / 4;
                    //目标坐标列数
                    int targetCol = matrix[i][j] - (targetRow * 4) - 1;
                    if (targetCol==-1){
                        targetRow-=1;
                        targetCol = 3;
                    }
                    pN += Math.abs(targetRow - i) + Math.abs(targetCol - j);
                }
            }
        }
        return node.getG() + pN;
    }

    /**
     * 更新OPEN表
     *
     * @return
     */
    public void updateOpen(Node node) {
        if (node.getRow()>0){
            //上移
            addNode(node,node.getRow()-1,node.getCol());
        }

        if (node.getRow()<result.length-1){
            //下移
            addNode(node,node.getRow()+1,node.getCol());
        }

        if (node.getCol()>0){
            //左移
            addNode(node,node.getRow(),node.getCol()-1);
        }

        if (node.getCol()<result[0].length-1){
            //右移
            addNode(node,node.getRow(),node.getCol()+1);
        }
    }

    /**
     * 判断结点状态，将符合要求的结点加入OPEN表
     *
     * @param parentNode
     * @param row
     * @param col
     */
    public void addNode(Node parentNode,int row,int col){
        Node node = new Node(row,col);
        //复制矩阵，更新复制后的矩阵为移动后的状态
        int[][] nodeMatrix = cloneMatrix(parentNode.getMatrix());
        int tmp = nodeMatrix[node.getRow()][node.getCol()];
        nodeMatrix[node.getRow()][node.getCol()] = nodeMatrix[parentNode.getRow()][parentNode.getCol()];
        nodeMatrix[parentNode.getRow()][parentNode.getCol()] = tmp;
        node.setMatrix(nodeMatrix);
        //设置结点字段值
        node.setParent(parentNode);
        node.setF(calculate(node));
        node.setG(node.getG()+1);
        if (isIn(closed,node)){
            //如果在CLOSED表中，代表以及拓展过该结点，不进行操作
            return;
        }
        if (!isIn(open,node)) {
            //如果不在OPEN表，加入OPEN表
            open.add(node);
        }
    }

    /**
     * 判断是否到达目标状态
     *
     * @param node
     * @return
     */
    public boolean isTarget(Node node) {
        int[][] nodeMatrix = node.getMatrix();
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                if (result[i][j] != nodeMatrix[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断是否在open或closed表中
     *
     * @param table
     * @param node
     * @return
     */
    public boolean isIn(ArrayList<Node> table,Node node){
        for (Node tableNode : table){
            if (isSameMatrix(tableNode.getMatrix(),node.getMatrix())){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断两个状态的数码矩阵是否相同
     *
     * @param matrix1
     * @param matrix2
     * @return
     */
    public boolean isSameMatrix(int[][]matrix1,int[][]matrix2){
        for (int i=0;i<matrix2.length;i++){
            for (int j=0;j<matrix2[0].length;j++){
                if (matrix1[i][j]!=matrix2[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        while (!solution.open.isEmpty()){
            //将OPEN表按照f(n)递增排序
            Collections.sort(solution.open, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return o1.getF() - o2.getF();
                }
            });

            //选择f(n)最小的结点
            Node firstNode = solution.open.get(0);

            if (solution.isTarget(firstNode)){
                //达到目标状态
                Stack<Node> stack = new Stack<>();
                Node node = firstNode;
                while (node!=null){
                    //回溯结果
                    stack.push(node);
                    node = node.getParent();
                }
                //输出结果
                int step = 0;
                while (!stack.isEmpty()){
                    System.out.println("step:"+step++);
                    solution.printMatrix(stack.pop().getMatrix());
                }
                break;
            }else{
                //将结点n移出open表,加入closed表
                solution.closed.add(firstNode);
                solution.open.remove(0);
                //遍历结点n的邻近结点
                solution.updateOpen(firstNode);
            }
        }
    }

}


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