大连理工大学远程与继续教育学院《人工智能》课程设计
学习中心： ***
专 业： 计算机科学与技术 年 级： *** 学 号： *** 学 生： ***
题 目： 题目一：A*算法
1.谈谈你对本课程学习过程中的心得体会与建议？
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。通过本学期学习， 我熟悉启发式搜索的定义、估价函数和算法过程，并利用A*算法求解了8数码难题，理解了求解流程和搜索顺序。本次课程实践过程中巩固了所学的知识，通过实践也提高了自己的编程和思维能力，收获很多。
2. 《人工智能》课程设计, 从以下5个题目中任选其一作答。
题目一：A*算法
一、算法思路
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。
A*算法基本步骤
1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。 2）生成一个列表CLOSED，它的初始值为空。 3）如果OPEN表为空，则失败退出。
4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。
大连理工大学远程与继续教育学院《人工智能》课程设计
5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。
6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n的后继。
7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。 8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。 9）返回第3步。
在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。
二、算法程序框图
大连理工大学远程与继续教育学院《人工智能》课程设计
是开始 读入棋局初始状态 否是初始状态加入open表 是否可解 在open表中找到评价值最小的节点，作为当前结点 是目标节点 否扩展新状态，把不重复的新状态加入open表中 当前结点从open表移除 输出结果
结束
三、程序代码
#include
const int ROW = 3;//行数 const int COL = 3;//列数
const int MAXDISTANCE = 10000;//最多可以有的表的数目 const int MAXNUM = 10000;
typedef struct _Node{ int digit[ROW][COL];
int dist; //一个表和目的表的距离 int dep; // t深度 int index; //节点的位置 } Node;
奥鹏大连理工大学远程与继续教育学院《人工智能》课程设计
