EightPuzzle.rar

  • PUDN用户
    了解作者
  • Java
    开发工具
  • 4KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 17
    下载次数
  • 2009-11-22 15:58
    上传日期
A*算法实现八数码问题的解决,清华的人工智能课的作业,相信对后面的人有用。
EightPuzzle.rar
  • 2007011413-第二次程序
  • EightPuzzle.java
    9.3KB
  • Inter.java
    158B
  • Test.java
    379B
  • 〲㜰㄰㐱㌱딭뛚듾돎탌峲敲摡敭琮瑸
    544B
内容介绍
/** 实现Inter.java接口中的函数 不要添加 package语句 */ import java.util.*; /**实验者:王齐双 * 功能:A*算法求解八数码问题 * 产生式说明:f(n)=g(n)+h(n),其中g(n)为当前状态的层数,h(n)为该状态中不在位的将牌离自己应当所在位的距离之和。和书上80页介绍的是一样的。 * 实验的算法过程和书上介绍的一样。 */ class EightNode { /** * 自己定义的一个类,一个对象表示一个状态,包括八数码的分布,该状态 * 对应的f,g。而h通过后面的函数可以求出来 */ private int f; private int g; private int []num;//一维数组的结构用来存储一个八数码状态 private EightNode parent;//生成当前状态的前一个状态 public EightNode()//构造函数 { f=0; g=0; num=new int[9]; parent=null; } //下面几个函数均是用于状态里面变量的操作,包括赋值,取值等 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 int []getNum() { return num; } public void setNum(int num[]) { this.num=num; } public EightNode getParent() { return parent; } public void setParent(EightNode parent) { this.parent=parent; } //将一维数组表示的状态转换成字符串表示 /*public String numToString() { String str=new String(""); for(int i=0;i<9;i++) str=str+num[i]; return str; }*/ public String toString() { String str=new String(""); for(int i=0;i<num.length;i++) str=str+num[i]; return str; } //显示该状态的数组,用于调试 public void show() { for(int i=0;i<9;i++) { System.out.print(num[i]); } System.out.println(); } } public class EightPuzzle implements Inter{ /** 不要定义static 的变量 */ //ArrayList<Hashtable<Integer,String>> open; //ArrayList<Hashtable<Integer,String>> close; PriorityQueue<EightNode> openQueue; //优先级队列,存储的元素是节点状态,自动调整,将f最小的排在队列最前 HashSet<String> open; //open表,将一个状态的字符串当做一个对象放在open表中 HashSet<String> close; //close表 String target=new String("123804765");//目标状态的字符串表示 EightNode targetNode; //目标节点 int []targetArray=new int[9]; EightPuzzle()//构造函数 { targetNode=null; //重新定义优先级队列的比较方法,根据加入到优先级队列中节点的f来比较 openQueue = new PriorityQueue<EightNode>(20,new Comparator<EightNode>(){ public int compare(EightNode node1, EightNode node2) { return node1.getf()-node2.getf(); } }); open=new HashSet<String>(); close=new HashSet<String>(); targetArray=change(target); } public String[] getStrategy(String initState){ //判断是否有解,利用起始串和目标串逆序数的奇偶性 if(!Issolve(initState,target)) {//如果没有解,返回空串 System.out.println("No solution!"); return null; } //将起始串读取出来放在数组里面 int start[]=new int[9]; start=change(initState); EightNode startNode=new EightNode(); startNode.setNum(start); startNode.setf(calH(start)); openQueue.add(startNode); open.add(startNode.toString()); //targetNode.setNum(targetArray); /** 说明: 这里是你的实现,用A*算法解决八数码问题 输入为一个字符串,表示初始状态, 输出是一个字符串的数组,表示解答过程,第i个元素表示第i步后九宫格的状态 第0个元素表示初始状态,如 "283164705"; …………………… 最后一个元素表示最终状态,即 "123804765"; 如果没有解,返回一个只有一个元素"no solution"的字符串数组 your code; */ EightNode firstNode; while(true) {//一直循环,知道找到目标状态 firstNode=openQueue.poll();//获得openQueue队列的头,即open中f最小的 if(isTarget(firstNode)) { //System.out.println("Hello"); break; } close.add(firstNode.toString());//将该节点加入到close中 open.remove(firstNode.toString());//在open中将该节点删除 tuozhan(firstNode); //从该节点拓展 } //依次得到解得求解过程 Stack<EightNode> stack=new Stack<EightNode>(); EightNode tempNode=targetNode; //tempNode.show(); while(tempNode!=null) { //tempNode.show(); stack.push(tempNode); tempNode=tempNode.getParent(); } String []str=new String[stack.size()]; int k=0; //将加入到栈里面的数都读出来 while(!stack.isEmpty()) { str[k]=stack.pop().toString(); k++; } return str; } //根据root节点进行拓展,拓展出来新的节点放入到open中去 void tuozhan(EightNode root) { int []rootArray=new int[9]; rootArray=root.getNum(); int location=0; //标记为0所在的位置 //求出0所在的位置 for(int i=0;i<9;i++) if(rootArray[i]==0) { location=i; break; } //下面四个判断分别向四个方向进行拓展 if(location>2)//0位不在0,1,2三个位置时,上升拓展 { int currentArray[]=new int[9];//用来标记新的节点数组 /*for(int i=0;i<9;i++) { System.out.print(rootArray[i]+" "); }*/ for(int i=0;i<9;i++) currentArray[i]=rootArray[i]; currentArray[location]=currentArray[location-3]; currentArray[location-3]=0; EightNode newNode=new EightNode();//建立新的节点 newNode.setNum(currentArray); //设置该节点的数 newNode.setg(root.getg()+1); //层数增加1 newNode.setf(root.getg()+1+calH(currentArray));//f=g+h newNode.setParent(root); /*for(int i=0;i<9;i++) { System.out.print(currentArray[i]); }*/ if(!openOrclose(newNode)) { openQueue.add(newNode); open.add(newNode.toString()); } } if(location<6) //0位不在6,7,8三个位置时,可以向下拓展 { int currentArray[]=new int[9];//用来标记新的节点数组 for(int i=0;i<9;i++) currentArray[i]=rootArray[i]; currentArray[location]=currentArray[location+3]; currentArray[location+3]=0; EightNode newNode=new EightNode();//建立新的节点 newNode.setNum(currentArray); //设置该节点的数 newNode.setg(root.getg()+1); //层数增加1 newNode.setf(root.getg()+1+calH(currentArray));//f=g+h newNode.setParent(root); if(!openOrclose(newNode)) { openQueue.add(newNode); open.add(newNode.toString()); } } if((location%3)!=0) //0的位置不在0,3,6这三个位置,即可以向左移动 { int currentArray[]=new int[9];//用来标记新的节点数组 for(int i=0;i<9;i++) currentArray[i]=rootArray[i]; currentArray[location]=currentArray[location-1]; currentArray[location-1]=0; EightNode newNode=new EightNode();//建立新的节点 newNode.setNum(currentArray); //设置该节点的数 newNode.setg(root.getg()+1); //层数增加1 newNode.setf(root.getg()+1+calH(currentArray));//f=g+h newNode.setParent(root); if(!openOrclose(newNode)) { openQueue.add(newNode); open.add(newNode.toString()); } } if((location%3)!=2) //0的位置不在2,5,8三个位置时可以向右拓展 { int currentArray[]=new int[9];//用来标记新的节点数组 for(int i=0;i<9;i++) currentArray[i]=rootArray[i]; currentArray[location]=currentArray[location+1]; currentArray[location+1]=0; EightNode newNode=new EightNode();//建立新的节点 newNode.setNum(currentArray); //设置该节点的数 newNode.setg(root.getg()+1); //层数增加1 newNode.setf(root.getg()+1+calH(currentArray));//f=g+h newNode.setParent(root); if(!openOrclose(newNode)) { openQueue.add(newNode); open.add(newNode.toString()); } } } boolean openOrclose(EightNode node) { if(open.contains(node.toString())||close.contains(node.toString())) return true; else return false; } boolean Issolve(String start,String target) //判断是否存在解得函数 { int star_num=0,tar_num=0; int i,j; //求解两个字符串的逆序数 for(i=0;i<9;i++) { for(j=0;j<i;j++) { if(start.charAt(j)<start.charAt(i) && start.charAt(j)!='0') star_num++; if(target.charAt(j)<target.charAt(i) && target.charAt(j)!='0') tar_num++; } } //利用逆序数的奇偶性 star_num=star_num%2; tar_num=tar_num%2;
评论
    相关推荐
    • 八数码问题.rar
      八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。
    • 八数码问题.zip
      求解八数码问题,感觉还可以,欢迎各位下载
    • 八数码问题.zip
      此代码完成了经典的八数码问题,使用c++语言
    • 八数码.zip
      这是一个专门用于解决·八数码问题的C++程序
    • 八数码问题
      八数码问题代码实现,使用了Astar算法以及二叉堆.
    • 八数码问题
      人工智能经典八数码问题,以数学逻辑完成人工智能.
    • 八数码问题
      通过设计一个八数码问题求解程序,学习、了解状态空间搜索的思想,进一步加深对人工智能课程相关启发式搜索的理解。 z实验内容 1. 针对八数码问题,在Windows环境下用C/C++语言(Java语言)实现几种搜索算法(最好是...
    • 八数码问题.zip
      数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。...解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
    • 八数码问题.zip
      matlab中八数码问题代码(A*算法实例)
    • 八数码.rar
      八数码A星版本,头文件中是所有函数的定义,输入按照main.cpp的格式