人工智能实验 a搜索n数码

《人工智能实验 a搜索n数码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能实验报告题目：用A*搜索求解n数码问题姓名：班级：学号：学院：计算机科学与信息专业：计算机科学与技术指导教师：日期：2011年12月6日23一、实验目的：熟悉和掌握深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解8数码难题，理解求解流程和搜索顺序。二、实验原理：1、A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可

2、考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。2、深度优先搜索(breadth-firstsearch)的定义：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。3、宽度优先搜索(breadth-firstsearch)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这

3、种搜索就叫做宽度优先搜索(breadth-firstsearch).三、实验内容：①　以8数码为例实际求解A*算法。②　画出A*算法求解框图。③　分析估价函数对搜索算法的影响。④　分析A*算法的特点。⑤　宽度求8数码⑥　深度求8数码四、实验描述及要求：4.1维护搜索图的A*算法（1）创建一个搜索图G，只包含开始节点n0。把n0放到OPEN表中。（2）创建CLOSED表：初始为空。（3）如果OPEN表空，算法以失败退出。（4）选OPEN表中的首节点，从OPEN表中移走，放到CLOSED表中。称该节点

4、为n。（5）如果n是目标节点，算法以成功退出：通过跟踪沿着图G中从n指向n0的指针获得解。（6）扩展节点n，产生后继集合M，M不包含图G中n的祖先。把M的成员作为n的后继安装到图G中。把M的成员放到OPEN表中。（7）建立从M的没有在G中出现过的成员到n的指针。对M的已经在OPEN表或CLOSED表中的每个成员m，如果目前发现的到达m的最佳路径经过n，则把它的指针改为指向n。对M的每个已经在CLOSED表中的成员，修改它在图G中的所有子孙的指针，使得它们沿着目前发现的最好路径指向它们的祖先。（通过

5、建立从儿子指向父亲的指针维护搜索树Tr）23（8）按f'值递增的顺序重排序OPEN表。（9）转步骤（3）。4.2启发式搜索构造搜索树：局部搜索树：6258346175258258634634171764625825834636171373282582585235636361471471474.3实验要求（1）分别实现固定数码排列和随机生成数码的排列两种情形（2）能正确演示A*算法搜索的步骤，指示每一步的数码排列状态（3）按照实验报告要求书写并上交实验报告4.4实验环境VC++6.0Win7系统23

6、五、实验步骤：①、开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。②、点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。③、算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。④、观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运

7、行15数码难题演示实例。⑤、算法流程的任一时刻的相关状态,以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示,便于深入学习理解A*算法。⑥、根据程序运行过程画出A*算法框图。六、实验结果：1、A*算法求8数码：23232、宽度求8数码：233、深度求8数码23七、实验总结：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，

8、可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。通过本实验，我熟悉和掌握了深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解了8数码难题，理解了求解流程和搜索顺序。实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。23八、源程序代码：1、A*算法//用A*算法实现八数码问题//如：283123//0-2行，0-2列//164------》84//75765//A*