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

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

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

3、行性分析十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字 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；对于目标状态：1、2、3、4、5、6、7、8、9、10、11、12、13、1

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

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

6、佳代价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.2 A*算法设计（1）根据初始排列生成初始结点s，并判断问题的可解性。若可解则转（2）否则退出。（2）初始化open，closed表，并将初始

7、节点加入open表。（3）从open表中取出第一个节点。（4）若是目标节点则成功退出。（5）把该节点从open表删除，并添加到closed表中。（6）对该节点进行扩展，其生成节点mi分成三种情况，mj，mk，ml。mj：新生成的节点既不在open表中也不在closed表中，直接把生成的节点添加到open表即可。Mk：新生成的节点出现在open表中且新生成节点的f（n）小于open表中该节点的f（n），则更改open表中的f（n）的值。Ml：新生成的节点在closed表中并且新生成节点的f（n）小于closed表中对应节点的f（n）的值，则把该节点从open表中删除，添加到open表中并写该其f

8、值为新生成节点的f值。（7）对open表中的节点按f值从小到大的顺序进行排列。（8）转到（3）。4 实验总结4.1 实验可视化界面 4.2个人体会初学人工智能时，最先联想到的便是机器人，一直感觉机器人是非常智能且神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的想要了解他的内涵。经过三十多个学时的学习，我对人工智能已经有了初步的了解，也深深的被它吸引，尤其通过本次课程设计，对人工智能的学习兴趣更加浓厚了！15数码问题是人工智能的一个经典的问题。本文中通过设计一个基于A*算法的状态空间搜索程序，对于给定的初始状态，采用f(n)=h(n)+g(n)表示以当前节点与其目标节点相应

9、位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用面相对象的编程语言java来实现该问题。在程序的设计与实现过程中，遇到了很多的问题。首先由于初学人工智能，理解上有一定的困难，对A*算法的深入学习是一个曲折的过程。其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验。所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响。 同时通过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列。但对某些稍微复杂的初始状态虽能得到正确解却不能完全

10、得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解。这是有待进一步学习并改进的地方。 但本程序还是有些值得肯定之处。界面设计比较友好，容易操作。而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间。虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。4.3 详细代码：public class 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,

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.out.println("此种方案无解");System.exit(-1);System.out.println("数据的变化情况如下所示：n");Node resultnode = FifteenNum.moveManHa(node);for(int i=1; i<=resultnode

12、.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();System.out.println();System.out.println();System.out.println("第"+i+"步

13、");totalnum = i;Interface f = new Interface();f.P1(resultnode.data,totalnum);resultnode.print();import java.util.ArrayList;import java.util.List;public class Node public static final int N = 4; private int f ; private int h ; private int w ; List<Node> pnodes = new ArrayList<Node>()

14、; FifteenNum.Direction last_Dirction ; 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() retur

15、n last_Dirction;public void setLast_Dirction(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;publi

16、c void print()System.out.println();for(int i=0; i<8; i+)System.out.print("* ");System.out.println();for(int i=0; i<N; i+)System.out.print("* ");for(int j = 0; j<N; j+)if(dataij = 0)System.out.print(" ");else if(dataij < 10)System.out.print(dataij+" &quo

17、t;);elseSystem.out.print(dataij+" ");System.out.println("*");for(int i=0; i<8; i+)System.out.print("* ");System.out.println();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

18、;break;if(!flag) break;return flag;public 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;import java.util.Scanner;public class Data public static int n = Main.N;static Scanner sc = new Scanner(System.in);public

19、 static void inputNum(int num)int k=0;for(int i=0; i<n; i+)for(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

20、= new intn*n-1;for(int i=0; i<n; i+)for(int j = 0; j<n; j+)if(dataij != 0)tempindex = dataij;/System.out.print(tempindex+" ");index+;System.out.println();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

21、 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.standardij)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 =

22、 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 - 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 boole

23、an isDataOk(int a, int b)return sameOdevity(inverseNum(a), inverseNum(b);import java.util.ArrayList;import java.util.List;public class FifteenNum public static int openNum = 0;public static int closedNum = 0;public enum Direction UP,RIGHT,DOWN,LEFT;public static final int n = Main.N;static List<N

24、ode> open = new ArrayList<Node>();static List<Node> closed = new ArrayList<Node>();public static boolean changeTo(Direction direction,int i, int j, int data_temp)int temp;boolean flag = true;switch(direction)case UP: if(i>=1)temp = data_tempij;data_tempij = data_tempi-1j;data

25、_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)temp = data_tempij;data_tempij = data_tempi+1j;data_tempi+1j = temp;elseflag = false;break;case LEFT: if(j>=1)temp = data

26、_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 && d2 = Direction.DOWN | d1=Direction.DOWN && d2 = Direction.UP)return true;else if(d1=Direction.RIGHT &am

27、p;& d2 = Direction.LEFT | d1=Direction.LEFT && d2 = Direction.RIGHT)return true;return false;public static Node moveManHa(Node node1)Direction direction = Direction.UP, Direction.RIGHT, Direction.DOWN, Direction.LEFT;int i = 0;int j = 0;int wrongNum;boolean isOver = false;/设定初始节点的参数node1

28、.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) /定位要扩展节点的空格所在的位置for(int x=0; x<n; x+)for(int y = 0; y<n; y+)if(node.dataxy = 0)i = x;j = y;/System.out.println("空格的坐

29、标="+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(), directiondir_index)continue;Data.arrayCopy(temp, node.data);if(FifteenNum.changeTo(directiondir_index, i,

30、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.setLast_Dirction(directiondir_index);/记录该节点的的移动方向，以便其孩子节点不再与该节点移动的方向相反/* * 把新生成节点的祖先节点放入到新生成节点里 */for

31、(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 node_mk = null;/open表中或closed表中 （与新生成的节点状态一样 ）的节点if(node_mk = node_temp.getSameStateFr

32、om(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(node_ml);open.add(node_temp);openNum+;elseopen.add(node_temp);openNum+;if(Data.manHa(n

33、ode_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;/System.out.println("扩展节点数closednum="+closedNum+"生成节点数produce="+produce);return node;public static void sort(List<Node> list)for(int i=0; i<list.size(); i+ )int k = i;for(int j=i+1; j<list.size(); j+)if(list.get(k).getF()>list.get(j).getF()k = j;if(k !=