• PUDN用户
    了解作者
  • Java
    开发工具
  • 7KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 4
    下载次数
  • 2012-06-16 10:37
    上传日期
九宫格问题求解,包含广度优先,有界深度优先以及全局择优三种算法,自己写的,比较简单
jiugong.rar
  • jiugong
  • bin
  • state.class
    3KB
  • jiugong.class
    5.1KB
  • .settings
  • org.eclipse.jdt.core.prefs
    629B
  • src
  • jiugong.java
    5.9KB
  • state.java
    2KB
  • .project
    383B
  • .classpath
    301B
内容介绍
import java.util.*; public class jiugong{ public static boolean BFS(state s0,state s1){ Queue <state> open=new LinkedList<state>(); Stack <state> closed=new Stack<state> (); open.offer(s0); state s=new state(s0); state ns; int flag=0; while(!open.isEmpty()){ s=open.poll(); //s.print(); closed.push(s); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.offer(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } break; } } if(flag==1){ flag=0; break; } } } return false; } public static boolean DFS(state s0,state s1){ Stack <state> open=new Stack<state> (); Stack <state> closed=new Stack<state> (); s0.depth=0; s0.parent=null; open.push(s0); state s; state ns; int flag=0; int maxDepth=4; while(!open.isEmpty()){ s=open.pop(); if(s.depth>maxDepth){ continue; } // s.print(); closed.push(s); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.push(ns); ns.parent=s; ns.depth=ns.parent.depth+1; } } break; } } if(flag==1){ flag=0; break; } } } return false; } public static boolean GPS(state s0,state s1){ ArrayList <state> open=new ArrayList <state>(); Stack <state> closed=new Stack <state>(); s0.depth=0; s0.parent=null; s0.value=state.different(s0,s1)+s0.depth; open.add(s0); state s; state ns; int flag=0; while(!open.isEmpty()){ s=open.get(0); open.remove(0); closed.push(s); // s.print(); if(s.equals(s1)){ //输出正确寻找路径 Stack <state> printStack=new Stack<state> (); while(s.parent != null){ printStack.push(s); s=s.parent ; } printStack.push(s); while(!printStack.isEmpty()){ printStack.pop().print(); } return true; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s.number[i][j]==0){ flag=1; if(j!=0){ ns=new state(s); ns.number[i][j]=ns.number[i][j-1]; ns.number[i][j-1]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(i!=0){ ns=new state(s); ns.number[i][j]=ns.number[i-1][j]; ns.number[i-1][j]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(j!=2){ ns=new state(s); ns.number[i][j]=ns.number[i][j+1]; ns.number[i][j+1]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } if(i!=2){ ns=new state(s); ns.number[i][j]=ns.number[i+1][j]; ns.number[i+1][j]=0; if(!ns.in(closed)){ open.add(ns); ns.parent=s; ns.depth=ns.parent.depth+1; ns.value=state.different(ns,s1)+ns.depth; } } break; } } if(flag==1){ flag=0; break; } } state.sort(open); } return false; } public static void main(String [] args) { int num0[][]={{1,3,4},{8,2,0},{7,6,5}}; state state0=new state(num0); int numn[][]={{1,2,3},{8,0,4},{7,6,5}}; state state1=new state(numn); //BFS(state0,state1); //DFS(state0,state1); GPS(state0,state1); } }
评论
    相关推荐
    • BidirectConstrGaph.zip
      图论中二分图匹配算法求解的matlab代码
    • suduGame.zip
      求解数独,根据递归唯一余数法和摒除法求解,如果无法解决在递归假设法求解
    • 数独解法.zip
      在excel的单元格中填制已知的数,通过树叉的回溯,完成数独未知数的填制。
    • A*算法 计算九宫格数字移动问题
      今天进行程序的测试,发现运算速度相当缓慢,当使用876,543,210这个矩阵变换,运算了130k+步骤,耗时有半个小时多。经过简单 计算,九个格子放入九个数,就有A99种排列组合,结果是360K+,所以当程序运行到100K+...
    • 数独编辑器 1.002版
      小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。压缩包中附带了若干...
    • java数独计算器升级版(包含出题器)
      第一部分:纯java实现的数独计算器,使用回溯法递归求解。同时实现了唯一候选值法、隐性唯一候选值法、区块删减法等最优求解法。 第二部分:java数独出题器,运用回溯算法实现自定义出题,绝对的随机出题,可以...
    • 字母拼图-C语言
      类似于A*算法的求解宫格问题,实现字母拼图。通过按键盘来移动对应的字母。
    • java数独计算器
      纯java实现的数独计算器,使用回溯法递归求解。同时实现了唯一候选值法、隐性唯一候选值法、区块删减法等最优求解法。
    • 广度优先 深度优先 九宫格
      人工智能 用启发式方法搜索求解九宫格问题 广度优先 深度优先 九宫格
    • matlabcnhelp.rar
      matlab中文帮助很难找的,快速下载