【人工智能导论】A*算法求解15数码问题 Java

2024-07-13 06:35| 来源: 网络整理| 查看: 265

完整源码 - Eclipse项目文件 - GitHub地址题目描述

在这里插入图片描述

关于本算法

两个晚上写完的，不足之处多多指教…

启发函数的选择：

一开始选用不在位数码个数+节点深度作为启发函数，效果不是很好。

后来改用所有数码到目标位置的矩形距离+节点深度作为启发函数，计算出：

从初始到达目标状态深度为14（步），见附录一共进行了68次拓展最后一次拓展时Open表Board个数为70 /** * 设计一个启发函数,利用A*算法求解15数码问题 * * 要求: 尽可能用与A*算法一致的思路实现算法, 力求简单明了地给出一个解. * 1)打印并上交带有关键步骤说明的程序代码. * 2)演示运行过程,并回答老师的询问 * * @author luyang.gong * * f(n)=g(n)+h(n) * g(n):已经走过 * h(n):对未来的估计 * * Begin：读入初始状态和目标状态，并计算初始状态评价函数值f；初始化两个open表和closed表，将初始状态放入open表中 If（open表为空）查找失败； End if else ① 在open表中找到评价值最小的节点，作为当前结点，并放入closed表中； ② 判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③ 对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点； ④ 对于新扩展的状态结点，进行如下操作： A．新节点既不在open表中，也不在closed表中，则ADD (mj, OPEN)； B．新节点在open表中，则 IF f(n-mk) < f(mk) THEN f(mk):=f(n-mk)， C．新节点在closed表中，则IF f(n-ml) < f(ml) THEN f(ml):=f(n-ml)， ⑤ 把当前结点从open表中移除； End if End * */

在这里插入图片描述

题解 - 目录结构

在这里插入图片描述

题解 - 代码实现 Java

Main.java

public class Main { public static Board beginBoard = new Board(Init.BEGINARR); public static Board endBoard = new Board(Init.ENDARR); public static void main(String[] args) { OpenTable openTable = new OpenTable(); openTable.tbArr.add(beginBoard);// 这里需要拷贝逻辑否则复制的只是指针 CloseTable closeTable = new CloseTable(); System.out.println(openTable); Board curBoard = null; int count = 0; while (openTable.tbArr.size() != 0) { System.out.println("第" + ++count + "次拓展"); openTable.sortItSelf(); curBoard = openTable.getMinBoard(); closeTable.tbArr.add(curBoard); // 是否为end if (curBoard.equals(endBoard)) { System.out.println("SUCCESS:" + curBoard); while (curBoard.parentBoard != null) { System.out.println("上一步："); System.out.println(curBoard.parentBoard); curBoard = curBoard.parentBoard; } break; } // 4方向拓展 for (int s = 0; s if (curBoard.canDown()) { newBoard = curBoard.goDown(); } else { continue; } } else if (s == 1) { if (curBoard.canUp()) { newBoard = curBoard.goUp(); } else { continue; } } else if (s == 2) { if (curBoard.canRight()) { newBoard = curBoard.goRight(); } else { continue; } } else if (s == 3) { if (curBoard.canLeft()) { newBoard = curBoard.goLeft(); } else { continue; } } if (openTable.hasBoard(newBoard)) {// 新节点在open表中比较已有fn和新节点fn的大小 Board oldBoard = openTable.getBoardByArr(newBoard.arr); if (newBoard.fn newBoard.childBoards.get(i).parentBoard = newBoard; } // 删旧的增新的 openTable.tbArr.remove(openTable.getIndex(oldBoard)); openTable.tbArr.add(newBoard); System.out.println("openTable:update"); } } else if (closeTable.hasBoard(newBoard)) {// 新节点在close表中 Board oldBoard = closeTable.getBoardByArr(newBoard.arr); if (newBoard.fn newBoard.childBoards.get(i).parentBoard = newBoard; } closeTable.tbArr.remove(closeTable.getIndex(oldBoard)); // closeTable.tbArr.add(newBoard); openTable.tbArr.add(newBoard);// 重新放回open表中 System.out.println("openTable:update"); } } else {// 两表都不在 openTable.tbArr.add(newBoard); System.out.println("openTable:add"); } } openTable.tbArr.remove(openTable.getIndex(curBoard)); } } }

Init.java

package cn.hanquan.ai; public class Init { /** * 数组大小 */ public static final int SIZE = 4; /** * 初始状态 */ public static final int[][] BEGINARR = { { 5, 1, 2, 4 }, { 9, 6, 3, 8 }, { 13, 15, 10, 11 }, { 14, 0, 7, 12 } }; /** * 目标状态 */ public static final int[][] ENDARR = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 0 } }; }

