人工智能十五数码实验报告

1、目录1实验概述 .22十五数码问题分析 .22.1十五数码问题简介 .22.2可行性分析 .33 问题的求解策略 .33.1算法分析 .33.2A*算法设计 .44实验总结 .54.1实验可视化界面 .54.2个人体会 .64.3详细代码： .71 实验概述十五数码问题来源于美国的科学魔术大师萨姆.洛伊德（ Sam I.oyd）在 1978年推出的著名的“ 14-15”智力玩具。这个游戏曾经风靡欧美大陆" 。洛伊德的发明其实只是将重排九宫（即八数码问题）中的3 阶方阵扩大到 4 阶方阵罢了。由于这个细微的变化， 十五数码问题的规模远远大于八数码问题，八数码问题的规模较小，总的状态数为

2、9！（=362880）个，而十五数码问题的状态,数为 16！（）个。故十五数码问题更能评价一个算法的“智能”水平。2 十五数码问题分析2.1 十五数码问题简介15 数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15 数码问题：就是在一个4×4 的 16 宫格棋盘上，摆放有15 个将牌，每一个将牌都刻有 115 中的某一个数码。 棋盘中留有一个空格， 允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态 )和一个目标布局 (称目标状态 )，问如何移动数码，实现从初始状态到目标状态的转变，如下图

3、所示。问题的实质就是寻找一个合法的动作序列2.2 可行性分析十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字0 不计入其中 , i 是第 i 个数之前比该数小的数字的个数 ,则 =i 是该状态的逆序数 ,例如：对于初始状态： 5、1、2、4、9、6、3、8、13、15、10、11、14、7、12.其 =0+0+1+2+4+4+2+6+8+9+8+9+11+6+11=81；对于目标状态

4、： 1、2、3、4、5、6 、7 、8 、9 、10、11 、12 、13 、14 、15 ，其=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105。初始状态和目标状态的奇偶性相同，故存在解路径。3 问题的求解策略3.1 算法分析十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：一类是盲目搜索， 如深度优先搜索 DFS 和广度优先搜索 BFS；另一类是启发式搜索，如 A* 算法。对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。 应用此策略很可能得不到解。 宽度优先搜索的优势在于

5、当问题有解时， 一定能找到解， 且能找到最优解。 但其搜索时需要保存所有的待扩展结点， 这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸” 。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章， 往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。 其核心思想是引入一个启发式函数 （或称为评估函数）利用评估函数为生成的结点估值 %并按估值的大小对结点进行排序，优先搜索估值小的结点。该评估函数根据问题的启发信息建立，评估了解决问题所需的最小

6、费用，其基本形式是 f(n) = g(n)+h(n)。 其中 g(n)：从初始状态 s 到中间状态 n 的最佳代价 g*(n)的估值，h（n）：从中间状态 n 到目标状态 t 的最佳代价h* （n）的估值，利用评估函数来进行的图搜索算法称为A 算法，若还有h（n）<= h*（n）则称为A* 算法。在八数码问题中，通常g（n）是搜索树中当前结点n 的深度，是从根结点到当前结点 n 的最短路径长度； h（n）的取值则有多种，如错位将牌数、曼哈顿距离。这里主要是 h（n）体现了启发信息， h（n）设计的好坏体现了算法的“智能”水平。本课设借鉴这些算法h（n）采用曼哈顿距离。3.2A*算法设计（

7、1）根据初始排列生成初始结点 s，并判断问题的可解性。 若可解则转（2）否则退出。（2）初始化 open， closed 表，并将初始节点加入open 表。（3）从 open 表中取出第一个节点。（4）若是目标节点则成功退出。（5）把该节点从 open 表删除，并添加到closed 表中。（6）对该节点进行扩展，其生成节点 mi 分成三种情况， mj，mk，ml。mj：新生成的节点既不在 open 表中也不在 closed 表中，直接把生成的节点添加到 open 表即可。 Mk：新生成的节点出现在 open 表中且新生成节点的 f（n）小于 open 表中该节点的 f（n），则更改 open

8、表中的 f（n）的值。 Ml ：新生成的节点在 closed 表中并且新生成节点的 f（ n）小于 closed 表中对应节点的 f（n）的值，则把该节点从 open 表中删除，添加到 open 表中并写该其 f 值为新生成节点的 f值。（7）对 open 表中的节点按 f 值从小到大的顺序进行排列。（8）转到（ 3）。4 实验总结4.1实验可视化界面4.2 个人体会初学人工智能时， 最先联想到的便是机器人， 一直感觉机器人是非常智能且神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱， 非常迫切的想要了解他的内涵。 经过三十多个学时的学习， 我对人工智能已经有了初步的了解，也深深的被

