目录
隐式图的搜索问题(A*算法解决八数码)
一、实验要求
3х3九宫棋盘,放置数码为1~8的8个棋子,棋盘中留有一个空格,空格周围的棋子可以移动到空格中,从而改变棋盘的布局。根据给定初始布局和目标布局,移动棋子从初始布局到达目标布局,求解移动步骤并输出。请设计算法,使用合适的搜索策略,在较少的空间和时间代价下找到最短路径。
二、编程语言及开发环境
Java
JDK12
IntelliJ IDEA
三、项目设计思路
A*算法
public static int A_star(int[][] MT) {
int x0 = 0, y0 = 0;
for (x0 = 0; x0 < N; x0++) {
boolean flag = false;
for (y0 = 0; y0 < N; y0++) {
if (MT[x0][y0] == 0) {
flag = true;
break;
}
}
if (flag)
break;
}
Queue<node> q = new PriorityQueue<node>(cmp);
int[][] curmt = new int[N][];
int[][] markemt = new int[N][];
for (int r = 0; r < N; r++)
curmt[r] = MT[r].clone();
for (int r = 0; r < N; r++)
markemt[r] = MT[r].clone();
List<int[][]> path = new ArrayList<int[][]>();
path.add(MT);
node cur = new node(x0, y0, 0, 0, 0, curmt, path);
marke.add(markemt);
q.add(cur);
while (!q.isEmpty()) {
cur = (node) q.poll().clone();
boolean tag = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (cur.mt[i][j] != endMT[i][j]) {
tag = true;
}
}
}
if (!tag) {
System.out.println("共扩展了" + marke.size() + "个结点");
return cur.step;
}
for (int i = 0; i < 4; i++) {
node next = (node) cur.clone();
next.x = cur.x + dir[i][0];
next.y = cur.y + dir[i][1];
if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N) {
next.mt[cur.x][cur.y] = next.mt[next.x][next.y];
next.mt[next.x][next.y] = 0;
boolean mark = false;
for (int c = 0; c < marke.size(); c++) {
int x = 0, y = 0;
for (x = 0; x < N; x++) {
for (y = 0; y < N; y++)
if (marke.get(c)[x][y] != next.mt[x][y])
break;
if (y < N)
break;
}
if (x == N && y == N)
mark = true;
}
if (!mark) {
next.step++;
next.g++;
next.path.add(next.mt);
int count = 0;
for (int row = 0; row < N; row++) {
for (int cow = 0; cow < N; cow++) {
if (cow != 0 && next.mt[row][cow] != endMT[row][cow]) {
count += Math.abs(row - map.get(next.mt[row][cow])[0])
+ Math.abs(cow - map.get(next.mt[row][cow])[1]);
}
}
}
next.h = count;
int[][] newmt = new int[N][];
for (int r = 0; r < N; r++)
newmt[r] = next.mt[r].clone();
marke.add(newmt);
q.add((node) next.clone());
}
}
}
}
return 0;
}