资源描述:
《人工智能实验报告:搜索策略等》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、人工智能实验报告学院:专业班级:指导老师:学号:姓名:第一次实验:搜索策略1.节点静态图(Node1为起点,Node0为终点)2.DFS搜索策略:当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。搜索结果前四步open表和close表的变化Open表Close表14161,401,4,63.BFS搜索策略:BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个
2、先进先出的队列中。依次对出队的结点进行搜索,直至找到目标节点搜索结果前四步open表和close表的变化Open表Close表1416,21,42,0,31,4,64.Lowestcostfirst搜索策略:类似于BFS,但在搜索结点时,并不按照队列的顺序进行搜索,而选取队列中与起始结点距离最近的结点进行搜索。搜索结果前四步open表和close表的变化Open表Close表1416,21,42,0,31,4,65.bestfirst搜索策略:最佳优先搜索通过扩展最有可能到达目标节点的节点,根据指定的规则,探索一个图。搜索结果前四步open表和close表的变化Open表Close表
3、1416,21,42,0,31,4,66.层次深度优先搜索策略:令k=1,进行k层的深度优先搜索,如果没有找到目标,则k+1,进行k+1层的深度优先搜索,以此类推。搜索结果前四步open表和close表的变化Open表Close表1416,21,42,0,31,4,67.A*算法搜索策略:A*[1] (A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为:f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)
4、条件,关键在于估价函数f(n)的选取:估价值h(n)<=n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行,此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。搜索结果前四步open表和close表的变化Open表Close表1416,21,42,0,31,4,68.修改源代码中的估价函数对于一个启发式算法来说,他的搜索顺序依赖于估价函数的定义,而估价函数中启发函数部分h的定义比较主观,容易对搜索造成比较大的影
5、响。因此,如果我们修改关于八数码问题的源代码,将估价函数中的曼哈顿距离改为欧式距离,结果可能会改变。修改前修改后(将启发函数由曼哈顿距离改为欧氏距离)由上面的2个结果可以看出,当未做修改前,我们的算法可以通过5步搜索得出结果,当把曼哈顿距离改为欧氏距离之后,算法尝试了561次搜索,直到内存不够,也没能得出结果。可见估价函数对于整个搜索的影响力。第二次实验:推理技术1.实验说明产生式系统用来描述若干个不同的以一个基本概念为基础的系统,这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中,论域的知识分为两部分:用事实表示静态知识;用产生式规则表示推理过程和行为。2.实验内容下面
6、以一个具体的动物识别专家系统模型来说明其原理。建立该专家系统的代码:规则库事实库该动物是哺乳动物<-该动物有毛发.该动物是哺乳动物<-该动物有奶.该动物是鸟<-该动物有羽毛.该动物是鸟<-该动物会飞&会下蛋.该动物是食肉动物<-该动物吃肉.该动物是食肉动物<-该动物有犬齿&有爪&眼盯前方.该动物是有蹄类动物<-该动物是哺乳动物&有蹄.该动物是有蹄类动物<-该动物是哺乳动物&是嚼反刍动物.该动物是金钱豹<-该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.该动物是虎<-%会游泳.%--该动物是企鹅%不会飞.%有黑白二色.%该动物是鸟.%--------%--该动物是鸟%该动物会飞.
7、%会下蛋.%----该动物是金钱豹<-该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.%该动物有毛发.%是食肉动物.%是黄褐色.%身上有暗斑点.该动物是哺乳动物&是食肉动物&是黄褐色&身上有黑色条纹.该动物是长颈鹿<-该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.该动物是斑马<-该动物是有蹄类动物&身上有黑色条纹.该动物是鸵鸟<-该动物是鸟&有长脖子&有长腿&不会飞&有黑白二色.该动物是企鹅<-该动物是鸟&会游泳&不会飞&有黑白二色.该动物是信