人工智能化实验报告

1、 人工智能九宫格重移搜索成员：赵春杰 2009210665羊森 2009210653黄鑫 2009210周成兵 2009210664王素娟 20092106441.问题描述：八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间

2、过渡状态。2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。所以147258369是无解的情况。由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。3.BFS算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new L

3、ist<Bfstr>();存放已被扩展过的节点 ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找3.1BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。3.2状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中

4、，从第一行开始从左往右给九宫格标号08，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。3.3搜索树2 8 31 6 47 512 8 31 6 47 52 8 31 47 6 52 8 31 6 47 52342 8 36 41 7 52 31 8 47 6 52 8 31 6 7 5 42 8 31 47 6 52 8 31 47 6 5567893.4算法步骤 搜索：（1）把初始节点S0放入OPEN表。（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。（4）考察节点n是否为目

5、标节点。若是，则求得了问题的解，退出。（5）若节点n不可扩展，则转第2步。（6）扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。扩展fun()：（1）取open中第一个节点a加入到closed中（2）找到a9中值为9（空格）的位置i；（3）当open中元素个数不为0时，循环执行（3）到（） 3.1从open中取出一个元素（状态），并加入到closed中，对这个状态扩展； 3.2若空格在第2、3列,向左移动得到新状态； 新状态不是目标状态，就加入open中； 新状态是目标状态，就加入closed中，编号加1，结束算法； 3.3若空格在第2、3行,

6、向上移动得到新状态 新状态不是目标状态，就加入open中， 新状态是目标状态，就加入closed中，编号加1，结束算法； 3.4若空格在第1、2列,向右移动得到新状态 新状态不是目标状态，就加入open中， 新状态是目标状态，就加入closed中，编号加1，结束算法； 3.5若空格在第1行,向下移动得到新状态 新状态不是目标状态，就加入open中， 新状态是目标状态，就加入closed中，编号加1，结束算法；3.5算法流程图输入初始状态SS和目标状态NN开始open空?YNn=0,初始节点送入open队列搜索失败，算法结束，从open中取出节点到closed中并编号加1扩展编号为n的节点，加入

7、open中closed中是否有目标节点Y算法结束是否还有后续节点NNY4.启发式A*算法 队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点 ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找sort排序4.1算法介绍算法A不能保证当图中存在从起始节点到目标节点的最短路径时，一定能找到它，而A*中评估函数f*

8、(n)=g*(n)+f*(n)保证路径存在时，一定能找到。算法A中，g(n)和h(n)是g*(n)和f*(n)的近似估价。如果对于所有节点h(n)<g*(n),则它就称为A*算法：4.2.状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号08，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。4.3.搜索树2 8 31 6 47 512 8 31 6 47 52 8 31 47 6 52 8 31 6 47 52342 8 36 41 7 52 31 8 47 6 52

9、8 31 6 7 5 42 8 31 47 6 52 8 31 47 6 557892因为2节点离目标节点更近，调换到3前面4.4.算法步骤算法描述：3.1把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；3.2检查OPEN表是否为空，若为空则问题无解，退出；3.3把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；3.4考察节点n是否为目标节点。若是，则求得了问题的解，退出；3.5扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；3.6针对M中子节点的不同情况，分别进行如下处理：3.6.1对于那些未曾在G

10、中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）3.6.2对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）3.6.3对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中, 对节点n子节点的子节点更新g(x) ）3.7对OPEN表中的节点按估价函数进行排序；3.8转第2步。4.5.算法流程图开始输入初始状态SS和目标状态NNS0加入open表，构造Gopen空？YN失败结束open取首节点放入closed,n号扩展n节点，加入G

11、将不是n为父的子节点记做集合MM中未在G出现过的设置父节点n,放入openM中已G出现过的open表中更新M中已G出现过且扩展的，closed表中更新g(x)OPEN表中的节点按估价函数进行排序5.启发式A算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点 ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查

12、找sort排序5.1算法介绍 启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的形式如下：f（n）g（n）h（n） ; 其中n是被评价的节点。说明：g*(n)：表示从初始节点s到节点n的最短路径的耗散值；h*(n)：表示从节点n到目标节点g的最短路径的耗散值；f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。是一种预测。A算法就是利用这种预

13、测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。5.2.状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号08，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。5.3.搜索树 5.4.算法步骤5.1 建立一个只含初始节点So的搜索图G，把So放入Open表，并计算f（So）的值；5.2 如果Open表是空的，则失败，否则，

