人工智能A星算法.docx

《人工智能A星算法.docx》由会员分享，可在线阅读，更多相关《人工智能A星算法.docx（8页珍藏版）》请在第一文库网上搜索。

1、人工智能（A星算法）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数码为例实际求解

2、A*算法2 .画出A*算法求解框图3 .分析估价函数对搜索算法的影响4 .分析A*算法的特点实验分析1. A*算法基本步骤1 ）生成一个只包含开始节点n 0的搜索图G ,把n 0放在一个叫OPEN的列表上。2 ）生成一个列表CLOSED ,它的初始值为空。3 ）如果OPEN表为空，则失败退出。4 ）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED ,称该节点为n。5）如果n是目标节点，顺着G中，从n到n的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。6 ）扩展节点n,生成其后继结点集M,在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n

3、的后继。7 ）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中,也不在CLOSED中）。把Ml的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m ,如果到目前为止找到的到达m的最好路径通过n ,就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。8）按递增f*值，重排OPEN （相同最小f*值可根据搜索树中的最深节点来解决）。9 ）返回第3步。在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低,就要重定向指向该节点的指针。已经在CLOSED

4、中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图程序代码#include #include #include using namespace std;const int ROW = 3; 行数const int COL = 3;/ 列数const int MAXDISTANCE = 10000;/最多可以有的表的数目const int MAXNUM = 10000;typedef struct _Nodeint digitROWCOL;int dist; 1/ 一个表和目的表的距离it dep; / t 深度int index; /节点的位置 Node

5、;Node src, dest;/父节表 目的表vector node_v; / 存储节点bool isEmptyOfOPENQ /open 表是否为空(for (int i = 0; i node_v.sizeQ; i+) if(node,vi.dist != MAXNUM)return false;)return true;)bool isEqual(int index, int digit COL) /判断这个最优的节点是否和目的节点一样(for (int i = 0; i ROW; i+)for (int j = 0; j COL; j+) if node_vindex.digitij

6、 != digiti jreturn false;)return true;ostream& operator(ostream& osl Node& node)(for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+)os node.digitij ,os endl;return os;)void PrintSteps(int index, vector& rstep.v) 输出每一个遍历的节点 深度遍历(rstep_v.push_back(node_vindex);index = node_vindex.index;while (index

7、!= 0)(rstep_v.push_back(node_vindexJ;index = node_vindex.index;)for (int i = rstep_v.sizeQ -1; i = 0; i-) 输出每一步的探索过程cout Step , rstep_v.sizeQ - i endl rstep_vi endl;)void Swap(int& a, int& b)int t;t = a;a = b;b = t;)void Assign(Node& node, int index)for (int i = 0; i ROW; i+)for (int j = 0; j COL; j

8、+)node.digiti j = node_vindex.digiti j;int GetMinNodeQ 找到最小的节点的位置 即最优节点(int dist = MAXNUM;int loc; / the location of minimize nodefor (int i = 0; i node.v.sizeQ; i+)(if (node_vi.dist = MAXNUM)continue;else if (nodevi.dist + node_vi.dep) dist) loc = i;dist = nodevi.dist + node_vi.dep;return loc;)bool

9、 isExpandable(Node& node)for (int i = 0; i node.v.sizeQ; i+) if (isEqual(i, node.digit)return false;return true;)int distance = 0;bool flag = false;for(int i = 0; i ROW; i+)for (int j = 0; j COL; j+)for (int k = 0; k ROW; k+) for (int 1 = 0; 1 COL; l+) if(node.digitij = digitkl distance += abs(i - k) + abs(j -1);flag = true;break;)elseflag = false;)if (flag)break;)return distance;)int MinDistance(int af int b)(return (a b ? a : b);void ProcessNode(int index)int x, y;bool flag;for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) if node_vindex.digitij = 0)