人工智能实验报告.docx

可编辑范本
可编辑范本
人工智能
九宫格重移——搜索
成员：赵春杰2009210665
羊森2009210653
黄鑫2009210
周成兵2009210664
王素娟2009210644
：
八rrayList();//存放答案
HashTale：Hashtabletable=newHashtable()构造哈希表以方便查找sort排序
算法介绍
定能找到它,
算法A不能保证当图中存在从起始节点到目标节点的最短路径时，
而A*中评估函数f*(n尸g*(n)+f*(n)保证路径存在时，一定能找到。算法A中，g(n)和h(n)
是g*(n)和f*(n)的近似估价。如果对于所有节点h(n)<g*(n),则它就称为A*算法：
状态空间表示
状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一
行开始从左往右给九宫格标号0……8,字符串now元素下标代表格子位置，而now数
组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。
搜索树
可编辑范本
可编辑范本
法步骤
算法描述：
把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G;
检查OPEN表是否为空，若为空则问题无解，退出；
把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；
考察节点n是否为目标节点。若是，则求得了问题的解，退出；
扩展节点n,生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M,
并把这些子节点作为节点n的子节点加入G中；
针又M中子节点的不同情况，分别进行如下处理：
对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）
对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中，对g（x）进行更新）
对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继
可编辑范本
可编辑范本
节点指向父节点的指针；(在CLOSE表中,对节点n子节点的子节点更新g(x))
对OPEN表中的节点按估价函数进行排序；
转第2步。
算法流程图
可编辑范本
可编辑范本
可编辑范本
可编辑范本
可编辑范本
.启发式A算法
队列：Queueopen=newQueue()存放待扩展的节点
List：List<Bfstr>closed=newList<Bfstr>();存放已被扩展过的节点
ArrayListmap=newArrayList();//存放答案
可编辑范本
可编辑范本
可编辑范本
HashTale：Hashtabletable=newHashtable()构造哈希表以方便查找sort排序
算法介绍
启发式搜索算法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
值最小的节点来优先扩展。
可编辑范本
可编辑范本
可编辑范本
状态空间表示
状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开
始从左往右给九宫格标号0……8,字符串now元素下标代表格子位置，而now数组中
对应数组的值代表九宫格中存放的数码，用数值9代表空格。
搜索树
D⑸
.算法步骤
可编辑范本
可编辑范本
可编辑范本
建立一个只含初始节点So的搜索图G,把So放入Open表，并计算f(So)的值;
如果Open表是空的，则失败，否则，继续下一步；
从Open表中取出f值为最小的结点，置于Close表，给这个结点编号为n;
如果n是目标结点，则得解，算法成功退出。此解可从目标结点开始到初始节点的
返回指针中得到。否则，继续下一步；
扩展