14、继续下一步；5.3从Open表中取出f值为最小的结点，置于Close表，给这个结点编号为n；5.4如果n是目标结点，则得解，算法成功退出。此解可从目标结点开始到初始节点的返回指针中得到。否则，继续下一步；5.5扩展结点n。生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；5.6对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表 ；5.7对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）5.8对于那些先前已在G中出现并且已经扩展了的M成员，确

15、定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中, 对节点n子节点的子节点更新g(x) ）5.9按f值从大至小的顺序，对Open表中的结点重新排序；5.10 返回步骤2。5.5算法流程图 开始输入初始状态SS和目标状态NNS0加入open表，构造Gopen空？YN失败结束open取首节点放入closed,n号扩展n节点，加入G将不是n为父的子节点记做集合MM中未在G出现过的设置父节点n,放入openM中已G出现过的open表中更新M中已G出现过且扩展的，closed表中更新g(x)OPEN表中的节点按估价函数进行排序6.随机数生成算法6.1.算法介绍在数据结构、算法分析与设计、科学

16、模拟等方面都需要用到随机数。由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。因此，我们就整数随机数和实数随机数，以及它们的数据值的范围性和是否可重复性，分别对其算法加以分析和设计。1、Microsoft VC+产生随机数的原理：Srand ( )和Rand( )函数。它本质上是利用线性同余法，y=ax+b(mod m)。其中a，b，m都是常数。因此rand的产生决定于x，x被称为Seed。Seed需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是032767（int），即双字节（16位

17、数），若用unsigned int 双字节是65535，四字节是4294967295，一般可以满足要求。根据整数随机数范围性和是否可重复性，可分为：(1)某范围内可重复。(2)某范围内不可重复。(3)枚举可重复。(4)枚举不可重复。所谓范围，是指在两个数n1和n2之间。例如，在100和200之间这个范围，那么，只要产生的整数随机数n满足100n200，都符合要求。所谓枚举，是指有限的、已知的、若干个不连续的整数。例如，34、20、123、5、800这5个整数就是一种枚举数，也就是单独可以一个个确定下来。某范围内可重复在Visual Basic 语言中，有一个随机数函数Rnd。语法：Rnd(nu

18、mber)。参数number 可选，number 的值决定了 Rnd 生成随机数的方式。Rnd 函数返回小于 1 但大于或等于 0 的值。Number类型Rnd 结果小于零每次都相同的数字，并将 number 用作种子。大于零序列中的下一个随机数。等于零最近生成的数字。未提供序列中的下一个随机数。  在调用 Rnd 之前，先使用无参数的 Randomize 语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子。若要生成某给定范围内的随机整数，可使用以下公式：Int(upperbound - lowerbound + 1) * Rnd + lowerbound)这里，upper

19、bound 是此范围的上限，而 lowerbound 是范围的下限6.2.程序流程图：开始给定范围上限： lowerbound下限：upperbound生成随机数：Random Int(upperboundlowerbound+1)%Rnd+lowerbound结束7.DFS黄鑫负责部分（请注意与上面的格式搭配一下）8.效果图滑块问题求解系统（1）DFS时当显示只需2、3步时，搜索空间爆栈，内存溢出，失败。暂时解决办法：重新生成结束状态或者初始状态（2）BFS、A、A*时显示32步时，搜索空间太多，内存溢出，失败。暂时解决办法：重新生成结束状态或者初始状态（3）不能同时生成结束状态图和初始状态

20、图。暂时解决办法：分步生成结束状态或者初始状态（4）未完成工作：1、时间显示2、自动演示8.1初始界面：8.3.BFS效果图：8.3.启发式*效果图：8.4启发式A效果图：8.5.DFS效果图：9.代码共包括3个工程文件：Common RAND YYSEN工程文件名类名功能代码行数Common Ase.cs实现A算法约350行Common Astr.csA算法的解空间27Common Bfs.cs实现广度优先算法220Common Bfstr.cs广度优先算法的解空间15Common Bse.cs实现A*算法35Common common.cs公用方法72Common Dfs.cs实现深度优先

21、算法250Common Dfstr.cs深度优先算法解空间15RANDRandNum.cs生成随机地图55YYYSENForm1.csWindows功能实现290YYYSENForm1.Designer.csWindows界面设计660YYYSENProgram.csWindows界面入口211、class Ase实现启发式A算法using System;using System.Collections.Generic;using System.Text;using System.Collections;/约350行namespace Common public class Ase priva