Utils.java

package cn.hanquan.ai; public class Utils { /** * 计算不在位的将牌个数 * @param tbArr 15数码的一个状态 * @return 不在位的将牌个数 */ public static int getAbsentCount(Board curBoard, Board endBoard) { // System.out.println(curBoard); // System.out.println(endBoard); int count = 0; for (int i = 0; i label: for (int m = 0; m if (curBoard.arr[i][j] == endBoard.arr[m][n]) { count += getDistance(i, j, m, n); break label; } } } } } return count; } /** * 计算两坐标的矩形距离 * @param x1 * @param y1 * @param x2 * @param y2 * @return */ public static int getDistance(int x1,int y1,int x2,int y2) { return Math.abs(x1-x2)+Math.abs(y1-y2); } /** * 计算不在位的将牌个数重载 * @param arr 15数码的一个状态 * @return 不在位的将牌个数 */ public static int getAbsentCount(Board curBoard, int[][] arr) { // System.out.println(curBoard); // System.out.println(endBoard); int count = 0; for (int i = 0; i if (curBoard.arr[i][j] != 0 && curBoard.arr[i][j] != arr[i][j]) { count++; } } } return count; } }

Board.java

package cn.hanquan.ai; import java.util.ArrayList; import java.util.Arrays; public class Board { /** * 将牌状态 */ public int[][] arr; /** * 总耗散值 */ public int fn=-1; /** * 当前已走深度(耗散值) */ public int dn=0; /** * 不在位将牌个数(耗散值) */ public int hn=-1; /** * 父节点 */ public Board parentBoard; /** * 子节点列表 */ public ArrayList childBoards=new ArrayList(); public Board(int[][] arr) { super(); this.arr = arr; this.dn = 0; this.hn = Utils.getAbsentCount(this, Init.ENDARR); this.fn = this.dn + this.hn; } public Board() { super(); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("\n"); for (int i = 0; i sb.append(arr[i][j] + "\t"); } sb.append("\n"); } sb.append("fn gn hn = " + fn + " " + dn + " " + hn+"\n"); return sb.toString(); } /** * 复制本身arr数值 * @return */ public int[][] copySelfArr() { int[][] newArr = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; for (int i = 0; i newArr[i][j] = arr[i][j]; } } return newArr; } /** * 判断两个board是否arr值相等 * @param board * @return */ public boolean equals(Board board) { boolean isEqual = true; for (int i = 0; i if (arr[i][j] != board.arr[i][j]) { isEqual = false; break; } } } return isEqual; } /** * 重载，判断board和arr是否值相等 * @param board * @return */ public boolean equals(int[][] array) { boolean isEqual = true; for (int i = 0; i if (arr[i][j] != array[i][j]) { isEqual = false; break; } } } return isEqual; } /** * 是否可以向下移动 * @return */ public boolean canDown() { boolean isOK = true; label: for (int i = 0; i if (arr[i][j] == 0 && i == Init.SIZE-1) { isOK = false; break label; } } } System.out.println("canDown:"+isOK); return isOK; } /** * 是否可以向右移动 * @return */ public boolean canRight() { boolean isOK = true; label: for (int i = 0; i if (arr[i][j] == 0 && j == Init.SIZE-1) { isOK = false; break label; } } } System.out.println("canRight:"+isOK); return isOK; } /** * 是否可以向左移动 * @return */ public boolean canLeft() { boolean isOK = true; label: for (int i = 0; i if (arr[i][j] == 0 && j == 0) { isOK = false; break label; } } } System.out.println("canLeft:"+isOK); return isOK; } /** * 是否可以向上移动 * @return */ public boolean canUp() { boolean isOK = true; label: for (int i = 0; i if (arr[i][j] == 0 && i == 0) { isOK = false; break label; } } } System.out.println("canUp:" + isOK); return isOK; } /** * 向下移动 * @return */ public Board goDown() { System.out.println("Go Down"); Board newBoard = new Board(this.copySelfArr()); label: for (int i = 0; i if (newBoard.arr[i][j] == 0) { int t; t = newBoard.arr[i][j]; newBoard.arr[i][j] = newBoard.arr[i + 1][j]; newBoard.arr[i + 1][j] = t; break label;// 这里label退出循环！！避免重复操作！！ } } } newBoard.dn = this.dn + 1;// 深度 newBoard.hn = Utils.getAbsentCount(newBoard, Main.endBoard);// 不在位将牌个数 newBoard.fn = newBoard.dn + newBoard.hn; newBoard.parentBoard=this; this.childBoards.add(newBoard); return newBoard; } /** * 向上移动 * @return */ public Board goUp() { System.out.println("Go Up"); Board newBoard = new Board(this.copySelfArr());//这里不能这样复制 label: for (int i = 0; i if (newBoard.arr[i][j] == 0) { int t; t = newBoard.arr[i][j]; newBoard.arr[i][j] = newBoard.arr[i - 1][j]; newBoard.arr[i - 1][j] = t; break label; } } } newBoard.dn = this.dn + 1;// 深度 newBoard.hn = Utils.getAbsentCount(newBoard, Main.endBoard);// 不在位将牌个数 newBoard.fn = newBoard.dn + newBoard.hn; newBoard.parentBoard = this; this.childBoards.add(newBoard); return newBoard; } /** * 向右移动 * @return */ public Board goRight() { System.out.println("Go Right"); Board newBoard = new Board(this.copySelfArr()); label: for (int i = 0; i if (newBoard.arr[i][j] == 0) { int t; t = newBoard.arr[i][j]; newBoard.arr[i][j] = newBoard.arr[i][j+1]; newBoard.arr[i][j+1] = t; break label; } } } newBoard.dn = this.dn + 1;// 深度 newBoard.hn = Utils.getAbsentCount(newBoard, Main.endBoard);// 不在位将牌个数 newBoard.fn = newBoard.dn + newBoard.hn; newBoard.parentBoard=this; this.childBoards.add(newBoard); return newBoard; } /** * 向左移动 * @return */ public Board goLeft() { System.out.println("Go Left"); Board newBoard = new Board(this.copySelfArr()); label: for (int i = 0; i if (newBoard.arr[i][j] == 0) { int t; t = newBoard.arr[i][j]; newBoard.arr[i][j] = newBoard.arr[i][j-1]; newBoard.arr[i][j-1] = t; break label; } } } newBoard.dn = this.dn + 1;// 深度 newBoard.hn = Utils.getAbsentCount(newBoard, Main.endBoard);// 不在位将牌个数 newBoard.fn = newBoard.dn + newBoard.hn; newBoard.parentBoard=this; this.childBoards.add(newBoard); return newBoard; } }

OpenTable.java

package cn.hanquan.ai; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; /** * Open表 * @author luyang.gong * */ public class OpenTable { public ArrayList tbArr = new ArrayList(); /** * Open表排序 */ public void sortItSelf() { Collections.sort(tbArr, new Comparator() { @Override public int compare(Board b1, Board b2) {// 重写 Comparator 函数 if (b1.fn b2.fn) return 1; else return 0; } }); System.out.println("Open表Board个数："+this.tbArr.size()); // System.out.println("排序后：\n"+tbArr); System.out.println("最小fn="+tbArr.get(0)); System.out.println("\n"); } /** * 返回fn最小Board * @return */ public Board getMinBoard() { return tbArr.get(0); } /** * 判断Table中是否包含某个board * @param board * @return */ public boolean hasBoard(Board board) { boolean hasBoard = false; for (int i = 0; i hasBoard = true; break; } } return hasBoard; } /** * 获取Board在OpenTable中的索引 * @param board * @return 索引值 */ public int getIndex(Board board) { int index=-1; for (int i = 0; i index = i; break; } } return index; } public Board getBoardByArr(int[][] array){ for (int i = 0; i return tbArr.get(i); } } try { throw new Exception("Opentable:不存在该arr!"); } catch (Exception e) { e.printStackTrace(); } return null; } @Override public String toString() { StringBuilder sb=new StringBuilder(); sb.append("\n"); sb.append("OpenTable:\n"); for(int i=0;i ArrayList tbArr = new ArrayList(); /** * 判断Table中是否包含某个board * @param board * @return */ public boolean hasBoard(Board board) { boolean hasBoard = false; for (int i = 0; i hasBoard = true; break; } } return hasBoard; } /** * 获取Board在CloseTable中的索引 * @param board * @return 索引值 */ public int getIndex(Board board) { int index=-1; for (int i = 0; i index = i; break; } } return index; } public Board getBoardByArr(int[][] array){ for (int i = 0; i return tbArr.get(i); } } try { throw new Exception("Closetable:不存在该arr!"); } catch (Exception e) { e.printStackTrace(); } return null; } } 附：输出结果

（这个倒着看，在SUCCESS之后，反向输出了一下过程）

OpenTable: 5 1 2 4 9 6 3 8 13 15 10 11 14 0 7 12 fn gn hn = 12 0 12 第1次拓展 Open表Board个数：1 最小fn= 5 1 2 4 9 6 3 8 13 15 10 11 14 0 7 12 fn gn hn = 12 0 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第2次拓展 Open表Board个数：3 最小fn= 5 1 2 4 9 6 3 8 13 0 10 11 14 15 7 12 fn gn hn = 17 1 16 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第3次拓展 Open表Board个数：5 最小fn= 5 1 2 4 9 6 3 8 13 10 0 11 14 15 7 12 fn gn hn = 16 2 14 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第4次拓展 Open表Board个数：7 最小fn= 5 1 2 4 9 6 3 8 13 10 7 11 14 15 0 12 fn gn hn = 15 3 12 canDown:false canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第5次拓展 Open表Board个数：8 最小fn= 5 1 2 4 9 6 3 8 13 10 11 0 14 15 7 12 fn gn hn = 15 3 12 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第6次拓展 Open表Board个数：9 最小fn= 5 1 2 4 9 6 3 8 13 10 11 12 14 15 7 0 fn gn hn = 14 4 10 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第7次拓展 Open表Board个数：9 最小fn= 5 1 2 4 9 6 3 8 13 10 7 11 14 15 12 0 fn gn hn = 16 4 12 canDown:false canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第8次拓展 Open表Board个数：9 最小fn= 5 1 2 4 9 6 3 8 13 10 7 11 14 0 15 12 fn gn hn = 16 4 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第9次拓展 Open表Board个数：10 最小fn= 5 1 2 4 9 6 3 8 13 15 10 11 14 7 0 12 fn gn hn = 17 1 16 canDown:false canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第10次拓展 Open表Board个数：11 最小fn= 5 1 2 4 9 6 3 8 13 15 10 11 0 14 7 12 fn gn hn = 17 1 16 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:false 第11次拓展 Open表Board个数：11 最小fn= 5 1 2 4 9 6 3 8 13 10 11 12 14 15 0 7 fn gn hn = 17 5 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第12次拓展 Open表Board个数：12 最小fn= 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12 fn gn hn = 17 5 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:false 第13次拓展 Open表Board个数：12 最小fn= 5 1 2 4 9 6 3 0 13 10 11 8 14 15 7 12 fn gn hn = 18 4 14 canDown:true Go Down canUp:true Go Up openTable:add canRight:false canLeft:true Go Left openTable:add 第14次拓展 Open表Board个数：13 最小fn= 5 1 2 4 9 6 3 8 13 15 10 11 14 7 12 0 fn gn hn = 18 2 16 canDown:false canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第15次拓展 Open表Board个数：13 最小fn= 5 1 2 4 9 6 3 8 0 15 10 11 13 14 7 12 fn gn hn = 18 2 16 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:false 第16次拓展 Open表Board个数：14 最小fn= 5 1 2 4 9 6 3 8 13 10 11 12 14 0 15 7 fn gn hn = 18 6 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第17次拓展 Open表Board个数：15 最小fn= 5 1 2 4 9 6 3 8 0 10 7 11 13 14 15 12 fn gn hn = 18 6 12 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:false 第18次拓展 Open表Board个数：16 最小fn= 5 1 2 4 9 6 0 8 13 10 3 11 14 15 7 12 fn gn hn = 19 3 16 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第19次拓展 Open表Board个数：18 最小fn= 5 1 2 4 9 6 3 8 13 10 7 0 14 15 12 11 fn gn hn = 19 5 14 canDown:true Go Down canUp:true Go Up openTable:add canRight:false canLeft:true Go Left openTable:add 第20次拓展 Open表Board个数：19 最小fn= 5 1 2 4 9 6 3 8 13 0 7 11 14 10 15 12 fn gn hn = 19 5 14 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第21次拓展 Open表Board个数：21 最小fn= 5 1 2 4 0 6 3 8 9 15 10 11 13 14 7 12 fn gn hn = 19 3 16 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:false 第22次拓展 Open表Board个数：22 最小fn= 5 1 2 4 9 6 3 8 15 0 10 11 13 14 7 12 fn gn hn = 19 3 16 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第23次拓展 Open表Board个数：24 最小fn= 5 1 2 4 9 6 3 8 15 10 0 11 13 14 7 12 fn gn hn = 18 4 14 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第24次拓展 Open表Board个数：26 最小fn= 5 1 2 4 9 6 3 8 15 10 7 11 13 14 0 12 fn gn hn = 17 5 12 canDown:false canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第25次拓展 Open表Board个数：27 最小fn= 5 1 2 4 9 6 3 8 15 10 11 0 13 14 7 12 fn gn hn = 17 5 12 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第26次拓展 Open表Board个数：28 最小fn= 5 1 2 4 9 6 3 8 15 10 11 12 13 14 7 0 fn gn hn = 16 6 10 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第27次拓展 Open表Board个数：28 最小fn= 5 1 2 4 9 6 3 8 15 10 7 11 13 14 12 0 fn gn hn = 18 6 12 canDown:false canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第28次拓展 Open表Board个数：28 最小fn= 5 1 2 4 9 6 3 8 13 10 11 12 0 14 15 7 fn gn hn = 19 7 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:false 第29次拓展 Open表Board个数：28 最小fn= 5 1 2 4 0 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 19 7 12 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:false 第30次拓展 Open表Board个数：29 最小fn= 5 1 2 4 9 6 3 8 10 0 7 11 13 14 15 12 fn gn hn = 19 7 12 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第31次拓展 Open表Board个数：31 最小fn= 5 1 2 4 9 6 3 8 15 10 11 12 13 14 0 7 fn gn hn = 19 7 12 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第32次拓展 Open表Board个数：32 最小fn= 5 1 2 4 9 0 3 8 13 6 10 11 14 15 7 12 fn gn hn = 20 2 18 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第33次拓展 Open表Board个数：34 最小fn= 5 1 2 4 9 6 3 8 0 13 10 11 14 15 7 12 fn gn hn = 20 2 18 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right canLeft:false 第34次拓展 Open表Board个数：35 最小fn= 5 1 2 4 9 6 3 8 13 15 0 11 14 7 10 12 fn gn hn = 20 2 18 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第35次拓展 Open表Board个数：37 最小fn= 5 1 2 4 9 6 3 8 13 15 11 0 14 7 10 12 fn gn hn = 19 3 16 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第36次拓展 Open表Board个数：38 最小fn= 5 1 2 4 9 6 3 8 13 15 11 12 14 7 10 0 fn gn hn = 18 4 14 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第37次拓展 Open表Board个数：38 最小fn= 5 1 2 4 9 6 3 8 13 10 0 12 14 15 11 7 fn gn hn = 20 6 14 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第38次拓展 Open表Board个数：40 最小fn= 5 1 2 4 9 6 8 0 13 10 3 11 14 15 7 12 fn gn hn = 20 4 16 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第39次拓展 Open表Board个数：41 最小fn= 5 1 2 4 9 6 3 8 13 7 0 11 14 10 15 12 fn gn hn = 20 6 14 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第40次拓展 Open表Board个数：43 最小fn= 5 1 2 4 9 6 3 8 13 7 11 0 14 10 15 12 fn gn hn = 19 7 12 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第41次拓展 Open表Board个数：44 最小fn= 5 1 2 4 9 6 3 8 13 7 11 12 14 10 15 0 fn gn hn = 18 8 10 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第42次拓展 Open表Board个数：44 最小fn= 0 1 2 4 5 6 3 8 9 15 10 11 13 14 7 12 fn gn hn = 20 4 16 canDown:true Go Down canUp:false canRight:true Go Right openTable:add canLeft:false 第43次拓展 Open表Board个数：44 最小fn= 1 0 2 4 5 6 3 8 9 15 10 11 13 14 7 12 fn gn hn = 19 5 14 canDown:true Go Down openTable:add canUp:false canRight:true Go Right openTable:add canLeft:true Go Left 第44次拓展 Open表Board个数：45 最小fn= 1 2 0 4 5 6 3 8 9 15 10 11 13 14 7 12 fn gn hn = 18 6 12 canDown:true Go Down openTable:add canUp:false canRight:true Go Right openTable:add canLeft:true Go Left 第45次拓展 Open表Board个数：46 最小fn= 1 2 3 4 5 6 0 8 9 15 10 11 13 14 7 12 fn gn hn = 17 7 10 canDown:true Go Down openTable:add canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第46次拓展 Open表Board个数：48 最小fn= 1 2 3 4 5 6 10 8 9 15 0 11 13 14 7 12 fn gn hn = 18 8 10 canDown:true Go Down openTable:add canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第47次拓展 Open表Board个数：50 最小fn= 1 2 3 4 5 6 10 8 9 15 7 11 13 14 0 12 fn gn hn = 17 9 8 canDown:false canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第48次拓展 Open表Board个数：51 最小fn= 1 2 3 4 5 6 10 8 9 15 11 0 13 14 7 12 fn gn hn = 17 9 8 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第49次拓展 Open表Board个数：52 最小fn= 1 2 3 4 5 6 10 8 9 15 11 12 13 14 7 0 fn gn hn = 16 10 6 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第50次拓展 Open表Board个数：52 最小fn= 1 2 3 4 5 6 8 0 9 15 10 11 13 14 7 12 fn gn hn = 18 8 10 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第51次拓展 Open表Board个数：53 最小fn= 1 2 3 4 5 6 10 8 9 15 7 11 13 14 12 0 fn gn hn = 18 10 8 canDown:false canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第52次拓展 Open表Board个数：53 最小fn= 1 2 4 0 5 6 3 8 9 15 10 11 13 14 7 12 fn gn hn = 19 7 12 canDown:true Go Down openTable:add canUp:false canRight:false canLeft:true Go Left 第53次拓展 Open表Board个数：53 最小fn= 1 2 3 4 5 6 10 8 9 0 15 11 13 14 7 12 fn gn hn = 19 9 10 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第54次拓展 Open表Board个数：55 最小fn= 1 2 3 4 5 6 10 8 9 15 11 12 13 14 0 7 fn gn hn = 19 11 8 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第55次拓展 Open表Board个数：56 最小fn= 1 2 3 4 5 6 8 11 9 15 10 0 13 14 7 12 fn gn hn = 19 9 10 canDown:true Go Down openTable:add canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第56次拓展 Open表Board个数：57 最小fn= 1 2 3 4 5 6 8 11 9 15 10 12 13 14 7 0 fn gn hn = 18 10 8 canDown:false canUp:true Go Up canRight:false canLeft:true Go Left openTable:add 第57次拓展 Open表Board个数：57 最小fn= 5 1 2 4 6 0 3 8 9 15 10 11 13 14 7 12 fn gn hn = 20 4 16 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:true Go Left 第58次拓展 Open表Board个数：59 最小fn= 5 1 2 4 9 6 3 8 15 14 10 11 13 0 7 12 fn gn hn = 20 4 16 canDown:false canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第59次拓展 Open表Board个数：60 最小fn= 5 1 2 4 9 6 3 8 15 10 7 11 13 0 14 12 fn gn hn = 20 6 14 canDown:false canUp:true Go Up openTable:add canRight:true Go Right canLeft:true Go Left openTable:add 第60次拓展 Open表Board个数：61 最小fn= 5 1 2 4 9 6 3 0 15 10 11 8 13 14 7 12 fn gn hn = 20 6 14 canDown:true Go Down canUp:true Go Up openTable:add canRight:false canLeft:true Go Left openTable:add 第61次拓展 Open表Board个数：62 最小fn= 5 1 2 4 9 6 3 8 0 10 11 12 13 14 15 7 fn gn hn = 20 8 12 canDown:true Go Down canUp:true Go Up openTable:add canRight:true Go Right openTable:add canLeft:false 第62次拓展 Open表Board个数：63 最小fn= 0 1 2 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 20 8 12 canDown:true Go Down canUp:false canRight:true Go Right openTable:add canLeft:false 第63次拓展 Open表Board个数：63 最小fn= 1 0 2 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 19 9 10 canDown:true Go Down openTable:add canUp:false canRight:true Go Right openTable:add canLeft:true Go Left 第64次拓展 Open表Board个数：64 最小fn= 1 2 0 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 18 10 8 canDown:true Go Down openTable:add canUp:false canRight:true Go Right openTable:add canLeft:true Go Left 第65次拓展 Open表Board个数：65 最小fn= 1 2 3 4 5 6 0 8 9 10 7 11 13 14 15 12 fn gn hn = 17 11 6 canDown:true Go Down openTable:add canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第66次拓展 Open表Board个数：67 最小fn= 1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12 fn gn hn = 16 12 4 canDown:true Go Down openTable:add canUp:true Go Up canRight:true Go Right openTable:add canLeft:true Go Left openTable:add 第67次拓展 Open表Board个数：69 最小fn= 1 2 3 4 5 6 7 8 9 10 11 0 13 14 15 12 fn gn hn = 15 13 2 canDown:true Go Down openTable:add canUp:true Go Up openTable:add canRight:false canLeft:true Go Left 第68次拓展 Open表Board个数：70 最小fn= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 fn gn hn = 14 14 0 SUCCESS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 fn gn hn = 14 14 0 上一步： 1 2 3 4 5 6 7 8 9 10 11 0 13 14 15 12 fn gn hn = 15 13 2 上一步： 1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12 fn gn hn = 16 12 4 上一步： 1 2 3 4 5 6 0 8 9 10 7 11 13 14 15 12 fn gn hn = 17 11 6 上一步： 1 2 0 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 18 10 8 上一步： 1 0 2 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 19 9 10 上一步： 0 1 2 4 5 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 20 8 12 上一步： 5 1 2 4 0 6 3 8 9 10 7 11 13 14 15 12 fn gn hn = 19 7 12 上一步： 5 1 2 4 9 6 3 8 0 10 7 11 13 14 15 12 fn gn hn = 18 6 12 上一步： 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12 fn gn hn = 17 5 12 上一步： 5 1 2 4 9 6 3 8 13 10 7 11 14 0 15 12 fn gn hn = 16 4 12 上一步： 5 1 2 4 9 6 3 8 13 10 7 11 14 15 0 12 fn gn hn = 15 3 12 上一步： 5 1 2 4 9 6 3 8 13 10 0 11 14 15 7 12 fn gn hn = 16 2 14 上一步： 5 1 2 4 9 6 3 8 13 0 10 11 14 15 7 12 fn gn hn = 17 1 16 上一步： 5 1 2 4 9 6 3 8 13 15 10 11 14 0 7 12 fn gn hn = 12 0 12

【本文地址】

公司简介

联系我们