人工智能实验报告-八数码问题(共12页).doc

《人工智能实验报告-八数码问题(共12页).doc》由会员分享，可在线阅读，更多相关《人工智能实验报告-八数码问题(共12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验一 启发式搜索算法姓名：尹鹏飞 学号：S 日期：2014/10/22一、实验目的：熟练掌握启发式搜索算法及其可采纳性。二、实验内容：使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题算法，采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。本实验采用+ 作为启发式函数.三、实验原理：1. 问题描述：八数码问题也称为九宫问题。在33的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求

2、解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2. 原理描述：2.1 有序搜索算法：（1）原理：在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。在本例中，估价函数中的取错放的棋子个数，为节点n的状态与目标状态之间错放的个数，即函数。（2）算法描述： 把起始节点S放到OPEN表中，并计算节点S的； 如果OPEN是空表

3、，则失败退出，无解； 从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点； 把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； 如果是个目标节点，则成功退出，求得一个解； 扩展节点，生成其全部后继节点。对于的每一个后继节点：计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则(I)

4、以此新值取代旧值。(II)从指向，而不是指向他的父节点。(III)如果节点在CLOSED表中，则把它移回OPEN表中。 转向，即GOTO。（3） 算法流程图：2.2启发式搜索技术（1）原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2）估价函数计算一个节点的估价函数，可以分成两个部分：1、 已经付出的代价（起始节点到当前节点）；2、 将要付出的代价（当前节点到目标节点）。节点n的估价函数定义为从初始节点、经过n、

5、到达目标节点的路径的最小代价的估计值，即 = + 。是从初始节点到达当前节点n的实际代价； 是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。（3） 算法描述：参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。四、 实验程序及其说明： 程序开发语言采

6、用C#和面向对象的设计思想,设计的类内容如下:类视图SplashForm用来显示启动界面;MainForm 用来显示数据设置界面;ShowForm 用来显示结果界面;Number用来记录每个节点当前的状态和权值;属性: private int num;/保存当前输入的八数码状态 private int w, p;/分别记录当前的八数码搜索深度和不在位棋子数private Number next;/指向下一个节点 private Number parent;/指向父节点 private int index;/定义当前0所在的位置方法: /复写父类比较方法 public override bool

7、 Equals(Object num)/两个对象的比较方法 public bool CompareLow(Number num)NumberUtil类,工具类,对八数码的各种状态进行控制管理private Queue numQueue;/八数码队列,保存open表 private int soure;/初始状态private int target;/目标状态private Number result;/结果集方法:public bool Control(Number num)/控制策略public bool Calculate() /计算结果Queue 用来作为程序的open表,扩展节点pri

8、vate Number head;/定义队列的头 private ArrayList listClose;/close表保存所有出现的状态表 /添加新的元素,并按照A*算法的计算值递增排序 public void addNumber(Number num)/出队一个元素 public Number equeue()五、 实验小结通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数来说，它的定义趋向多元化，只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问

9、题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。通过实验结果来看，这两个函数都是可采纳的，尽管存在不必要的扩展。六、 实验代码及输出结果1. 源代码：class Queue private Number head;/定义队列的头 private ArrayList listClose;/close表保存所有出现的状态表 public Queue() listC

10、lose = new ArrayList(); head = new Number(); head.Next = null; internal Number Head get return head; set head = value; private int count = 0;/队列中的元素 public int Count get return count; set count = value; public void show() Number n = head.Next; while(n!=null) Console.WriteLine(n.ToString(); n = n.Nex

11、t; /添加新的元素,并按照A*算法的计算值递增排序 public void addNumber(Number num) /如果该状态已出现则不再加入其中 if(listClose.IndexOf(num)=0) Console.WriteLine(listClose.IndexOf(num)+-); return; listClose.Add(num); Number n = head.Next;/获取头元素 Number front = head;/前节点 if (n = null) head.Next = num; else for (;n!=null;n=n.Next)/遍历所有元素

12、/采用头插法将数据插入后面 if(num.CompareLow(n)/如果num比当前对象小,则直接插入前面 num.Next = n; front.Next = num;/插入成功 count+;/增加当前的节点数目 return; front = n; front.Next = num;/直接插入尾部 count+;/增加当前的节点数目 /出队列 public Number equeue() if(count =0) return null; Number n = head.Next; head.Next = head.Next.Next; count-; return n; using

13、System;using System.Collections.Generic;using System.Linq;using System.Text;namespace AICode class NumberUtil private Queue numQueue;/八数码队列,保存open表 private int soure;/初始状态 public int Soure get return soure; set soure = value; private int target;/目标状态 public int Target get return target; set target =

14、 value; private Number result;/结果集 internal Number Result get return result; set result = value; private int index;/当前的0所在数组中的下标 public int Index get return index; set index = value; public NumberUtil() numQueue = new Queue();/ /获取结果栈对象 public Stack getResult() Stack s = new Stack(); if (result != n

15、ull) for (Number n = result; n != null; n = n.Parent) s.Push(n); return s; /对A,B两个数组进行比较 public bool compareArray(int a,int b) for (int i = 0; i = 8;i+ ) if (ai != bi) return false; return true; /A*算法策略 public void A(Number n,int t) int countP = 0; for (int i = 0; i=8;i+ ) int temp = n.Numi; if (n.N

16、umi != ti) for (int j = 0; j 0) /从队首出对一个元素 Number num = numQueue.equeue(); if (!Control(num) return true; ; / numQueue.show(); / Console.WriteLine(=); MAXCount+; if (MAXCount10000) return false; return false; public bool Control(Number num)/控制策略 /开始利用A*算法进行结果的搜索 int index = num.Index;/获取当前0所在的数组位置 i

17、nt row, col; /行和列 col = index % 3;/表示在二维数组中的行数 row = index / 3;/表示二维数组中的列 /每个八数码有四种空间状态 /(1) if(row-1=0) Number n = new Number(); /获取数组的副本 int s =(int)num.Num.Clone(); int i=(row-1)*3+col; int temp = si; si = sindex; sindex = temp; /设置对象的值 n.D = num.D+1; n.Num = s; n.Index = i; n.Parent = num;/添加对象的

18、父节点 A(n, target);/计算权值 /将对象添加到队列中,如果找到对象了,则返回 if (compareArray(n.Num,target) this.result = n; return false; numQueue.addNumber(n); if(row+1=0) Number n = new Number(); /获取数组的副本 int s = (int)num.Num.Clone(); int i = row * 3 + col-1; int temp = si; si = sindex; sindex = temp; /设置对象的值 n.D = num.D + 1;

19、n.Num = s; n.Index = i; n.Parent = num;/添加对象的父节点 A(n, target);/计算权值 /将对象添加到队列中 if (compareArray(n.Num, target) this.result = n; return false; numQueue.addNumber(n); if(col+1=2) Number n = new Number(); /获取数组的副本 int s = (int)num.Num.Clone(); int i = row * 3 + col +1; int temp = si; si = sindex; sindex = temp; /设置对象的值 n.D = num.D + 1; n.Num = s; n.Index = i; n.Parent = num;/添加对象的父节点 A(n, target);/计算权值 /将对象添加到队列中 if (compareArray(n.Num, target) this.result = n; return false; numQueue.addNumber(n); return true; 2. 输出结果：专心-专注-专业