文档介绍：人工智能各算法实验分析及指导撰写时间: 2012 年6月 15日实验一 A* 算法实验一、实验目的: 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用 A* 算法求解 N数码难题,理解求解流程和搜索顺序。二、实验原理: A* 算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择 f值最小的节点作为扩展节点。因此, f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点 n的估价函数值为两个分量:从起始节点到节点 n的代价以及从节点 n到达目标节点的代价。三、实验环境: Windows 操作系统, C语言或 Prolog 语言。四、实验内容: 8数码和 15 数码为例实际求解 A* 算法。 2 .画出 A* 算法求解框图。 3 .分析估价函数对搜索算法的影响。 A* 算法的特点。六、实验报告要求: 1 A* 算法流程图和算法框图。 2试分析估价函数的值对搜索算法速度的影响。 3根据 A* 算法分析启发式搜索的特点。提交程序清单。 1 知识点归纳搜索策略的知识点主要可以分为六块内容来进行讲解: ?搜索的基本概念?状态空间的盲目搜索?状态空间的启发式搜索?与/或树的盲目搜索?与/或树的启发式搜索?博弈树的启发式搜索?α-β剪枝技术很多问题都可以用到人工智能中的搜索策略来进行问题求解,比如迷宫问题、博弈问题、 8皇后问题、旅行商问题、排课问题、背包问题等等。对于本实验所要求解的 8数码问题,需要掌握的知识点主要有几下这些: ?一般图搜索算法流程?广度优先和深度优先搜索?代价树搜索?启发信息和评估函数?A算法?A*算法 2 算法流程 1)初始化 Open 表和 Closed 表。 2)把图搜索初始化节点放入 Open 表中。 3) Open 若非空,取出表头的节点 x。 4)若x就是目标节点,返回搜索成功。 5)将该节点 x从 Open 表中删除并放入 Closed 表中。 6)根据图信息产生 x的孩子节点 y 1、y 2、…… y n。 7)标记 x为y i的父节点。 8)若y i从未在 Open 表和 Closed 表中出现过, 根据评估函数计算 y i的评估值并放入 Open 表中。 9)若y i在 Open 表中出现过且当前 y i 的评估值较小,更新 Open 表中该节点的评估值并重置该节点的父节点为 x。 10) 若y i在 Closed 表中出现过且当前 y i 的评估值较小,更新 Closed 表中该节点的评估值并重置该节点的父节点未 x,同时将其从 Closed 表中删除并重新移入 Open 表。 11) 若x还有子节点 y i+1,重复循环 8、9、 10三个步骤。 12) 若x没有子节点了,将 Open 表中已有的节点根据相应的搜索策略进行排序, 然后回到步骤 3。 13) 若 Open 表已空,也没有搜索成功,则返回搜索失败,不存在该路径。 3 算法伪代码 A* 算法搜索过程中设置两个表: Open 和Closed 。Open 表保存了所有已生成而未考察的节点, Closed 表中记录已访问过的节点。算法中有一步是根据估价函数重排 Open 表。这样循环中的每一步只考虑 Open 表中状态最好的节点。 4 算法分析 1) 对于步骤 1,Open 表和 Closed 表只是数据结构上的一种形式,至于在写代码时到底是使用栈式存储结构还是队列式存储结构没有严格要求,需要根据具体问题具体分析用哪一种数据结构,最好是能够选择算法效率更高的。 2) 对于步骤 2 ,一般而言,这里的初始节点代表的是一个状态,也就是说,需要根据实际问题来设计一种能表示任何一种确定状态的类,而该节点显然就是该类的一个实例或对象,将该节点放入 Open 表中,需要 Open 表能够设计的足够空间用来存放许许多多这样的实例,因为在状态空间搜索的过程中, 状态经常是以几何数量级增长的。 3)对于步骤 3,在写代码的过程中,取出表头的节点 x可以有很多种方式实现, 未必一定要从该数据结构的头部进行取节点的操作,因为如何从 Open 表中取节点是关系到算法搜索效率的关键,显然,我们都希望从 Open 表中众多的节点中选取到最有希望通向目标节点的过渡节点来,当然直接选出目标节点是最好的(虽然几乎是做不到的)。 4)对选出的状态节点进行是否是目标节点的判断,显然需要一个高效的判断方式,针对不同问题状态空间中的每一状态,也许会有截然不同的状态比较方式,对于 8数码问题,可以通过逐个比较每一位置的数码来进行是否是目标状态的判断,但效率显然不高,后面会介绍一种更加高效的方式,它是设计一种哈希函数,使得根据这种函数能计算出一个哈希码来唯一确定整个状态空间中任何一个状态,这样就能做到比较一个问题