22、te int SS=new int9; private int NN=new int9; private string S; private string N; public bool BOOL;/是否有解； List<Astr> open=new List<Astr>() ;/未搜索； List<Astr> closed = new List<Astr>();/已搜索； Hashtable table = new Hashtable(); public ArrayList map=new ArrayList(); public Ase(int

23、SS,int NN) SS.CopyTo(this.SS ,0); NN.CopyTo(this.NN, 0); S = common.changestring(SS); N = common.changestring(NN); BOOL = common.check(this.SS, this.NN, this.SS.Length); public void search() /呵呵，调用其他的搜索，不解释 Bfs ansbfs = new Bfs(this.SS, this.NN); ansbfs.search(); map = ansbfs.map; return; if (S != N

24、) Astr node = new Astr(); node.now = S; node.qian = "" node.gn = 0; node.wn = fwn(S, N); node.fn = node.gn + node.wn; open.Add(node); table.Add(node.now, node.gn); fun(); /构造最佳答案； int i = 0; Astr p=closed closed .Count -1; closed.Remove(p); map.Add(p.now); while (p.now != S) for (i = 0; i

25、< closed.Count; i+) if (closedi.now = p.qian) map.Add(closedi.now); p = closedi; closed.Remove(p); break; /交换 int j = 0; for (i = 0, j = map.Count - 1; i < j; i+, j-) string sss = mapi as string; mapi = mapj; mapj = sss; /交换值 private void swap(int a, int x, int y) int t; t = ax; ax = ay; ay =

26、t; private int fwn(string s1, string s2) int i; int sum=0; for (i = 0; i < s1.Length; i+) if (s1i != s2i) sum+; return sum; / private void fun() Astr node_1 = new Astr(); Astr node_2 = new Astr(); /Astr node_3 = new Astr(); int a = new int9; int b = new int9; string s; int count = 0; while (true&

27、amp;&open.Count !=0) if (count+ > 10000) return; /找最小元素 /list.Sort(x, y) => y.Age - x.Age);排序 int i = 0; /去open中的fn最小值 node_1 = openi; for (i = 0; i < open.Count; i+) if (node_1.fn >= openi.fn) node_1 = openi; open.Remove (node_1); closed.Add(node_1); if(node_1.now =N) return ; a = c

28、ommon.changeint(node_1.now); for (i = 0; i < a.Length; i+) if (ai = 9) break; int index = i; if (i % 3 != 0) a.CopyTo(b, 0); swap(b, i, i - 1); s = common.changestring(b); node_2.now =s; node_2.qian=node_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,N); node_2.fn =node_2.gn+node_2.wn ; int j=0;

29、for (j = 0; j < open.Count; j+) if (openj.now = node_2.now) if (openj.gn > node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k < closed.Count; k+) if (closed k.now = node_2.now) if (closed k.gn > node_2.gn) closed.RemoveAt(k); closed.Ad

30、d(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count) if(k = closed .Count) open.Add(node_2); table.Add(node_2.now, node_2.gn); if (i -3>= 0) a.CopyTo(b, 0); swap(b, i, i - 3); s = common.changestring(b); node_2.now =s; node_2.qian=node_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,

31、N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j < open.Count; j+) if (openj.now = node_2.now) if (openj.gn > node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k < closed.Count; k+) if (closed k.now = node_2.now) if (closed k.gn

32、 > node_2.gn) closed.RemoveAt(k); closed.Add(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count&&k=closed .Count ) open.Add(node_2); table.Add(node_2.now, node_2.gn); if (i % 3 != 2) a.CopyTo(b, 0); swap(b, i, i + 1); s = common.changestring(b); node_2.now =s; node_2.qian=nod

33、e_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j < open.Count; j+) if (openj.now = node_2.now) if (openj.gn > node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k < closed.Count; k

34、+) if (closed k.now = node_2.now) if (closed k.gn > node_2.gn) closed.RemoveAt(k); closed.Add(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count&&k=closed .Count ) open.Add(node_2); table.Add(node_2.now, node_2.gn); if (i + 3 < 9) a.CopyTo(b, 0); swap(b, i, i +3 ); s = common.changestring(b); node_2.now =s; node_2.qian=node_1.now; node_2.gn=node