9、它吸引， 尤其通过本次课程设计， 对人工智能的学习兴趣更加浓厚了！15 数码问题是人工智能的一个经典的问题。本文中通过设计一个基于A* 算法的状态空间搜索程序， 对于给定的初始状态， 采用 f(n)=h(n)+g(n)表示以当前节点与其目标节点相应位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用面相对象的编程语言java 来实现该问题。在程序的设计与实现过程中，遇到了很多的问题。首先由于初学人工智能，理解上有一定的困难，对 A* 算法的深入学习是一个曲折的过程。 其次，在程序真正的设计及实现过程中， 的确需要花费大量的精力来思考， 反复试验。所设计的程序能够运行， 但缺陷还是非常之大

10、的，如其中重排 OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置， 这实际上对程序的运行效率有很大的影响。 同时通过输入大量的初始状态和目标状态发现， 在一般情况下都可以找到最优的动作序列。但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态， 甚至得不到解。 这是有待进一步学习并改进的地方。但本程序还是有些值得肯定之处。界面设计比较友好，容易操作。而且在程序开始时， 就判断目标状态是否可达，这样可节约大量的时间。 虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。4.3详细代码：public class

11、Main public static final int N = 4;static int num = 5,1,2,4,9,6,3,8,13,15,10,11,14,0,7,12;static int standard = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0;public static void main(String args)int totalnum = 0;Node node = new Node(num);if(!Data.isDataOk(num, standard)此种方案无解");System.exit(-1);数据的变化情况如下

12、所示：n");Node resultnode = FifteenNum.moveManHa(node);for(int i=1; i<=resultnode.getPnodes().size(); i+)Interface f = new Interface();f.P1(resultnode.getPnodes().get(i-1).data,i-1);try Thread.sleep(2000); catch (InterruptedException e) e.printStackTrace();resultnode.getPnodes().get(i-1).print(

13、);第 "+i+"步");totalnum = i;Interface f = new Interface();f.P1(resultnode.data,totalnum);resultnode.print();public class Node public static final int N = 4;private int f ;private int h ;private int w ;List<Node> pnodes = new ArrayList<Node>();FifteenNum.Direction last_Dircti

14、on ;int data = new intNN;public Node(int data)this.h = 0;this.w = 0;this.f = 0;this.last_Dirction = null;Data.arrayCopy(this.data, data);/pnodes.add(this);public List<Node> getPnodes() return pnodes;public FifteenNum.Direction getLast_Dirction() return last_Dirction;public void setLast_Dirctio

15、n(FifteenNum.Direction lastDirction) last_Dirction = lastDirction;public int getF() return f;public void setF(int f) this.f = f;public int getH() return h;public void setH(int h) this.h = h;public int getW() return w;public void setW(int w) this.w = w;public void print()for(int i=0; i<8; i+)for(i

16、nt i=0; i<N; i+)for(int j = 0; j<N; j+)if(dataij = 0)");else if(dataij < 10)elsefor(int i=0; i<8; i+)public boolean isequal( Node node)boolean flag = true;for(int i=0; i<N; i+)for(int j = 0; j<N; j+)if(dataij != node.dataij)flag = false;break;if(!flag) break;return flag;public

