八数码问题的Java修正版

package exercise0; public class test5 { public final static int MAXSIZE = 65535; public static void main(String[] args) { // long start = System.currentTimeMillis();// 开始时间 long startTime = System.nanoTime(); // 声明变量 OneState x, y; // 初始状态x，及目标状态y OneState[] Graph; // 搜索树 SqQueue Open; // 队列 SqStack Close; // 栈 Operators Operator; // 操作 int count1 = 0; // 结点编号 // int[][] mid1 = { { 2, 8, 3 }, { 1, 0, 4 }, { 7, 6, 5 } }; // int[][] mid2 = { { 1, 2, 3 }, { 8, 0, 4 }, { 7, 6, 5 } }; int[][] mid1 = { { 6, 7, 8, 9 }, { 5, 0, 1, 10 }, { 4, 3, 2, 11 }, }; int[][] mid2 = { { 6, 7, 8, 9 }, { 5, 1, 10, 0 }, { 4, 3, 2, 11 }, }; // 初始化主要变量 x = new OneState(mid1); y = new OneState(mid2); Graph = new OneState[MAXSIZE]; Open = new SqQueue(); Close = new SqStack(); Operator = new Operators(); // 判断问题是否可解，若可解则进行搜索 if (!Operator.isRightOrder(x, y)) { System.out.println("该问题无解，不能由初始状态经规定操作到达目标状态！"); } else { if (Operator.stateCompare(x, y) == true) System.out.println("the start state is the end start"); else { Open.EnQueue(x); // OneState p = new OneState(x); OneState p, q; // 根结点入图 Graph[++count1] = new OneState(mid1); Graph[count1].setParent(0); Graph[count1].setLayer(1); Graph[count1].setId(1); Graph[count1].setEstimate(y); Graph[count1].setOperate(operator.ROOT); while (!Open.IsEmpty()) { Open.SelectSort(); p = new OneState(Open.DeQueue()); q = new OneState(p); // MOVELEFT if (Operator.moveLeft(p)) { if (Operator.notContain(p, Graph, count1)) { p.setParent(p.getId()); p.setLayer(p.getLayer() + 1); p.setId(++count1); p.setEstimate(y); p.setOperate(operator.LEFT); Graph[count1] = p; if (Operator.stateCompare(p, y)) break; else Open.EnQueue(Graph[count1]); } p = new OneState(q); } // MOVERIGHT if (Operator.moveRight(p)) { if (Operator.notContain(p, Graph, count1)) { p.setParent(p.getId()); p.setLayer(p.getLayer() + 1); p.setId(++count1); p.setEstimate(y); p.setOperate(operator.RIGHT); Graph[count1] = p; if (Operator.stateCompare(p, y)) break; else Open.EnQueue(Graph[count1]); } p = new OneState(q); } // MOVEUP if (Operator.moveUp(p)) { if (Operator.notContain(p, Graph, count1)) { p.setParent(p.getId()); p.setLayer(p.getLayer() + 1); p.setId(++count1); p.setEstimate(y); p.setOperate(operator.UP); Graph[count1] = p; if (Operator.stateCompare(p, y)) break; else Open.EnQueue(Graph[count1]); } p = new OneState(q); } // MOVEDOWN if (Operator.moveDown(p)) { if (Operator.notContain(p, Graph, count1)) { p.setParent(p.getId()); p.setLayer(p.getLayer() + 1); p.setId(++count1); p.setEstimate(y); p.setOperate(operator.DOWN); Graph[count1] = p; if (Operator.stateCompare(p, y)) break; else Open.EnQueue(Graph[count1]); } p = new OneState(q); } }// while // 判断本方法是否已找到解，若已找到，则输出 if (Open.IsEmpty()) System.out.println("本方法没有找到可达路径，请改变搜索长度，或使用其他方法！"); else { for (int i = count1; i > 0;) { Close.Push(Graph[i]); i = Graph[i].getParent(); } System.out.println("输出八数码问题启发式搜索的最优路径如下：\n"); while (!Close.IsEmpty()) { p = Close.PoP(); p.display(); } } }// else1 }// else0 // long end = System.currentTimeMillis();// 终止时间 // System.out.println("Run Time：" + (end - start) + "ms"); long endTime = System.nanoTime();// 终止时间 System.out.println("Run Time：" + (endTime - startTime) / 1000000.0 + "ms"); } }