人工智能实验二

《人工智能实验二》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、人工智能实验报告姓名：潘凯学号:E11314127班级：科技一班学号：E11314127考生姓名：潘凯一、实验目的：掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。二、实验原理：用3*3数组表示八数码棋盘，用0表示空的位置，1-8表示八个数码。棋盘中数码的美中排列顺序为一个状态节点。用A*算法从初始节点进行求解。三、算法和数据结构：A*算法的基本运算过程如下：1）建立一个队列，计算初始结点的估价函数f,并将初始结点入队，设置队列头和尾指针。2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则

2、对结点进行扩展。3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针Z前），则将它抛弃;若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。4）如果扩展出的新结点-与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。5）如果队列头的结点述可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。本实验中估价函数h（x）为目标节点和该节点中1-8号数码所在位置的欧式距离和

3、。数据机构：//Closed表intnumber;typedefstruetClosed{〃节点编号inta[3][3]:inthx:intgx;intS:structClosed*next;}Closed,*closed;//Open表typedefstructOPEN{inta[3][3];inthx:intgx;intS;structOPEN*next;//节点实况//估价函数估价值//已付出代价//父节点编号〃节点实况//估价函数估价值//已付出代价//父节点编号}OPEN,*open;四、运行结果截图:所以节点是倒序输岀:6123选择功冃日阿共需4步达到目

4、标节点T点4：203184765节点3：023184765节点2：123084?65••C:U$er$pankaiDesktopDebugVV8RS.exe*陰赞坯瞰氢二9,其中除示空格:28304765输入目标状态-9,其中0表示空格:23804*亍昭出时是从目标节点往上溯源,