【人工智能导论】A*算法求解15数码问题 Java
生活随笔
收集整理的這篇文章主要介紹了
【人工智能导论】A*算法求解15数码问题 Java
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
完整源碼 - Eclipse項目文件 - GitHub地址
題目描述
關于本算法
兩個晚上寫完的，不足之處多多指教…
啟發函數的選擇：
一開始選用不在位數碼個數+節點深度作為啟發函數，效果不是很好。
后來改用所有數碼到目標位置的矩形距離+節點深度作為啟發函數，計算出：
- 從初始到達目標狀態深度為14（步），見附錄
- 一共進行了68次拓展
- 最后一次拓展時Open表Board個數為70
題解 - 目錄結構
題解 - 代碼實現 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);// 是否為endif (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 < 4; s++) {Board newBoard = null;if (s == 0) {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 < oldBoard.fn) {// 新的比舊的fn小// 更新指針newBoard.childBoards = oldBoard.childBoards;for (int i = 0; i < newBoard.childBoards.size(); i++) {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 < oldBoard.fn) {newBoard.childBoards = oldBoard.childBoards;for (int i = 0; i < newBoard.childBoards.size(); i++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {label: for (int m = 0; m < Init.SIZE; m++) {for (int n = 0; n < Init.SIZE; n++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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<Board> childBoards=new ArrayList<Board>();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();}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("\n");for (int i = 0; i < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE && isEqual == true; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE && isEqual == true; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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 < Init.SIZE; i++) {for (int j = 0; j < Init.SIZE; j++) {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<Board> tbArr = new ArrayList<Board>();/*** Open表排序*/public void sortItSelf() {Collections.sort(tbArr, new Comparator<Board>() {@Overridepublic int compare(Board b1, Board b2) {// 重寫 Comparator 函數if (b1.fn < b2.fn)//小的排前面return -1;else if (b1.fn > b2.fn)return 1;elsereturn 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 < tbArr.size(); i++) {if (tbArr.get(i).equals(board)) {hasBoard = true;break;}}return hasBoard;}/*** 獲取Board在OpenTable中的索引* @param board* @return 索引值*/public int getIndex(Board board) {int index=-1;for (int i = 0; i < tbArr.size(); i++) {if (tbArr.get(i).equals(board)) {index = i;break;}}return index;}public Board getBoardByArr(int[][] array){for (int i = 0; i < tbArr.size(); i++) {if (tbArr.get(i).equals(array)) {return tbArr.get(i);}}try {throw new Exception("Opentable:不存在該arr!");} catch (Exception e) {e.printStackTrace();}return null;}@Overridepublic String toString() {StringBuilder sb=new StringBuilder();sb.append("\n");sb.append("OpenTable:\n");for(int i=0;i<tbArr.size();i++) {sb.append(tbArr.get(i).toString());sb.append("\n");}return sb.toString();} }CloseTable.java
package cn.hanquan.ai;import java.util.ArrayList;public class CloseTable {ArrayList<Board> tbArr = new ArrayList<Board>();/*** 判斷Table中是否包含某個board* @param board* @return*/public boolean hasBoard(Board board) {boolean hasBoard = false;for (int i = 0; i < tbArr.size(); i++) {if (tbArr.get(i).equals(board)) {hasBoard = true;break;}}return hasBoard;}/*** 獲取Board在CloseTable中的索引* @param board* @return 索引值*/public int getIndex(Board board) {int index=-1;for (int i = 0; i < tbArr.size(); i++) {if (tbArr.get(i).equals(board)) {index = i;break;}}return index;}public Board getBoardByArr(int[][] array){for (int i = 0; i < tbArr.size(); i++) {if (tbArr.get(i).equals(array)) {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 12canDown: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 16canDown: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 14canDown: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 12canDown: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 12canDown: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 10canDown: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 12canDown: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 12canDown: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 16canDown: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 16canDown: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 12canDown: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 12canDown: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 14canDown: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 16canDown: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 16canDown: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 12canDown: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 12canDown: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 16canDown: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 14canDown: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 14canDown: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 16canDown: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 16canDown: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 14canDown: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 12canDown: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 12canDown: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 10canDown: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 12canDown: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 12canDown: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 12canDown: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 12canDown: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 12canDown: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 18canDown: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 18canDown: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 18canDown: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 16canDown: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 14canDown: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 14canDown: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 16canDown: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 14canDown: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 12canDown: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 10canDown: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 16canDown: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 14canDown: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 12canDown: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 10canDown: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 10canDown: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 8canDown: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 8canDown: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 6canDown: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 10canDown: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 8canDown: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 12canDown: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 10canDown: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 8canDown: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 10canDown: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 8canDown: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 16canDown: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 16canDown: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 14canDown: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 14canDown: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 12canDown: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 12canDown: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 10canDown: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 8canDown: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 6canDown: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 4canDown: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 2canDown: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 0SUCCESS: 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總結
以上是生活随笔為你收集整理的【人工智能导论】A*算法求解15数码问题 Java的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【JavaScript】js数组与字符串
- 下一篇： 【Python Flask】SQLAlc