人工智能(A星算法).doc

A*算法实验报告 实验目的 1．熟悉和掌握启发式搜索的定义、估价函数和算法过程 2. 学会利用A*算法求解N数码难题 3. 理解求解流程和搜索顺序 实验原理 A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索 ，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的 观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节 点n的代价以及从节点n到达目标节点的代价。 实验条件 1. Window NT/xp/7及以上的操作系统 2. 内存在512M以上 3. CPU在奔腾II以上 实验内容 1. 分别以8数码和15数码为例实际求解A*算法 2. 画出A*算法求解框图 3. 分析估价函数对搜索算法的影响 4. 分析A*算法的特点 实验分析 1. A*算法基本步骤 1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。 2）生成一个列表CLOSED，它的初始值为空。 3）如果OPEN表为空，则失败退出。 4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。 5）如果n是目