java实现八数码问题(含GUI)_克里图拉杨马尔斯

结果展示

移动步数为5

移动步数为19

移动步数为31

一.八数码问题描述

1. 基础实验

使用盲目搜索中的宽度优先搜索算法，或者使用启发式搜索中的全局择优搜索算法或A*算法解决八数码问题。要求对任意的八数码问题，给出求解过程和求解结果。
例如：对于如图1的具体八数码问题：

要求通过设计启发函数，编程实现求解过程，如果问题有解，给出数码移动过程，否则，报告问题无解。

2. 拓展实验

（以下三个实验任选 1 个完成）

1. 分别记录宽度优先搜索算法、全局择优搜索算法和A*算法的执行时间并比较 3 者的效率。

2. 在启发式搜索中，分别采用四种不同的启发式函数并比较四者的效率，思考如何进一步改进启发式函数。

3. 试分析在所有可能的初始状态和目标状态之间最长的最小移动步骤数是多少？

二.求解算法设计

1. 设计节点的数据结构

设计Node节点类，用于存储节点状态。
Node类具有记录八数码状态、深度、启发式函数的代价、逆序数和移动方向的功能。为了便于最后确定搜索路径，还记录了父节点在对象数CLOSED中的下标，以便于递归回溯。
具体的数据存储类型如下：

public class Node {
   

	int num[][]=new int [3][3];	//用于存放节点数据
	//约束条件: Xi属于{0，1 ，2，3，4，5，6，7，8}  当 i!=j 时，Xi!=Xj。 
	
	int depth;	//移动步数/深度
	
	int Reverse_order_number; //逆序数
	//具有同奇或同偶排列的八数码才能移动可达，否则不可达
	
	int direction;//父节点移动的方向,1 2 3 4 分别为上 下 左 右
	//子节点移动的方向不可与父节点相反
	
	//int fatherNode=-2;	//	父节点
	
	int worth;	//启发式函数的值
	
	private Node father=null;
	
	public Node(int n[][],int dep,int Reverse_number,int dir,Node fa,int w) {
   
		
		for (int i 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23