• / 78
  • 下载费用:17 金币  

人工智能项目实验情况报告.doc

关 键 词:
人工智能 项目 实验 情况 报告
资源描述:
-_人工智能九宫格重移——搜索成员:赵春杰 2009210665羊森 2009210653黄鑫 2009210周成兵 2009210664王素娟 20092106441.问题描述:八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后,状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.九宫重移有无答案检查(逆序数)我们把每个9宫格横向展开,如第一个123456789,我们把左边数大于右边数的组数称为这个九宫格的逆序数,显然123456789的逆序数为0;考虑横向平移,那么逆序数的增量为2或0或-2;纵向平移,逆序数的增量为4或0或-4;但147258369的逆序数为奇数。所以147258369是无解的情况。由此也可以类推当将9宫格展开后,如果数据序列的逆序数为奇数,则此数据序列对应的九宫格是无解的。3.BFS算法队列: Queue open = new Queue();存放待扩展的节点List: List closed = new List();存放已被扩展过的节点 ArrayList map = new ArrayList();//存放答案HashTale: Hashtable table = new Hashtable();构造哈希表以方便查找3.1.BFS算法介绍广度优先搜索算法BFS基本思想:从图中某顶点v出发,逐层对节点进行拓展,并考察是否为目标节点,在第n层节点没有全部扩展并考察前,不对第n+1层节点进行扩展。对九宫重排问题,即构造广度优先搜索树,从初始状态,利用广度优先搜索算法逐步找到目标状态的节点。3.2.状态空间表示状态空间用一维数组表示,每个节点存放在Bfstr结构体中的字符now中,从第一行开始从左往右给九宫格标号0……8,字符串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)若节点n不可扩展,则转第2步。(6)扩展节点n,将其子节点放入OPEN表的尾部,并为每一个子节点都配置指向父节点的指针,然后转第2步。扩展fun():(1)取open中第一个节点a加入到closed中(2)找到a[9]中值为9(空格)的位置i;(3)当open中元素个数不为0时,循环执行(3)到() 3.1从open中取出一个元素(状态),并加入到closed中,对这个状态扩展; 3.2若空格在第2、3列,向左移动得到新状态; 新状态不是目标状态,就加入open中; 新状态是目标状态,就加入closed中,编号加1,结束算法; 3.3若空格在第2、3行,向上移动得到新状态 新状态不是目标状态,就加入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的节点,加入open中closed中是否有目标节点Y算法结束是否还有后续节点NNY4.启发式A*算法 队列: Queue open = new Queue();存放待扩展的节点List: List closed = new List();存放已被扩展过的节点 ArrayList map = new ArrayList();//存放答案HashTale: Hashtable table = new Hashtable();构造哈希表以方便查找sort排序4.1.算法介绍算法A不能保证当图中存在从起始节点到目标节点的最短路径时,一定能找到它,而A*中评估函数f*(n)=g*(n)+f*(n)保证路径存在时,一定能找到。算法A中,g(n)和h(n)是g*(n)和f*(n)的近似估价。如果对于所有节点h(n) closed = new List();存放已被扩展过的节点 ArrayList map = new ArrayList();//存放答案HashTale: Hashtable table = new Hashtable();构造哈希表以方便查找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算法就是利用这种预测,来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序,f值小的节点放在前面,而f值大的节点则被放在OPEN表的后面,这样每次扩展节点时,都是选择当前f值最小的节点来优先扩展。5.2.状态空间表示状态空间用一维数组表示,每个节点存放在Bfstr结构体中的字符now中,从第一行开始从左往右给九宫格标号0……8,字符串now元素下标代表格子位置,而now数组中对应数组的值代表九宫格中存放的数码,用数值9代表空格。5.3.搜索树 5.4.算法步骤5.1 建立一个只含初始节点So的搜索图G,把So放入Open表,并计算f(So)的值;5.2 如果Open表是空的,则失败,否则,继续下一步;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成员,确定是否需要修改其后继节点指向父节点的指针;(在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.算法介绍在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数。由于在数学上,整数是离散型的,实数是连续型的,而在某一具体的工程技术应用中,可能还有数据值的范围性和是否可重复性的要求。因此,我们就整数随机数和实数随机数,以及它们的数据值的范围性和是否可重复性,分别对其算法加以分析和设计。1、Microsoft VC++产生随机数的原理:Srand ( )和Rand( )函数。它本质上是利用线性同余法,y=ax+b(mod m)。其中a,b,m都是常数。因此rand的产生决定于x,x被称为Seed。Seed需要程序中设定,一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小,取值范围是0—32767(int),即双字节(16位数),若用unsigned int 双字节是65535,四字节是4294967295,一般可以满足要求。根据整数随机数范围性和是否可重复性,可分为:(1)某范围内可重复。(2)某范围内不可重复。(3)枚举可重复。(4)枚举不可重复。所谓范围,是指在两个数n1和n2之间。例如,在100和200之间这个范围,那么,只要产生的整数随机数n满足100≤n≤200,都符合要求。所谓枚举,是指有限的、已知的、若干个不连续的整数。例如,34、20、123、5、800这5个整数就是一种枚举数,也就是单独可以一个个确定下来。某范围内可重复在Visual Basic 语言中,有一个随机数函数Rnd。语法:Rnd[(number)]。参数number 可选,number 的值决定了 Rnd 生成随机数的方式。Rnd 函数返回小于 1 但大于或等于 0 的值。Number类型Rnd 结果小于零每次都相同的数字,并将 number 用作种子。大于零序列中的下一个随机数。等于零最近生成的数字。未提供序列中的下一个随机数。  在调用 Rnd 之前,先使用无参数的 Randomize 语句初始化随机数生成器,该生成器具有一个基于系统计时器的种子。若要生成某给定范围内的随机整数,可使用以下公式:Int((upperbound - lowerbound + 1) * Rnd + lowerbound)这里,upperbound 是此范围的上限,而 lowerbound 是范围的下限6.2.程序流程图:开始给定范围上限: lowerbound下限:upperbound生成随机数:Random — Int((upperbound—lowerbound+1)%Rnd+lowerbound结束7.DFS黄鑫负责部分(请注意与上面的格式搭配一下)8.效果图滑块问题求解系统(1)DFS时当显示只需2、3步时,搜索空间爆栈,内存溢出,失败。暂时解决办法:重新生成结束状态或者初始状态(2)BFS、A、A*时显示32步时,搜索空间太多,内存溢出,失败。暂时解决办法:重新生成结束状态或者初始状态(3)不能同时生成结束状态图和初始状态图。暂时解决办法:分步生成结束状态或者初始状态(4)未完成工作:1、时间显示2、自动演示8.1初始界面:8.3.BFS效果图:8.3.启发式A*效果图: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实现深度优先算法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 { private int[] SS=new int[9]; private int[] NN=new int[9]; private string S; private string N; public bool BOOL;//是否有解; List open=new List() ;//未搜索; List closed = new List();//已搜索; Hashtable table = new Hashtable(); public ArrayList map=new ArrayList(); public Ase(int []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) { 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 < closed.Count; i++) { if (closed[i].now == p.qian) { map.Add(closed[i].now); p = closed[i]; closed.Remove(p); break; } } } //交换 int j = 0; for (i = 0, j = map.Count - 1; i < j; i++, j--) { string sss = map[i] as string; map[i] = map[j]; map[j] = sss; } } //交换值 private void swap(int[] a, int x, int y) { int t; t = a[x]; a[x] = a[y]; a[y] = t; } private int fwn(string s1, string s2) { int i; int sum=0; for (i = 0; i < s1.Length; i++) { if (s1[i] != s2[i]) sum++; } return sum; } // private void fun() { Astr node_1 = new Astr(); Astr node_2 = new Astr(); //Astr node_3 = new Astr(); int[] a = new int[9]; int[] b = new int[9]; string s; int count = 0; while (true&&open.Count !=0) { if (count++ > 10000) return; //找最小元素 //list.Sort((x, y) => y.Age - x.Age);排序 int i = 0; //去open中的fn最小值 node_1 = open[i]; for (i = 0; i < open.Count; i++) { if (node_1.fn >= open[i].fn) { node_1 = open[i]; } } open.Remove (node_1); closed.Add(node_1); if(node_1.now ==N) return ; a = common.changeint(node_1.now); for (i = 0; i < a.Length; i++) { if (a[i] == 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; for (j = 0; j < open.Count; j++) { if (open[j].now == node_2.now) { if (open[j].gn > node_2.gn) { open.RemoveAt(j); open.Add(node_2); table[node_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.Add(node_2); table[node_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,N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j < open.Count; j++) { if (open[j].now == node_2.now) { if (open[j].gn > node_2.gn) { open.RemoveAt(j); open.Add(node_2); table[node_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.Add(node_2); table[node_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=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; for (j = 0; j < open.Count; j++) { if (open[j].now == node_2.now) { if (open[j].gn > node_2.gn) { open.RemoveAt(j); open.Add(node_2); table[node_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.Add(node_2); table[node_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_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 (open[j].now == node_2.now) { if (open[j].gn > node_2.gn) { open.RemoveAt(j); open.Add(node_2); table[node_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.Add(node_2); table[node_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); } } } } }}2 class Astr 主要是启发式搜索算法A算法的解空间 using System;using System.Collections.Generic;using System.Text;//27namespace Common{ struct Astr { public string now { get; set; } /// /// 从起始点到n的路径长度 /// public int gn { get; set; } /// /// 代表节点n的格局与目标节点的格局相比文职不符的数目 /// public int wn { get; set; } /// /// fn=gn+wn; /// public int fn { get; set; } /// /// 前一个的状态; /// public string qian { get; set; } }}3、BFS主要是完成广度优先搜索功能using System;using System.Collections.Generic;using System.Text;using System.Collections;//220namespace Common{ public class Bfs { private int[] SS = new int[9]; private int[] NN = new int[9]; private string S; private string N; public bool BOOL;//是否有解; Hashtable table = new Hashtable(); Queue open = new Queue(); List closed = new List(); public ArrayList map = new ArrayList(); public Bfs(int[] 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); } private void swap(int[] a, int x, int y) { int t; t = a[x]; a[x] = a[y]; a[y] = t; } public void search() { if (S != N) { Bfstr node = new Bfstr(); node.now = S; node.qian = ""; node.tol = 0; open.Enqueue(node); table.Add(S, 0); fun(); } else { Bfstr node = new Bfstr(); node.now = S; node.qian = ""; node.tol = 0; closed.Add(node); } int i = 0; //在closed中去寻找答案 Bfstr p = new Bfstr (); p = closed[closed.Count - 1]; closed.Remove(p); map.Add(p.now); while (p.now != S) { for (i = 0; i < closed.Count; i++) { if (closed[i].now == p.qian) { map.Add(closed[i].now); p = closed[i]; closed.Remove(p); break; } } } int j=0; for (i = 0, j = map.Count - 1; i < j; i++, j--) { string sss = map[i] as string ; map[i] = map[j]; map[j] = sss; } } private void fun() { Bfstr node_0 = new Bfstr(); Bfstr node_1 = new Bfstr(); int[] a = new int[9]; int[] b = new int[9]; string s; while (open.Count != 0) { //取open 中的第一个节点; node_0 = (Bfstr)(open.Dequeue()); closed.Add(node_0); // a = common.changeint(node_0.now); int i=0; for (i = 0; i < a.Length; i++) { if (a[i] == 9) break; } int index = i; if (index % 3 != 0) { a.CopyTo(b, 0); swap(b, i, i - 1); s = common.changestring(b); if (s != N) { if (!table.Contains(s)) { node_1.now = s; node_1.qian = node_0.now; node_1.tol = node_0.tol + 1; open.Enqueue(node_1); table.Add(s, node_1.tol); } } else { node_1.now = s; node_1.qian = node_0.now; node_1.tol = node_0.tol + 1; table.Add(s, node_1.tol); closed.Add(node_1); break; } } if (i - 3 >= 0) { a.CopyTo(b, 0); swap(b, i, i - 3); s = common.changestring(b); if (s != N) { if (!table.Contains(s)) { node_1.now = s; node_1.qian = node_0.now; node_1.tol = node_0.tol + 1; open.Enqueue(node_1); table.Add(s, node_1.tol); } } else { node_1.now = s; node_1.qian = node_0.now; node_1.tol = node_0.tol + 1; table.Add(s, node_1.tol); closed.Add(node_1); break; } } if (i %3!=2) { a.CopyTo(b, 0);
展开阅读全文
  语墨文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:人工智能项目实验情况报告.doc
链接地址:http://www.wenku38.com/p-120970.html

                                            站长QQ:1002732220      手机号:18710392703    


                                                          copyright@ 2008-2020 语墨网站版权所有

                                                             经营许可证编号:蜀ICP备18034126号

网站客服微信
收起
展开