17、 Node getSameStateFrom(List<Node> list)for(int i=0; i<list.size(); i+)if(this.isequal(list.get(i) return list.get(i);return null;public class Data public static int n = Main.N;static Scanner sc = new Scanner(System.in);public static void inputNum(int num)int k=0;for(int i=0; i<n; i+)for(

18、int j = 0; j<n; j+)numij = sc.nextInt();public static void arrayCopy(int a, int b)for(int i=0; i<n; i+)for(int j = 0; j<n; j+)aij = bij;public static int inverseNum(int data)int index = 0;int num = 0;int tempnum = 0;int temp = new intn*n-1;for(int i=0; i<n; i+)for(int j = 0; j<n; j+)i

19、f(dataij != 0)tempindex = dataij;index+;for(int i=0; i<n*n-1; i+)tempnum = 0;for(int j=0; j<i; j+)if(tempj<tempi)tempnum+;num += tempnum;return num;public static int WrongLocationNum(int temp)int count = 0;for(int i=0; i<n; i+)for(int j = 0; j<n; j+)if(tempij != 0)if(tempij != Main.st

20、andardij)count+;return count;public static int manHa(int temp)int d = 0;boolean flag = false;for(int x1=0; x1<n; x1+)for(int y1=0; y1<n; y1+)if(tempx1y1 != 0)flag = false;for(int x2=0; x2<n; x2+)for(int y2=0; y2<n; y2+)if(tempx1y1 = Main.standardx2y2)d += Math.abs(x1 - x2) + Math.abs (y1

21、 - y2);flag = true;if(flag ) break;if(flag ) break;return d;public static boolean sameOdevity(int m, int n)if(m%2 = n%2) return true;else return false;public static boolean isDataOk(int a, int b)return sameOdevity(inverseNum(a), inverseNum(b);public class FifteenNum public static int openNum = 0;pub

22、lic static int closedNum = 0;public enum Direction UP,RIGHT,DOWN,LEFT;public static final int n = Main.N;static List<Node> open = new ArrayList<Node>();static List<Node> closed = new ArrayList<Node>();publicstatic boolean changeTo(Direction direction,int i, int j, int data_te

23、mp) int temp;boolean flag = true;switch(direction)case UP: if(i>=1)temp = data_tempij;data_tempij = data_tempi-1j;data_tempi-1j = temp;elseflag = false;break;case RIGHT: if(j<=2)temp = data_tempij;data_tempij = data_tempij+1;data_tempij+1 = temp;elseflag = false;break;case DOWN: if(i<=2)tem

24、p = data_tempij;data_tempij = data_tempi+1j;data_tempi+1j = temp;elseflag = false;break;case LEFT: if(j>=1)temp = data_tempij;data_tempij = data_tempij-1;data_tempij-1 = temp;elseflag = false;break;return flag;public static boolean oppositeDirection(Direction d1, Direction d2)if(d1=Direction.UP &

25、amp;& d2 = Direction.DOWN | d1=Direction.DOWN && d2 =Direction.UP)return true;else if(d1=Direction.RIGHT && d2 = Direction.LEFT | d1=Direction.LEFT && d2 = Direction.RIGHT)return true;return false;public static Node moveManHa(Node node1)Direction direction = Direction.UP,

26、 Direction.RIGHT, Direction.DOWN, Direction.LEFT;int i = 0;int j = 0;int wrongNum;boolean isOver = false;/ 设定初始节点的参数node1.setH(0);node1.setW(Data.manHa(node1.data);/曼哈顿node1.setF(node1.getW()+node1.getH();Node node = null;open.add(node1);node = open.remove(0);int a =0;while(node.getW() != 0)/ 定位要扩展节

27、点的空格所在的位置for(int x=0; x<n; x+)for(int y = 0; y<n; y+)if(node.dataxy = 0)i = x;j = y;空格的坐标 ="+i+"j="+j);break;int temp = new intnn;/ 对刚才从 open 表中取出的节点试探性的进行四个方向的扩展for(int dir_index = 0; dir_index < 4; dir_index+)if(FifteenNum.oppositeDirection(node.getLast_Dirction(),direction

28、dir_index)continue;Data.arrayCopy(temp, node.data);if(FifteenNum.changeTo(directiondir_index, i, j,temp)wrongNum = Data.manHa(temp);/ 曼哈顿距离Node node_temp = new Node(temp);/由父节点生成新的节点node_temp.setH(node.getH()+1);node_temp.setW(wrongNum);node_temp.setF(node_temp.getH()+node_temp.getW();node_temp.setL

29、ast_Dirction(directiondir_index);/记录该节点的的移动方向，以便其孩子节点不再与该节点移动的方向相反/*/把新生成节点的祖先节点放入到新生成节点里for(int k=0; k<node.getPnodes().size(); k+)node_temp.getPnodes().add(node.getPnodes().get(k);node_temp.getPnodes().add(node);/*判断当前节点n生成的节点mi 属于 mj 、mk、 ml的哪一种判断顺序为：mk->ml->mj*/Node node_ml = null ;Node

30、 node_mk = null;/open表中或 closed 表中（与新生成的节点状态一样 ）的节点if(node_mk = node_temp.getSameStateFrom(open) != null)if(node_temp.getH() > node_mk.getH()open.remove(node_temp);open.add(node_temp);else if(node_ml = node_temp.getSameStateFrom( closed) !=null)if(node_temp.getH() > node_ml.getH()closed.remove

31、(node_ml);open.add(node_temp);openNum+;elseopen.add(node_temp);openNum+;if(Data.manHa(node_temp.data) = 0) / 曼哈顿 isOver = true;node = node_temp;break;else/ 不可达的方向，错位将牌数取为10wrongNum = 10;/for结束if(isOver) break;/如果已经是目标状态退出程序closed.add(node);closedNum+;sort(open);node = open.remove(0);openNum-;/ 把open 表中的第一个节点从open 表中删除，添加到closed表中/while结束int produce = closedNum + openNum;扩展节点数closednum="+closedNum+"生成节点数produce="+produce);return node;public static void sort(List<Node> list)for(int i