题目二：隐式图的搜索问题（A*算法解决八数码）（实验准备）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了题目二：隐式图的搜索问题（A*算法解决八数码）（实验准备），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2219字，纯文字阅读大概需要4分钟。
内容图文
目录
隐式图的搜索问题（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;
}
内容总结
以上是互联网集市为您收集整理的题目二：隐式图的搜索问题（A*算法解决八数码）（实验准备）全部内容，希望文章能够帮你解决题目二：隐式图的搜索问题（A*算法解决八数码）（实验准备）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】