精华内容
下载资源
问答
  • 八数码问题JAVA实现

    2016-07-04 16:42:04
    八数码问题JAVA实现
  • 八数码问题java源码

    2016-01-11 15:38:45
    八数码问题java源码,完美运行,数据结构,人工智能等实验用到啦
  • 状态空间搜索——八数码问题 Java实现-附件资源
  • A*算法解决八数码问题 Java语言实现

    A*算法解决八数码问题 Java语言实现

    参考文章:

    (1)A*算法解决八数码问题 Java语言实现

    (2)https://www.cnblogs.com/beilin/p/5981483.html


    备忘一下。


    展开全文
  • A星算法(寻路问题,八数码问题 java版)
  • 状态空间搜索——八数码问题  实验报告 【注】源码将以附件的形式上传,其中EightPuzzle.java为vo类,EightPuzzleOperator.java为util类,EightPuzzleAlgorithm.java为算法实现类。Main函数在...

    状态空间搜索——八数码问题 

    实验报告

    【注】源码将以附件的形式上传,其中EightPuzzle.java为vo类,EightPuzzleOperator.java为util类,EightPuzzleAlgorithm.java为算法实现类。Main函数在EightPuzzleAlgorithm.java类中。

    源码下载

    一、实习目的和意义

    理解和掌握状态空间搜索的策略。

    二、实习内容

    在一个3*3的九宫中有1~8个数及一个空格随机地摆放在其中的个子里,现在要求实现这个问题;将该九宫格调整为某种有序的形式。调整的规则是,每次只能将空格左上右下移动,试编程实现这一问题的求解。

    三、实习要求

         用你们学过的某种语言编写程序,利用不同的搜索策略进行状态空间搜索(如宽度优先搜索、深度优先搜索、有界深度优先搜索、启发式搜索等)。

    四、实验总结

    【实验测试结果】

    测试中的一组数据:

     

    请输入初始位置(其中输入0代表空白块,例如:2 8 3 1 0 4 7 6 5):

    2 8 3 1 0 4 7 6 5

    请输入目标位置(其中输入0代表空白块,例如:2 8 3 1 4 0 7 6 5):

    2 8 3 1 4 0 7 6 5


    深度优先搜索:

     

    深度优先搜索方法路径!

    2 8 3 1 0 4 7 6 5

    2 8 3 0 1 4 7 6 5

    2 8 3 7 1 4 0 6 5

    2 8 3 7 1 4 6 0 5

    2 8 3 7 1 4 6 5 0

    2 8 3 7 1 0 6 5 4

    2 8 3 7 0 1 6 5 4

    2 8 3 0 7 1 6 5 4

    2 8 3 6 7 1 0 5 4

    2 8 3 6 7 1 5 0 4

    2 8 3 6 7 1 5 4 0

    2 8 3 6 7 0 5 4 1

    2 8 3 6 0 7 5 4 1

    2 8 3 0 6 7 5 4 1

    2 8 3 5 6 7 0 4 1

    2 8 3 5 6 7 4 0 1

    2 8 3 5 6 7 4 1 0

    2 8 3 5 6 0 4 1 7

    2 8 3 5 0 6 4 1 7

    2 8 3 0 5 6 4 1 7

    2 8 3 4 5 6 0 1 7

    2 8 3 4 5 6 1 0 7

    2 8 3 4 5 6 1 7 0

    2 8 3 4 5 0 1 7 6

    2 8 3 4 0 5 1 7 6

    2 8 3 0 4 5 1 7 6

    2 8 3 1 4 5 0 7 6

    2 8 3 1 4 5 7 0 6

    2 8 3 1 4 5 7 6 0

    2 8 3 1 4 0 7 6 5

    终于找到了,⊙﹏⊙b汗

    有界深度优先搜索:

     

    有界深度优先搜索方法路径!

    2 8 3 1 0 5 7 4 6

    0 8 3 2 4 5 1 7 6

    2 8 3 4 7 5 1 0 6

    2 0 3 4 8 5 1 7 6

    2 8 0 4 5 3 1 7 6

    2 8 3 4 0 6 1 5 7

    0 8 3 2 5 6 4 1 7

    2 8 3 5 1 6 4 0 7

    2 0 3 5 8 6 4 1 7

    2 8 0 5 6 3 4 1 7

    2 8 3 5 0 7 4 6 1

    0 8 3 2 6 7 5 4 1

    2 8 3 6 4 7 5 0 1

    2 0 3 6 8 7 5 4 1

    2 8 0 6 7 3 5 4 1

    2 8 3 6 0 1 5 7 4

    0 8 3 2 7 1 6 5 4

    2 8 3 7 5 1 6 0 4

    2 0 3 7 8 1 6 5 4

    2 8 0 7 1 3 6 5 4

    2 8 3 7 0 4 6 1 5

    0 8 3 2 1 4 7 6 5

    2 8 3 0 1 4 7 6 5

    2 8 3 7 1 4 0 6 5

    2 8 3 1 0 4 7 6 5

    0 8 3 2 1 4 7 6 5

    8 0 3 2 1 4 7 6 5

    0 8 3 2 1 4 7 6 5

    8 1 3 2 0 4 7 6 5

    8 3 0 2 1 4 7 6 5

    2 8 3 1 6 4 7 0 5

    2 8 3 1 6 4 0 7 5

    2 8 3 1 6 4 7 0 5

    2 8 3 1 6 4 0 7 5

    2 8 3 1 6 4 7 5 0

    2 8 3 0 6 4 1 7 5

    2 8 3 1 6 4 0 7 5

    2 8 3 6 0 4 1 7 5

    0 8 3 2 6 4 1 7 5

    2 8 3 1 6 4 7 5 0

    2 8 3 1 6 4 7 0 5

    2 8 3 1 6 4 0 7 5

    2 8 3 1 6 0 7 5 4

    2 8 3 1 0 6 7 5 4

    2 8 0 1 6 3 7 5 4

    2 8 3 1 0 4 7 6 5

    2 8 3 1 6 4 7 0 5

    2 8 3 1 6 4 0 7 5

    2 8 3 1 4 0 7 6 5

    终于找到了,⊙﹏⊙b汗

    广度优先搜索:

     

    广度优先搜索方法路径!

    2 8 3 1 0 4 7 6 5

    2 0 3 1 8 4 7 6 5

    2 8 3 1 4 0 7 6 5

    终于找到了,⊙﹏⊙b汗


     

    由于上面的运行结果截图不能一次截图完毕,所以将其中的运行过程复制了下来,上面的代码均为Java源码。下面分别对上面的三种算法使用自然语言描述。

    【实验算法描述】

    八数码问题,是对给定的一个初始位置,然后经过多次移动找到目标位置,并列举出其中的移动过程,最后可以找到既是可以成功,否则以失败告终。是一种过程中无人为参与的一中求解方法。

    深度优先搜索:

    深度优先搜索算法是按照一条路径一直往下深度延伸其子节点的算法,直到找到答案为止。也可能一直到达一个很深的深度之后还是没有找到问题的答案,这样就有可能出现栈溢出或者内存超界的情况(本实验中数字组合相对较少,不会造成内存超限的情况)。在深度优先搜索的求解过程中使用栈来存储还未搜索的节点,已经搜索过的节点使用一个链表来存储(避免重复的搜索,属于优化过程)。如果已经在链表中那么就不在放到栈中,因为之前已经搜索过了,不需要重复搜索。当然在深度优先搜索的过程中,不需要记录其深度,因为不会用深度来限制搜索。所以判断是不是已经包含当然搜索的节点在链表中,是用其中的数值数组是不是完全相同来判断的。

    有界深度优先搜索:

    有界深度优先搜索是在深度优先搜索的基础上进行的另一种对其深度进行限制的一种搜索方法。当然其使用的数据结构也是和深度优先搜索一样的,其中的不同之处在于,在有界深度优先搜索的基础上判断是不是相等时会有一个深度的同时相等的判断,即只有当其中的数组数值和搜索深度同时相等时才认为是相等的。同时也会在深度达到5以后搜索不会继续发展更深的子节点,而是开始搜索其兄弟节点等,然后继续。如果找不到就返回“非常遗憾,没有搜索到你需要的目标!%>_<%”。

    广度(宽度)优先搜索:

    广度优先搜索,也被称作宽度优先搜索,是首先在兄弟节点之间进行搜索和遍历的方法,然后知道其全部的兄弟节点都已经遍历完,才开始继续往下发展其子节点,所以在这个过程中使用队列(Queue接口的实现类LinkedList)来存储其中还没有遍历的但是已经发展了的节点,同时使用链表来存储已经搜索过的子节点,然后基本上是和深度优先搜索算法类似。如果找不到就返回“非常遗憾,没有搜索到你需要的目标!%>_<%”。

    【总结】

    本次实验利用图的搜素算法——深度优先搜索、广度优先搜索、有界深度优先搜索三种算法完成八数码问题的求解,利用Java程序设计语言编程,过程中遇到了诸多问题,以前太注重算法这一块的练习,实验中,每一块都是自己努力完成,也解决了遇到的问题,所以还是很有收获的。

    package cn.edu.nwsuaf.qhs.artificialintelligence.eightpuzzle;
    
    import java.util.Arrays;
    
    public class EightPuzzle implements Cloneable{
    	
    	/*利用一个二维的数组来存储数据*/
    	public int[][] data;
    	private int blankPos_x,blankPos_y;
    	private int depth;
    	
    	//无参构造函数
    	public EightPuzzle(){
    		data = new int[3][3];
    	}
    	//传递一个数组,进行初始化的构造函数
    	public EightPuzzle(int [][] data){
    		this.data = data;
    	}
    	//判断是不是和目标位置相同
    	/*int[][] data1 = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
    	int[][] data2 = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
    	System.out.println("Equals--->"+Arrays.equals(data1, data2));  false
    	System.out.println("deepEquals--->"+Arrays.deepEquals(data1, data2));  true*/
    	public boolean isEquals(EightPuzzle ep){
    		return Arrays.deepEquals(this.data, ep.data);		
    	}
    	
    	
    	@Override
    	public String toString(){
    		StringBuffer sb = new StringBuffer(20);
    		for (int i = 0; i < 3; i++){
    			for (int j = 0; j < 3; j++){
    				sb.append(this.data[i][j]);
    				sb.append(" ");
    			}
    		}
    		return sb.toString();
    	}
    	
    	// 获取空格的位置
    	public void getPostion() {
    		for (int i = 0; i < 3; i++) {
    			for (int j = 0; j < 3; j++) {
    				if (this.data[i][j] == 0) {
    					this.setBlankPos_x(i);
    					this.setBlankPos_y(j);
    				}
    			}
    		}
    	}
    	
    	public void setBlankPos_x(int blankPos_x) {
    		this.blankPos_x = blankPos_x;
    	}
    	
    	public void setBlankPos_y(int blankPos_y) {
    		this.blankPos_y = blankPos_y;
    	}
    	
    	public int getBlankPos_x() {
    		return blankPos_x;
    	}
    	
    	public int getBlankPos_y() {
    		return blankPos_y;
    	}
    	
    	public int getDepth() {
    		return depth;
    	}
    	
    	public void setDepth(int depth) {
    		this.depth = depth;
    	}
    	
    	public void print(){
    		System.out.println(this.toString());
    	}
    	
    	//浅拷贝
    	@Override
    	protected EightPuzzle clone() throws CloneNotSupportedException {
    		// TODO Auto-generated method stub
    		return new EightPuzzle(Arrays.copyOf(this.data, this.data.length));
    	}
    	//深拷贝
    	public EightPuzzle depthClone(){
    		EightPuzzle tmp_ep = new EightPuzzle();
    		for (int i = 0 ; i < 3; i++)
    			for (int j = 0 ; j < 3; j++)
    				tmp_ep.data[i][j] = this.data[i][j];
    		tmp_ep.depth = this.depth;
    		return tmp_ep;
    	}
    	
    	public static void main(String[] args) {
    		
    	}
    	@Override
    	public boolean equals(Object obj) {
    		// TODO Auto-generated method stub
    		return this.isEquals((EightPuzzle)obj);
    		//&&(this.getDepth() == ((EightPuzzle)obj).getDepth()
    	}
    	
    }
    

    package cn.edu.nwsuaf.qhs.artificialintelligence.eightpuzzle;
    
    public class EightPuzzleOperator {
    
    	//判断是不是可以继续移动
    	public static boolean canMove(int x, int y, int direction) {
    		if ((direction == 1 && x == 0) || (direction == -1 && x == 2)
    				|| (direction == 2 && y == 2) || (direction == -2 && y == 0)) {
    			return false;
    		}
    		return true;
    	}
    
    	//根据给出的参数,进行空格位置的移动
    	//其中1表示向上,2表示向右,-1表示向下,-2表示向左
    	public static EightPuzzle movePosition(EightPuzzle ep, int args) {
    		
    		EightPuzzle arg_ep = null;
    
    		arg_ep = ep.depthClone();
    		arg_ep.getPostion();
    		int blankPos_x = arg_ep.getBlankPos_x(), blankPos_y = arg_ep
    				.getBlankPos_y();
    
    		//指令为向上移动
    		if (args == 1) {
    			int temp = arg_ep.data[blankPos_x][blankPos_y];
    			arg_ep.data[blankPos_x][blankPos_y] = arg_ep.data[blankPos_x - 1][blankPos_y];
    			arg_ep.data[blankPos_x - 1][blankPos_y] = temp;
    			//表示移动成功
    		}
    		//指令为向下移动
    		else if (args == -1) {
    			int temp = arg_ep.data[blankPos_x][blankPos_y];
    			arg_ep.data[blankPos_x][blankPos_y] = arg_ep.data[blankPos_x + 1][blankPos_y];
    			arg_ep.data[blankPos_x + 1][blankPos_y] = temp;
    			//表示移动成功
    		}
    		//指令为向右移动
    		else if (args == 2) {
    			int temp = arg_ep.data[blankPos_x][blankPos_y];
    			arg_ep.data[blankPos_x][blankPos_y] = arg_ep.data[blankPos_x][blankPos_y + 1];
    			arg_ep.data[blankPos_x][blankPos_y + 1] = temp;
    			//表示移动成功
    
    		}
    		//指令为向左移动
    		else if (args == -2) {
    			int temp = arg_ep.data[blankPos_x][blankPos_y];
    			arg_ep.data[blankPos_x][blankPos_y] = arg_ep.data[blankPos_x][blankPos_y - 1];
    			arg_ep.data[blankPos_x][blankPos_y - 1] = temp;
    			//表示移动成功
    		}
    		//指令输入错误
    		else {
    			return null;
    		}
    		return arg_ep;
    	}
    }
    

    package cn.edu.nwsuaf.qhs.artificialintelligence.eightpuzzle;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class EightPuzzleAlgorithm {
    
    	private int[][] array = new int[3][3];
    	private int[][] target = new int[3][3];
    	private EightPuzzle ep, target_ep;
    	private int depth = 0;
    	private Stack<EightPuzzle> ep_stack = new Stack<EightPuzzle>();
    	private LinkedList<EightPuzzle> searched_list = new LinkedList<EightPuzzle>();
    	private Queue<EightPuzzle> ep_queue = new LinkedList<EightPuzzle>();
    
    	public EightPuzzleAlgorithm() {
    
    		// 初始化栈和队列,以及列表
    		ep_stack.clear();
    		searched_list.clear();
    		ep_queue.clear();
    
    		Scanner scanner = new Scanner(System.in);
    		// 输入初始位置
    		System.out.println("请输入初始位置(其中输入0代表空白块,例如:2 8 3 1 0 4 7 6 5):");
    		for (int i = 0; i < 3; i++) {
    			for (int j = 0; j < 3; j++) {
    				array[i][j] = scanner.nextInt();
    			}
    		}
    		// 输入目标位置
    		System.out.println("请输入目标位置(其中输入0代表空白块,例如:2 8 3 1 4 0 7 6 5):");
    		for (int i = 0; i < 3; i++) {
    			for (int j = 0; j < 3; j++) {
    				target[i][j] = scanner.nextInt();
    			}
    		}
    
    		ep = new EightPuzzle(array);
    		ep.setDepth(depth);
    		// 设置栈底元素
    		ep_stack.push(ep);
    		target_ep = new EightPuzzle(target);
    		scanner.close();
    		// 设置队首元素
    		ep_queue.offer(ep);
    	}
    
    	// 深度优先搜索
    	// 栈的方式实现
    	public void depthFirstSearch() {
    		System.out.println("深度优先搜索方法路径!");
    		if (!searched_list.isEmpty())
    			searched_list.clear();
    		
    		while (!ep_stack.isEmpty()) {
    			EightPuzzle move_ep = ep_stack.pop();
    			depth = move_ep.getDepth();
    			move_ep.getPostion();
    			int x = move_ep.getBlankPos_x(), y = move_ep.getBlankPos_y();
    			move_ep.print();
    			searched_list.add(move_ep);
    
    			if (move_ep.isEquals(target_ep)) {
    				System.out.println("终于找到了,⊙﹏⊙b汗");
    				return;
    			}
    			depth++;
    			EightPuzzle temp = null;
    
    			temp = move_ep.depthClone();
    
    			if (EightPuzzleOperator.canMove(x, y, 1)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, 1);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_stack.push(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, 2)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, 2);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_stack.push(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, -1)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, -1);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_stack.push(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, -2)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, -2);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_stack.push(temp);
    				}
    			}
    		}
    		System.out.println("非常遗憾,没有搜索到你需要的目标!%>_<%");
    	}
    
    	// 深度优先搜索(有界,最大深度为5)
    	// 栈的方式实现搜索
    	public void boundedDepthFirstSearch() {
    		System.out.println("有界深度优先搜索方法路径!");
    		if (!searched_list.isEmpty())
    			searched_list.clear();
    		while (!ep_stack.isEmpty()) {
    			EightPuzzle move_ep = ep_stack.pop();
    			depth = move_ep.getDepth();
    			move_ep.getPostion();
    			int x = move_ep.getBlankPos_x(), y = move_ep.getBlankPos_y();
    			move_ep.print();
    			searched_list.add(move_ep);
    
    			if (move_ep.isEquals(target_ep)) {
    				System.out.println("终于找到了,⊙﹏⊙b汗");
    				return;
    			}
    			if (depth < 4) {
    				depth++;
    				EightPuzzle temp = null;
    
    				temp = move_ep.depthClone();
    
    				if (EightPuzzleOperator.canMove(x, y, 1)) {
    					temp = EightPuzzleOperator.movePosition(move_ep, 1);
    					temp.setDepth(depth);
    					if (!searched_list.contains(temp)||(searched_list.contains(temp)&&
    							searched_list.get(searched_list.indexOf(temp)).getDepth()!=temp.getDepth())) {
    						ep_stack.push(temp);
    					}
    				}
    				if (EightPuzzleOperator.canMove(x, y, 2)) {
    					temp = EightPuzzleOperator.movePosition(move_ep, 2);
    					temp.setDepth(depth);
    					if (!searched_list.contains(temp)||(searched_list.contains(temp)&&
    							searched_list.get(searched_list.indexOf(temp)).getDepth()!=temp.getDepth())) {
    						ep_stack.push(temp);
    					}
    				}
    				if (EightPuzzleOperator.canMove(x, y, -1)) {
    					temp = EightPuzzleOperator.movePosition(move_ep, -1);
    					temp.setDepth(depth);
    					if (!searched_list.contains(temp)||(searched_list.contains(temp)&&
    							searched_list.get(searched_list.indexOf(temp)).getDepth()!=temp.getDepth())) {
    						ep_stack.push(temp);
    					}
    				}
    				if (EightPuzzleOperator.canMove(x, y, -2)) {
    					temp = EightPuzzleOperator.movePosition(move_ep, -2);
    					temp.setDepth(depth);
    					if (!searched_list.contains(temp)||(searched_list.contains(temp)&&
    							searched_list.get(searched_list.indexOf(temp)).getDepth()!=temp.getDepth())) {
    						ep_stack.push(temp);
    					}
    				}
    			}
    		}
    		System.out.println("非常遗憾,没有搜索到你需要的目标!%>_<%");
    	}
    
    	// 宽度(广度)优先搜索实现
    	public void breadthFirstSearch() {
    		if (!searched_list.isEmpty())
    			searched_list.clear();
    		System.out.println("广度优先搜索方法路径!");
    		while (!ep_queue.isEmpty()) {
    			EightPuzzle move_ep = ep_queue.poll();
    			depth = move_ep.getDepth();
    			move_ep.getPostion();
    			int x = move_ep.getBlankPos_x(), y = move_ep.getBlankPos_y();
    			move_ep.print();
    			searched_list.add(move_ep);
    
    			if (move_ep.isEquals(target_ep)) {
    				System.out.println("终于找到了,⊙﹏⊙b汗");
    				return;
    			}
    			depth++;
    			EightPuzzle temp = null;
    
    			temp = move_ep.depthClone();
    
    			if (EightPuzzleOperator.canMove(x, y, 1)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, 1);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_queue.offer(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, 2)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, 2);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_queue.offer(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, -1)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, -1);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_queue.offer(temp);
    				}
    			}
    			if (EightPuzzleOperator.canMove(x, y, -2)) {
    				temp = EightPuzzleOperator.movePosition(move_ep, -2);
    				temp.setDepth(depth);
    				if (!searched_list.contains(temp)) {
    					ep_queue.offer(temp);
    				}
    			}
    		}
    		System.out.println("非常遗憾,没有搜索到你需要的目标!%>_<%");
    	}
    
    	/*public void search() {
    		// this.getPostion();
    		// this.depthFirstSearch(blankPos_x, blankPos_y, 1);
    		this.depthFirstSearch();
    		this.boundedDepthFirstSearch();
    		this.breadthFirstSearch();
    	}*/
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		EightPuzzleAlgorithm epa = new EightPuzzleAlgorithm();
    		epa.depthFirstSearch();
    		epa.boundedDepthFirstSearch();
    		epa.breadthFirstSearch();
    	}
    	/*
    	 * 测试用例 【1】2 8 3 1 0 4 7 6 5 2 8 3 1 4 0 7 6 5 【2】2 8 3 1 0 4 7 6 5
    	 * 
    	 */
    }



    展开全文
  • 用A*算法求解八数码问题 java实现

    千次阅读 2020-01-27 20:08:00
    用A*算法求解八数码问题1.估价函数2.搜索过程3.流程图4.八数码的估计函数设计5.编码实现6.结果 1.估价函数 首先定义估价函数。计算一个节点的估价函数,可以分成两个部分:g(n)已经付出的代价(起始节点到当前节点)...

    1.估价函数

    首先定义估价函数。计算一个节点的估价函数,可以分成两个部分:g(n)已经付出的代价(起始节点到当前节点)和h(n)将要付出的代价(当前节点到目标节点)。节点n的估价函数f(n)定义为f(n)=g(n)+h(n)。在A搜索算法中使用的就是估价函数f(n)=g(n)+h(n)。
    接下来定义最优估价函数f*(n)=g*(n)+h*(n),其中g*(n)为起点到n状态的最短路径代价值,h*(n)是n状态到目的状态的最短路径的代价值。这样f*(n)就是起点出发通过n状态而到达目的状态的最佳路径的总代价值。但在绝大部分实际问题中并不存在f*(n)这样的先验函数,但可以将f(n)作为f*(n)的一个近似估计函数。在A及A搜索算法中,g(n)作为g(n)的近似估价。g(n)与g*(n)可能并不相等,但在搜索过程中有g(n)>=g*(n),当搜索过程中已发现了到达n状态的最佳状态时,它们才相等。同样,可以用h(n)代替h*(n)作为n状态到目的状态的最小代价估计值。虽然在绝大数情况下无法计算h*(n),但是要判别某一h(n)是否大于h*(n)还是可能的。所以如果A搜索算法所使用的估价函数f(x)所能达到的f(n)中的h(n)<=h*(n)时它就为A*搜索算法

    2.搜索过程

    启发式图搜索算法使用两张表记录状态信息:在open表中保留所有已生产而未扩展的状态。在closed表中记录已扩展过的状态。算法中是根据某些启发信息来排列open表的。它既不同于宽度优先使用的队列,也不同于深度优先所使用的堆栈,而是按一个状态的启发估价函数值的大小排列的一个表。进入open表的状态不是简单地排在队尾或队首,而是根据其估值的大小插入到表中合适的位置,每次从表中优先取出启发估价函数最小的状态加以扩展。
    A*算法的搜索过程是基于估价函数的一种加权启发式图搜索算法,搜索过程如下:
    1.把初始结点放入到open表
    2.若open表为空,则搜索失败,退出
    3.移出open表中第一个结点N放入closed表中,也就是估价函数最小的节点,并顺序编号n
    4.若目标结点的状态等于结点N的状态,则搜索成功,结束
    5.若N不可扩展则转步骤2
    6.扩展节点N,生成一组节点N的子节点,对这组子节点做如下操作:
    (1)考察是否有已在open表或closed表中存在的结点。若有则再考察其中有无N的先辈结点,若有则删除之,对于其余节点也删除,但由于它们又被第二次生成,因此需要考虑是否修改已经存在于open表或closed表中的这些结点及其后裔的返回指针和f(x)的值。修改原则是:选f(x)值小的路径走。
    (2)为其余子节点配上指向N的返回指针后放入open表中,并对open表按f(x)值以升序排序,转向步骤2

    3.流程图

    在这里插入图片描述

    4.八数码的估计函数设计

    估计函数是由两部分构成的,节点深度d(n)其实就是当前已经走的步数,不用额外设计函数;启发函数h(n)是比较重要的一个部分,启发函数的设计直接影响了估计函数的效率,有几种定义方法:
    (1)当前节点与目标节点差异的度量 => 当前结点与目标节点相比,位置不符的数字个数
    (2)当前节点与目标节点距离的度量 => 当前结点与目标节点格局位置不符的数字移动到目标节点中对应位置的最短距离之和
    估计函数一:
    八数码的g(n)为已经搜索的步数,八数码的h(n)为当前结点与目标节点差异的数量
    估计函数二:
    当前结点与目标节点格局位置不符的数字移动到目标节点中对应位置的最短距离之和

    5.编码实现

    package Astatr;
    
    import java.util.*;
    
    
    public class Astar {
        private int N=3;
        Scanner input=new Scanner(System.in);
        int Map[][]=new int[N][N];
        int target[][]=new int[N][N];
        List<Node> openList=new ArrayList<>();    //A*算法open列表
        List<Node> closeList=new ArrayList<>();   //A*算法closed列表
    
        List<Node> queue=new ArrayList<>();   //bfs队列
    
        HashMap<Integer,int []> targetmap=new HashMap<>();  //估价函数二所用的映射功能
        List<Node>  nodeList=new ArrayList<>();  //节点列表用于存储所有扩展节点
    
        Node Start;
        Node Target;
        Comparator<Node> comparator=new Comparator<Node>() {    //比较函数,根据f(n)的值可以将openlist或closedlist从小到大排列
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.getF()>o2.getF())
                    return 1;
                else if(o1.getF()==o2.getF())
                    return 0;
                else
                    return -1;
            }
        };
    
        public Astar(){
            if(init()) {
                A_algorithm();    //可以更改为bfs()测试bfs的性能
            }else{
                System.out.println("无解");
            }
        }
        boolean init(){         //初始化函数,用于输入初始八数码和目标八数码
            System.out.println("请输入八数码的初始状态:");
           for(int i=0;i<N;i++){
               for(int j=0;j<N;j++){
                   Map[i][j]=input.nextInt();
               }
           }
           Start=new Node();
           Start.setState(Map);
            System.out.println("请输入八数码的目标状态:");
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    target[i][j]=input.nextInt();
                    int index[]={i,j};
                    targetmap.put(target[i][j],index);
                }
            }
           Target=new Node();
            Target.setState(target);
            if(isSolve(Start,Target)){
                return true;
            }else{
                return false;
            }
        }
        public boolean isSolve(Node start,Node target){     //判断是否有解
        		/*
        		对于八数码问题,首先要判断当前的状态能不能到达目的状态,这里需要用到奇排列和偶排列的概念。八数码虽然是个二维数组,但也可以展开看成是一个一维序列。奇排列只能转换成奇排列,偶排列只能转换成偶排列。判断奇偶排列的方法就是:对于每个数,求出排在它之前的比它大的数的个数,然后将这些个数加起来,得到的数是奇数就是奇排列,是偶数就是偶排列,若起始状态和目标状态一个是奇排列一个数偶排列,那么肯定到达不了目标状态。
        		*/
            int startNum[]=start.getSequence();
            int endNum[] =target.getSequence();
            int st = 0;
            int et = 0;
            for (int i = N * N - 2; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {
                    if (startNum[i] > startNum[j])
                        st++;
                    if (endNum[i] > endNum[j])
                        et++;
                }
            }
            if (st % 2 == et % 2)
                return true;
            return false;
        }
    
        int IndexInList(List<Node> list,Node node){    //判断某一状态是否在列表中 
            for (int index = 0; index < list.size(); index++) {
                int i = 0,j=0;
                for (i = 0; i <N; i++) {
                    for(j=0;j<N;j++) {
                        if ((list.get(index).getState()[i][j]) != node.getState()[i][j])
                            break;
                    }
                    if (j < N)
                        break;
                }
                if (i==N&&j==N) {
                    return index;
                }
            }
            return -1;
        }
    
        public boolean isCanMove(int x,int y){    //是否可以移动0
            if(x<0||x>=3||y<0||y>=3){
                return false;
            }
            return true;
        }
        Node getNext(Node now,int direction){   //移动函数,用于获得下一状态
            int dx[]=new int[]{0,0,-1,1};
            int dy[]=new int[]{-1,1,0,0};
            Node next=new Node();
            int temp[][]=new int[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++)
                    temp[i][j]=now.getState()[i][j];
            }
            int zeroIndex[]=now.getZeroIndex();
            int x0=zeroIndex[0];
            int y0=zeroIndex[1];
            int nextZeroIndex=0;
            int nextx,nexty;
            nextx=x0+dx[direction];
            nexty=y0+dy[direction];
            if(isCanMove(nextx,nexty)){
                temp[x0][y0]=now.getState()[nextx][nexty];
                temp[nextx][nexty]=0;        
               List<Node> path=new ArrayList<>();
                path.addAll(now.path);
                next.setState(temp);
                next.setPath(path);
                return next;
            }else{
                return null;
            }
        }
    
        void A_algorithm(){       //A*算法主体
        Start.setUp2();    //设置估价函数,可以更改为其他估价函数
        Start.path.add(Start);
        openList.add(Start);
        nodeList.add(Start);
        while(!openList.isEmpty()){
            openList.sort(comparator);
            Node best=openList.get(0);
            openList.remove(0);
            closeList.add(best);
            if(best.isTarget(Target)){        //判断是否为目标状态
                System.out.println("-------打印路径------");
                for(int i=0;i<best.path.size();i++){
                    System.out.println("第"+i+"次移动");
                    best.path.get(i).print();
                }
                System.out.println("共扩展了"+nodeList.size()+"个节点");
                return;
            }
            for(int i=0;i<4;i++){
                Node next=getNext(best,i);
                if(next!=null){       //是否可以移动到下一个状态
                    if(IndexInList(closeList,next)==-1){     //如果不在cloesd列表中
                        int index=IndexInList(openList,next);
                        if(index>=0){       //如果在open列表中
                            if(next.getG()<openList.get(index).getG()){    //比较和已在open列表中的深度比较
                                openList.remove(index);     //如果next更小,则将open中已存在的更换为next
                                next.setParent(best);
                                next.setUp2(Target,targetmap);   //设置估价函数,可以更改为其他估价函数
                                next.path.add(next);
                                openList.add(next);
                                nodeList.add(next);
                            }
                        }else{    //如果不在open列表中,则加入到open列表中
                            next.setParent(best);
                            next.setUp2(Target,targetmap);   //设置估价函数,可以更改为其他估价函数
                            next.path.add(next);
                            openList.add(next);
                            nodeList.add(next);
                        }
                    }
                }
            }
        }
     }
    
        void bfs(){    //bfs算法
            Start.setUp3();
            Start.path.add(Start);
            queue.add(Start);
            while(!queue.isEmpty()){
                Node best=queue.get(0);
                queue.remove(0);
                if(best.isTarget(Target)){        //判断是否为目标状态
                    System.out.println("-------打印路径------");
                    for(int i=0;i<best.path.size();i++){
                        System.out.println("第"+i+"次移动");
                        best.path.get(i).print();
                    }
                    System.out.println("共扩展了"+nodeList.size()+"个节点");
                    return;
                }
                for(int i=0;i<4;i++){
                    Node next=getNext(best,i);
                    if(next!=null){       //是否可以移动到下一个状态
                        next.setParent(best);
                        next.setUp3();
                        next.path.add(next);
                        queue.add(next);
                        queue.add(next);
                    }
                }
            }
        }
    
         void printPath(Node end){    //打印路径
              while(end!=null){
                  path.add(end);
                  end=end.getParent();
              }
              for(int i=0;i<path.size();i++){
                  System.out.println("---------第"+(i+1)+"次移动--------");
                   path.get(i).print();
                  System.out.println("-------------------------");
              }
             System.out.println("移动次数:"+path.size());
         }
        public static void main(String[] args) {
            Astar astar=new Astar();
        }
    }
    
    
    
    
    
    class Node {       //用于定义状态的类
        private int N=3;
        int state[][]=new int[3][3];
        private int f;    //估计函数
        private int g;    //当前深度
        private int h;     //目标的估计
        private Node parent;  //存储当前结点的上一个状态
        List<Node> path=new ArrayList<>();   //存储路径
        public Node(){
    
        }
    
        public void setUp(Node target) {   //估价函数一
            int num=0;
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++)
                if(state[i][j]!=target.getState()[i][j]){
                    num++;
                }
            }
            this.h = num;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
        public void setUp2(Node target,Map<Integer,int[]> map){   //估价函数二
            int num = 0;
            for (int row = 0; row < N; row++) {
                for (int cow = 0; cow < N; cow++) {
                    if (cow != 0 && state[row][cow] != target.getState()[row][cow]){
                        num += Math.abs(row - map.get(state[row][cow])[0]) + Math.abs(cow - map.get(state[row][cow])[1]);
                    }
                }
            }
            this.h = num;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
        public void setUp3(){            //bfs的估价函数
            this.h = 0;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
    
        public int[][] getState() {
            return state;
        }
    
        public void setState(int[][] state) {
            this.state = state;
        }
    
        public int getF() {
            return f;
        }
    
        public void setF(int f) {
            this.f = f;
        }
    
        public int getG() {
            return g;
        }
    
        public void setG(int g) {
            this.g = g;
        }
    
        public Node getParent() {
            return parent;
        }
    
        public void setParent(Node parent) {
            this.parent = parent;
        }
    
        public List<Node> getPath() {
            return path;
        }
    
        public void setPath(List<Node> path) {
            this.path = path;
        }
    
        public boolean isTarget(Node target){
            int i = 0,j=0;
            for (i = 0; i <N; i++) {
                for(j=0;j<N;j++) {
                    if (state[i][j]!= target.getState()[i][j])
                        return false;
                }
            }
            return true;
        }
    
        public int[] getZeroIndex(){     //获得0的位置
            int x0 = 0, y0 = 0;
            for (x0 = 0; x0 < N; x0++) {
                boolean flag = false;
                for (y0 = 0; y0 < N; y0++) {
                    if (state[x0][y0] == 0) {
                        flag = true;
                        break;
                    }
                }
                if (flag)
                    break;
            }
            return new int[]{x0, y0};
        }
    
    
       public void print(){    //打印函数
            for(int i=0;i<3;i++){
               for(int j=0;j<3;j++){
                   System.out.print(state[i][j]+" ");
               }
                System.out.println();
            }
       }
    	
    	public int[] getSequence(){     //获取一维序列
        	int num[]=new int[N*N];
        	int count=0;
        	for(int i=0;i<N;i++)
        		for(int j=0;j<N;j++){
        			if(state[i][j]!=0){
    					num[count++]=state[i][j];
    				}
        		}
        	return num;
        }
    }
    
    
    
    
    public class Test(){
    	 public static void main(String[] args) {
            Astar astar=new Astar();
        }
    }
    

    6.结果

    使用0代替空格的位置,并输出打印路径和移动次数
    比较两种不同的估计函数的结果值
    设定初始状态为
    2 8 3
    1 6 4
    7 0 5
    目标状态为
    1 2 3
    8 0 4
    7 6 5

    不同估价函数的比较

    搜索方法 扩展节点数
    A*算法的估价函数一 14
    A*算法的估价函数二 12
    广度优先搜索(BFS) 684

    对比来看不同的估价函数是能够影响搜索效率的,bfs的效率相比于A*算法是低了很多的。

    展开全文
  • 用于实现java八数码问题,包括全局择优算法,A*算法,宽度优先算法,及四种启发式函数的实现
  • JAVA_八数码问题实现

    2013-06-27 12:31:28
    JAVA_八数码问题实现
  • 基于java八数码问题

    2010-08-24 22:02:09
    采用java,用深度优先搜索实现八数码问题
  • 八数码问题,是人工智能的实验,打包发布为JAR文件
  • java八数码问题A*算法,
  • 这是八数码问题java程序实现,希望对大家的编程学习有一定的帮助。
  • 八数码算法java实现

    2011-11-12 21:18:06
    基于java实现的八数码问题。能够动态的输入数字,以启发式函数实现的A算法。
  • 利用Java实现人工智能的八数码问题的宽度优先算法,实现对该问题的解决
  • 对于上次所传八数码问题中存在的严重错误表示道歉,现在上传修正版本,仍有不足之处,望高手多多指正。
  • Java语言应用人工智能里的A*算法解决八数码问题带有图形界面
  • Java_Eight Puzzle_八数码

    2012-05-31 19:35:53
    人工智能:基于A星算法的八数码问题Java程序源代码
  • Java 八数码问题求解

    2021-05-15 15:27:52
    import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; //以0为移动对象 Hn是错位个数/距离目标位置的距离 public class EightPuzzle implements Comparable { public static void ...
    
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    //以0为移动对象 Hn是错位个数/距离目标位置的距离
    public class EightPuzzle implements Comparable {
        public static void main(String args[]) {
            ArrayList<EightPuzzle> open = new ArrayList<EightPuzzle>();  //定义open表
            ArrayList<EightPuzzle> close = new ArrayList<EightPuzzle>();
            EightPuzzle start = new EightPuzzle();
            EightPuzzle target = new EightPuzzle();
            int startnum[] = {2, 1, 6, 4, 0, 8, 7, 5, 3};
            int targetnum[] = {1, 2, 3, 8, 0, 4, 7, 6, 5};
            start.setNum(startnum);
            target.setNum(targetnum);
            long startTime = System.currentTimeMillis();   //获取开始时间
            if (start.isSolvable(target)) {        //判断有解之后 起始状态逆序数的奇偶性和目标状态的奇偶性是一样的则有解
                start.init(target);       //初始化初始状态 Fn Gn Hn
                open.add(start);
                while (open.isEmpty() == false) {   //open表为空则失败
                    Collections.sort(open);            //按照Fn的值排序--Fn越小越先拓展
                    EightPuzzle best = open.get(0);    //从open表中取出最小估值的状态并移除open表
                    open.remove(0);
                    close.add(best);
                    if (best.isTarget(target)) {   //如果当前状态为目标状态
                        best.printRoute();  //输出
                        long end = System.currentTimeMillis(); //获取结束时间
                        System.out.println("程序运行时间: " + (end - startTime) + "ms");
                        System.exit(0);
                    }
                    int move;
                    //由best状态进行扩展 并加入到open表中
                    if (best.isMoveUp()) {//能向上移动
                        move = 0;
                        EightPuzzle up = best.moveUp(move);  //返回移动后的状态
                        up.operation(open, close, best, target);//0的位置上移之后状态不在close和open中  设定best为其父状态
                    }
    
                    if (best.isMoveDown()) {
                        move = 1;
                        EightPuzzle up = best.moveUp(move);
                        up.operation(open, close, best, target);//0的位置下移之后状态不在close和open中  设定best为其父状态
                    }
    
                    if (best.isMoveLeft()) {
                        move = 2;
                        EightPuzzle up = best.moveUp(move);
                        up.operation(open, close, best, target);
                    }
    
                    if (best.isMoveRight()) {
                        move = 3;
                        EightPuzzle up = best.moveUp(move);
                        up.operation(open, close, best, target);
                    }
    
                }
            } else
                System.out.println("没有解,请重新输入。");
        }
        private int[] num = new int[9];
        private int Gn;                    //当前的深度即走到当前状态的步骤--G
        private int Fn;                //从起始状态到目标的最小估计值--Fn
        private int Hn;            //到目标的最小估计--Hn
        private EightPuzzle parent;            //当前状态的父状态
    
        public int[] getNum() {
            return num;
        }
    
        public void setNum(int[] num) {
            this.num = num;
        }
    
        public int getGn() {
            return Gn;
        }
    
        public void setGn(int gn) {
            this.Gn = gn;
        }
    
        public int getFn() {
            return Fn;
        }
    
        public void setFn(int fn) {
            this.Fn = fn;
        }
    
        public int getHn() {
            return Hn;
        }
    
        public void setHn(int hn) {
            this.Hn = hn;
        }
    
        public EightPuzzle getParent() {
            return parent;
        }
    
        public void setParent(EightPuzzle parent) {
            this.parent = parent;
        }
    
        //         判断当前状态是否为目标状态
        public boolean isTarget(EightPuzzle target) {
            return Arrays.equals(getNum(), target.getNum());
        }
    
        /*
         * 初始化状态信息
         */
        public void init(EightPuzzle target) {
            int temp = 0;
            //两个不同的估价函数
            //当前位置与目标位置的距离之和
            for (int i = 0; i < 9; i++) {
                for(int j=0;j<9;j++){
                    int res1=0;
                    int res2=0;
                    int res3=0;
                    if (num[i] == target.getNum()[j]) {
                        if(Math.abs(j - i)>=3){
                            res3=Math.abs(j - i)/3;
                            res1 = Math.abs(j - i) % 3;
                        }
                        else{
                            res2= Math.abs(j - i) ;
                        }
                        temp+=res1+res2+res3;
                        break;
                    }
                }
            }
            //与目标状态相比的错位个数作为Hn
    //        for (int i = 0; i < 9; i++) {
    //            if (num[i] != target.getNum()[i])
    //                temp++;
    //        }
            this.setHn(temp);         //初始化Hn
            if (this.getParent() == null) {
                this.setGn(0);
            } else {
                this.Gn = this.parent.getGn() + 1;
            }
            this.setFn(this.getGn() + this.getHn());
        }
    
        /*
         * 求逆序值并判断是否有解
         */
        public boolean isSolvable(EightPuzzle target) {
            int reverse = 0;
            for (int i = 0; i < 9; i++) {  //计算逆序数
                for (int j = 0; j < i; j++) {
                    if (num[j] > num[i])
                        reverse++;
                    if (target.getNum()[j] > target.getNum()[i])
                        reverse++;
                }
            }
            if (reverse % 2 == 0)//如果逆序数奇偶性相同
                return true;
            return false;
        }
    
        @Override
        public int compareTo(Object o) {
            EightPuzzle c = (EightPuzzle) o;
            return this.Fn - c.getFn();//默认排序为f(n)由小到大排序
        }
    
        //返回0在8数码中的位置
        public int getZeroPosition() {
            int position = -1;
            for (int i = 0; i < 9; i++) {
                if (this.num[i] == 0) {
                    position = i;
                }
            }
            return position;
        }
    
        //判断当前状态是否存在于open表中
        public int isContains(ArrayList<EightPuzzle> open) {
            for (int i = 0; i < open.size(); i++) {
                if (Arrays.equals(open.get(i).getNum(), getNum())) {
                    return i;
                }
            }
            return -1;
        }
    
        //下标小于3的不能上移
        public boolean isMoveUp() {
            int position = getZeroPosition();
            if (position <= 2) {
                return false;
            }
            return true;
        }
    
        //大于6不能下移
        public boolean isMoveDown() {
            int position = getZeroPosition();
            if (position >= 6) {
                return false;
            }
            return true;
        }
    
        //0,3,6不能左移
        public boolean isMoveLeft() {
            int position = getZeroPosition();
            if (position % 3 == 0) {
                return false;
            }
            return true;
        }
    
        //2,5,8不能右移
        public boolean isMoveRight() {
            int position = getZeroPosition();
            if ((position) % 3 == 2) {
                return false;
            }
            return true;
        }
    
        //  move 0:上,1:下,2:左,3:右
        //  返回移动后的状态
        public EightPuzzle moveUp(int move) {
            EightPuzzle temp = new EightPuzzle();
            int[] tempnum = (int[]) num.clone();
            temp.setNum(tempnum);
            int position = getZeroPosition();    //0的位置
            int p = 0;                            //与0换位置的位置
            switch (move) {
                case 0:
                    p = position - 3;  //往上
                    temp.getNum()[position] = num[p];
                    break;
                case 1:
                    p = position + 3;  //往下
                    temp.getNum()[position] = num[p];
                    break;
                case 2:
                    p = position - 1;  //往左
                    temp.getNum()[position] = num[p];
                    break;
                case 3:
                    p = position + 1;  //往右
                    temp.getNum()[position] = num[p];
                    break;
            }
            temp.getNum()[p] = 0;
            return temp;
        }
    
    
          //按照八数码的格式输出
    
        public void print() {
            for (int i = 0; i < 9; i++) {
                if (i % 3 == 2) {
                    System.out.println(this.num[i]);
                } else {
                    System.out.print(this.num[i] + "  ");
                }
            }
        }
    
    
         //反序列输出状态
    
        public void printRoute() {
            EightPuzzle temp = null;
            int count = 0;
            temp = this;
            while (temp != null) {
                temp.print();
                System.out.println("F(n):"+temp.getFn()+" "+"G(n):"+ temp.getGn()+" "+"H(n):"+ temp.getHn());
                System.out.println("--------------------");
                temp = temp.getParent();
                count++;
            }
            System.out.println("步骤数:" + (count - 1));
        }
    
        /**
          open   open表
          close  close表
          parent 父状态
          target 目标状态
         */
        public void operation(ArrayList<EightPuzzle> open, ArrayList<EightPuzzle> close, EightPuzzle parent, EightPuzzle target) {
            if (this.isContains(close) == -1) {   //当前状态不在close表中,若在close表中说明已经拓展过了,跳过
                int position = this.isContains(open);  //当前状态在open表中的位置
                if (position == -1) {        //当前状态不在open表中
                    this.parent = parent;    //既不在open表中也不在close表中,则将其状态设置为父状态
                    this.init(target);      //初始化Fn
                    open.add(this);      //加入open表中
                } else {
                    if (this.getGn() < open.get(position).getGn()) {  //如果在open表中,比较Gn大小,小的话替换
                        open.remove(position);
                        this.parent = parent;
                        this.init(target);
                        open.add(this);
                    }
                }
            }
        }
    }
    
    
    
    展开全文
  • 八数码java代码

    2011-11-07 23:53:02
    八数码java实现,写着玩的,保存下,到别处下~
  • JAVA实现a*算法八数码问题

    热门讨论 2008-12-15 21:42:19
    JAVA写的A*算法实现八数码问题,能运行。
  • AStar解决八数码问题(java实现)

    千次阅读 2012-12-10 09:21:08
    八数码游戏(八数码问题)描述为:在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变...
  • 使用java语言写的八数码问题,仅供参考。其中用到了启发式搜索算法
  • import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Eight { public static int[] flags = { -1, -3, 1, 3 }; // left,up,right,down p...
  • 人工智能实验-八数码问题 3×3九宫棋盘,放置数码为1 -8的8个棋牌,剩下一个空格,只能通过棋牌向空格的移动来改变棋盘的布局。 要求:根据给定初始布局(即初始状态)和目标布局(即目标状态),如何移动棋牌才能从...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,274
精华内容 1,309
关键字:

八数码问题java

java 订阅